00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
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 mln_assertion(0);
00133
00134 return 0;
00135 }
00136
00137
00138
00139
00140 template <typename E,
00141 template <typename T, typename Seq> class C>
00142 template <typename G, typename F>
00143 inline
00144 void
00145 graph_first_search_t<E, C>::operator()(const Graph<G>& g_, F& f) const
00146 {
00147 trace::entering("canvas::browsing::internal::graph_first_search");
00148
00149 const G& g = exact(g_);
00150 mln_precondition(g.is_valid());
00151
00152 f.init(g);
00153
00154 mln_vertex_iter(G) v(g);
00155 for_all(v)
00156 if (f.to_be_treated(v.id()))
00157 {
00158 container_t q;
00159 q.push(v.id());
00160 f.new_component_from_vertex(v.id());
00161 while (! q.empty())
00162 {
00163 util::vertex<G> current_v = g.vertex(next(q));
00164 f.process_vertex(current_v.id());
00165 q.pop();
00166 for (unsigned nv = 0; nv < current_v.nmax_nbh_vertices(); ++nv)
00167 if (f.to_be_queued(current_v.ith_nbh_vertex(nv)))
00168 {
00169 f.added_to_queue(current_v.ith_nbh_vertex(nv));
00170 q.push(current_v.ith_nbh_vertex(nv));
00171 }
00172 }
00173 f.next_component();
00174 }
00175 f.final();
00176
00177 trace::exiting("canvas::browsing::internal::graph_first_search");
00178 }
00179
00180 # endif // ! MLN_INCLUDE_ONLY
00181
00182 }
00183
00184 }
00185
00186 }
00187
00188 }
00189
00190
00191 #endif // ! MLN_CANVAS_BROWSING_INTERNAL_GRAPH_FIRST_SEARCH_HH