Milena (Olena)
User documentation 2.0a Id
|
00001 // Copyright (C) 2009 EPITA Research and Development Laboratory (LRDE) 00002 // 00003 // This file is part of Olena. 00004 // 00005 // Olena is free software: you can redistribute it and/or modify it under 00006 // the terms of the GNU General Public License as published by the Free 00007 // Software Foundation, version 2 of the License. 00008 // 00009 // Olena is distributed in the hope that it will be useful, 00010 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00011 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00012 // General Public License for more details. 00013 // 00014 // You should have received a copy of the GNU General Public License 00015 // along with Olena. If not, see <http://www.gnu.org/licenses/>. 00016 // 00017 // As a special exception, you may use this file as part of a free 00018 // software project without restriction. Specifically, if other files 00019 // instantiate templates or use macros or inline functions from this 00020 // file, or you compile this file and link it with other files to produce 00021 // an executable, this file does not by itself cause the resulting 00022 // executable to be covered by the GNU General Public License. This 00023 // exception does not however invalidate any other reasons why the 00024 // executable file might be covered by the GNU General Public License. 00025 00026 #ifndef MLN_CANVAS_BROWSING_INTERNAL_GRAPH_FIRST_SEARCH_HH 00027 # define MLN_CANVAS_BROWSING_INTERNAL_GRAPH_FIRST_SEARCH_HH 00028 00035 00068 # include <deque> 00069 # include <queue> 00070 # include <stack> 00071 00072 # include <mln/core/concept/iterator.hh> 00073 # include <mln/core/concept/browsing.hh> 00074 # include <mln/core/concept/graph.hh> 00075 # include <mln/util/vertex.hh> 00076 00077 00078 namespace mln 00079 { 00080 00081 namespace canvas 00082 { 00083 00084 namespace browsing 00085 { 00086 00087 namespace internal 00088 { 00089 00092 template < typename E, 00093 template <typename T, typename Seq> class C > 00094 class graph_first_search_t : public Browsing< E > 00095 { 00096 typedef util::vertex_id_t T_; 00097 typedef C< T_, std::deque<T_> > container_t; 00098 public: 00099 template <typename G, typename F> 00100 void operator()(const Graph<G>&, F& f) const; 00101 }; 00102 00103 00104 00105 # ifndef MLN_INCLUDE_ONLY 00106 00107 00109 00110 template <typename T> 00111 inline 00112 util::vertex_id_t 00113 next(const std::queue<T>& queue) 00114 { 00115 return queue.front(); 00116 } 00117 00118 template <typename T> 00119 inline 00120 util::vertex_id_t 00121 next(const std::stack<T>& stack) 00122 { 00123 return stack.top(); 00124 } 00125 00126 template <typename S> 00127 inline 00128 util::vertex_id_t 00129 next(const S& stack) 00130 { 00131 (void) stack; 00132 mln_assertion(0); 00134 // mlc_abort(S)::check(); 00135 return 0; 00136 } 00137 00138 00139 00140 00141 template <typename E, 00142 template <typename T, typename Seq> class C> 00143 template <typename G, typename F> 00144 inline 00145 void 00146 graph_first_search_t<E, C>::operator()(const Graph<G>& g_, F& f) const 00147 { 00148 trace::entering("canvas::browsing::internal::graph_first_search"); 00149 00150 const G& g = exact(g_); 00151 mln_precondition(g.is_valid()); 00152 00153 f.init(g); // <--- init 00154 00155 mln_vertex_iter(G) v(g); 00156 for_all(v) 00157 if (f.to_be_treated(v.id())) // <--- to_be_treated 00158 { 00159 container_t q; 00160 q.push(v.id()); 00161 f.new_component_from_vertex(v.id()); // <--- new_component_from_vertex 00162 while (! q.empty()) 00163 { 00164 util::vertex<G> current_v = g.vertex(next(q)); 00165 f.process_vertex(current_v.id()); // <--- process_vertex 00166 q.pop(); 00167 for (unsigned nv = 0; nv < current_v.nmax_nbh_vertices(); ++nv) 00168 if (f.to_be_queued(current_v.ith_nbh_vertex(nv))) // <--- to_be_queued 00169 { 00170 f.added_to_queue(current_v.ith_nbh_vertex(nv)); // <--- added_to_queue 00171 q.push(current_v.ith_nbh_vertex(nv)); 00172 } 00173 } 00174 f.next_component(); // <-- next_component 00175 } 00176 f.final(); // <-- final 00177 00178 trace::exiting("canvas::browsing::internal::graph_first_search"); 00179 } 00180 00181 # endif // ! MLN_INCLUDE_ONLY 00182 00183 } // end of namespace mln::canvas::browsing::internal 00184 00185 } // end of namespace mln::canvas::browsing 00186 00187 } // end of namespace mln::canvas 00188 00189 } // end of namespace mln 00190 00191 00192 #endif // ! MLN_CANVAS_BROWSING_INTERNAL_GRAPH_FIRST_SEARCH_HH