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 #include <iostream>
00027 #include <mln/util/graph.hh>
00028 #include <mln/util/array.hh>
00029
00030 #include <mln/canvas/browsing/depth_first_search.hh>
00031
00032 struct Functor
00033 {
00034 template <typename G> void init(const mln::Graph<G>& g)
00035 {
00036 deja_vu_.resize(exact(g).v_nmax());
00037 deja_vu_.fill(false);
00038 order.resize(0);
00039 }
00040
00041 bool to_be_treated(unsigned id)
00042 {
00043 return !deja_vu_[id];
00044 }
00045
00046 void new_component_from_vertex(unsigned id)
00047 {
00048 deja_vu_[id] = true;
00049 }
00050
00051 void process_vertex(unsigned id)
00052 {
00053 order.append(id);
00054 }
00055
00056 bool to_be_queued(unsigned id)
00057 {
00058 return !deja_vu_[id];
00059 }
00060
00061 void added_to_queue(unsigned id)
00062 {
00063 deja_vu_[id] = true;
00064 }
00065
00066 void next_component()
00067 {
00068 }
00069
00070 void final()
00071 {
00072 }
00073
00074 mln::util::array<unsigned> order;
00075 mln::util::array<bool> deja_vu_;
00076 };
00077
00078 int main()
00079 {
00080 using namespace mln;
00081
00082 typedef util::graph G;
00083 G g;
00084 g.add_vertices(5);
00085 g.add_edge(0,4);
00086 g.add_edge(1,2);
00087 g.add_edge(1,3);
00088 g.add_edge(4,3);
00089 g.add_edge(4,2);
00090
00091 unsigned result[] = {0, 4, 2, 1, 3};
00092 Functor f;
00093
00094 canvas::browsing::depth_first_search(g, f);
00095
00096 for (unsigned i = 0; i < f.order.size(); ++i)
00097 mln_assertion(f.order[i] == result[i]);
00098 }