lemon-0.x: src/work/iterator_bfs

     1 // -*- c++ -*-

     2 #include <iostream>

     3 #include <vector>

     4 #include <string>

     6 #include <list_graph.h>

     7 #include <smart_graph.h>

     8 #include <bfs_iterator.h>

     9 #include <graph_wrapper.h>

    11 using namespace hugo;

    12 using std::cout;

    13 using std::endl;

    14 using std::string;

    16 template <typename Graph, typename NodeNameMap>

    17 class EdgeNameMap {

    18   Graph& graph;

    19   NodeNameMap& node_name_map;

    20 public:

    21   EdgeNameMap(Graph& _graph, NodeNameMap& _node_name_map) :

    22     graph(_graph), node_name_map(_node_name_map) { }

    23   string get(typename Graph::Edge e) const {

    24     return

    25       (node_name_map.get(graph.tail(e))+"->"+node_name_map.get(graph.head(e)));

    26   }

    27 };

    29 int main (int, char*[])

    30 {

    31   //typedef SmartGraph Graph;

    32   typedef ListGraph Graph;

    34   typedef Graph::Node Node;

    35   typedef Graph::Edge Edge;

    36   //typedef Graph::NodeIt NodeIt;

    37   //typedef Graph::EdgeIt EdgeIt;

    38   //typedef Graph::OutEdgeIt OutEdgeIt;

    39   //typedef Graph::InEdgeIt InEdgeIt;

    40   //typedef Graph::SymEdgeIt SymEdgeIt;

    42   Graph G;

    44   Node s=G.addNode();

    45   Node v1=G.addNode();

    46   Node v2=G.addNode();

    47   Node v3=G.addNode();

    48   Node v4=G.addNode();

    49   Node t=G.addNode();

    51   Graph::NodeMap<string> node_name(G);

    52   node_name.set(s, "s");

    53   node_name.set(v1, "v1");

    54   node_name.set(v2, "v2");

    55   node_name.set(v3, "v3");

    56   node_name.set(v4, "v4");

    57   node_name.set(t, "t");

    59   G.addEdge(s, v1);

    60   G.addEdge(s, v2);

    61   G.addEdge(v1, v2);

    62   G.addEdge(v2, v1);

    63   G.addEdge(v1, v3);

    64   G.addEdge(v3, v2);

    65   G.addEdge(v2, v4);

    66   G.addEdge(v4, v3);

    67   G.addEdge(v3, t);

    68   G.addEdge(v4, t);

    70   cout << "    /-->    ------------->            "<< endl;

    71   cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;

    72   cout << "  / |          |    /  /->     \\     "<< endl;

    73   cout << " /  |          |   /  |    ^    \\  "<< endl;

    74   cout << "s   |          |  /   |    |     \\->  t "<< endl;

    75   cout << " \\  |          | /    |    |     /->  "<< endl;

    76   cout << "  \\ |       --/ /     |    |    /     "<< endl;

    77   cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;

    78   cout << "    \\-->    ------------->         "<< endl;

    80 //   typedef TrivGraphWrapper<const Graph> CGW;

    81 //   CGW wG(G);

    83 //   cout << "bfs and dfs demo on the directed graph" << endl;

    84 //   for(CGW::NodeIt n=wG.first<CGW::NodeIt>(); n.valid(); ++n) {

    85 //     cout << n << ": ";

    86 //     cout << "out edges: ";

    87 //     for(CGW::OutEdgeIt e=wG.first<CGW::OutEdgeIt>(n); e.valid(); ++e)

    88 //       cout << e << " ";

    89 //     cout << "in edges: ";

    90 //     for(CGW::InEdgeIt e=wG.first<CGW::InEdgeIt>(n); e.valid(); ++e)

    91 //       cout << e << " ";

    92 //     cout << endl;

    93 //   }

    95   {

    96     typedef TrivGraphWrapper<const Graph> GW;

    97     GW wG(G);

    99     EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(wG, node_name);

   101     cout << "bfs and dfs iterator demo on the directed graph" << endl;

   102     for(GW::NodeIt n=wG.first<GW::NodeIt>(); wG.valid(n); wG.next(n)) {

   103       cout << node_name.get(n) << ": ";

   104       cout << "out edges: ";

   105       for(GW::OutEdgeIt e=wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e))

   106 	cout << edge_name.get(e) << " ";

   107       cout << "in edges: ";

   108       for(GW::InEdgeIt e=wG.first<GW::InEdgeIt>(n); wG.valid(e); wG.next(e))

   109 	cout << edge_name.get(e) << " ";

   110       cout << endl;

   111     }

   113     cout << "bfs from s ..." << endl;

   114     BfsIterator5< GW, GW::NodeMap<bool> > bfs(wG);

   115     bfs.pushAndSetReached(s);

   116     while (!bfs.finished()) {

   117       //cout << "edge: ";

   118       if (wG.valid(bfs)) {

   119 	cout << edge_name.get(bfs) << /*endl*/", " <<

   120 	  /*" aNode: " <<*/ node_name.get(wG.aNode(bfs)) <<

   121 	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<

   122 	  /*" bNode: " <<*/ node_name.get(wG.bNode(bfs)) <<

   123 	  (bfs.isBNodeNewlyReached() ? ": is newly reached." :

   124 	   ": is not newly reached.");

   125       } else {

   126 	cout << "invalid" << /*endl*/", " <<

   127 	  /*" aNode: " <<*/ node_name.get(bfs.aNode()) <<

   128 	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<

   129 	  /*" bNode: " <<*/

   130 	  "invalid.";

   131       }

   132       cout << endl;

   133       ++bfs;

   134     }

   136     cout << "    /-->    ------------->            "<< endl;

   137     cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;

   138     cout << "  / |          |    /  /->     \\     "<< endl;

   139     cout << " /  |          |   /  |    ^    \\  "<< endl;

   140     cout << "s   |          |  /   |    |     \\->  t "<< endl;

   141     cout << " \\  |          | /    |    |     /->  "<< endl;

   142     cout << "  \\ |       --/ /     |    |    /     "<< endl;

   143     cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;

   144     cout << "    \\-->    ------------->         "<< endl;

   146     cout << "dfs from s ..." << endl;

   147     DfsIterator5< GW, GW::NodeMap<bool> > dfs(wG);

   148     dfs.pushAndSetReached(s);

   149     while (!dfs.finished()) {

   150       ++dfs;

   151       //cout << "edge: ";

   152       if (wG.valid(dfs)) {

   153 	cout << edge_name.get(dfs) << /*endl*/", " <<

   154 	  /*" aNode: " <<*/ node_name.get(wG.aNode(dfs)) <<

   155 	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<

   156 	  /*" bNode: " <<*/ node_name.get(wG.bNode(dfs)) <<

   157 	  (dfs.isBNodeNewlyReached() ? ": is newly reached." :

   158 	   ": is not newly reached.");

   159       } else {

   160 	cout << "invalid" << /*endl*/", " <<

   161 	  /*" aNode: " <<*/ node_name.get(dfs.aNode()) <<

   162 	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<

   163 	  /*" bNode: " <<*/

   164 	  "invalid.";

   165       }

   166       cout << endl;

   167     }

   168   }

   171   {

   172     typedef RevGraphWrapper<const Graph> GW;

   173     GW wG(G);

   175     EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(wG, node_name);

   177     cout << "bfs and dfs iterator demo on the reversed directed graph" << endl;

   178     for(GW::NodeIt n=wG.first<GW::NodeIt>(); wG.valid(n); wG.next(n)) {

   179       cout << node_name.get(n) << ": ";

   180       cout << "out edges: ";

   181       for(GW::OutEdgeIt e=wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e))

   182 	cout << edge_name.get(e) << " ";

   183       cout << "in edges: ";

   184       for(GW::InEdgeIt e=wG.first<GW::InEdgeIt>(n); wG.valid(e); wG.next(e))

   185 	cout << edge_name.get(e) << " ";

   186       cout << endl;

   187     }

   189     cout << "bfs from t ..." << endl;

   190     BfsIterator5< GW, GW::NodeMap<bool> > bfs(wG);

   191     bfs.pushAndSetReached(t);

   192     while (!bfs.finished()) {

   193       //cout << "edge: ";

   194       if (wG.valid(bfs)) {

   195 	cout << edge_name.get(bfs) << /*endl*/", " <<

   196 	  /*" aNode: " <<*/ node_name.get(wG.aNode(bfs)) <<

   197 	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<

   198 	  /*" bNode: " <<*/ node_name.get(wG.bNode(bfs)) <<

   199 	  (bfs.isBNodeNewlyReached() ? ": is newly reached." :

   200 	   ": is not newly reached.");

   201       } else {

   202 	cout << "invalid" << /*endl*/", " <<

   203 	  /*" aNode: " <<*/ node_name.get(bfs.aNode()) <<

   204 	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<

   205 	  /*" bNode: " <<*/

   206 	  "invalid.";

   207       }

   208       cout << endl;

   209       ++bfs;

   210     }

   212     cout << "    /-->    ------------->            "<< endl;

   213     cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;

   214     cout << "  / |          |    /  /->     \\     "<< endl;

   215     cout << " /  |          |   /  |    ^    \\  "<< endl;

   216     cout << "s   |          |  /   |    |     \\->  t "<< endl;

   217     cout << " \\  |          | /    |    |     /->  "<< endl;

   218     cout << "  \\ |       --/ /     |    |    /     "<< endl;

   219     cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;

   220     cout << "    \\-->    ------------->         "<< endl;

   222     cout << "dfs from t ..." << endl;

   223     DfsIterator5< GW, GW::NodeMap<bool> > dfs(wG);

   224     dfs.pushAndSetReached(t);

   225     while (!dfs.finished()) {

   226       ++dfs;

   227       //cout << "edge: ";

   228       if (wG.valid(dfs)) {

   229 	cout << edge_name.get(dfs) << /*endl*/", " <<

   230 	  /*" aNode: " <<*/ node_name.get(wG.aNode(dfs)) <<

   231 	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<

   232 	  /*" bNode: " <<*/ node_name.get(wG.bNode(dfs)) <<

   233 	  (dfs.isBNodeNewlyReached() ? ": is newly reached." :

   234 	   ": is not newly reached.");

   235       } else {

   236 	cout << "invalid" << /*endl*/", " <<

   237 	  /*" aNode: " <<*/ node_name.get(dfs.aNode()) <<

   238 	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<

   239 	  /*" bNode: " <<*/

   240 	  "invalid.";

   241       }

   242       cout << endl;

   243     }

   244   }

   246   {

   247     typedef UndirGraphWrapper<const Graph> GW;

   248     GW wG(G);

   250     EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(wG, node_name);

   252     cout << "bfs and dfs iterator demo on the undirected graph" << endl;

   253     for(GW::NodeIt n=wG.first<GW::NodeIt>(); wG.valid(n); wG.next(n)) {

   254       cout << node_name.get(n) << ": ";

   255       cout << "out edges: ";

   256       for(GW::OutEdgeIt e=wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e))

   257 	cout << edge_name.get(e) << " ";

   258       cout << "in edges: ";

   259       for(GW::InEdgeIt e=wG.first<GW::InEdgeIt>(n); wG.valid(e); wG.next(e))

   260 	cout << edge_name.get(e) << " ";

   261       cout << endl;

   262     }

   264     cout << "bfs from t ..." << endl;

   265     BfsIterator5< GW, GW::NodeMap<bool> > bfs(wG);

   266     bfs.pushAndSetReached(t);

   267     while (!bfs.finished()) {

   268       //cout << "edge: ";

   269       if (wG.valid(GW::OutEdgeIt(bfs))) {

   270 	cout << edge_name.get(GW::OutEdgeIt(bfs)) << /*endl*/", " <<

   271 	  /*" aNode: " <<*/ node_name.get(wG.aNode(bfs)) <<

   272 	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<

   273 	  /*" bNode: " <<*/ node_name.get(wG.bNode(bfs)) <<

   274 	  (bfs.isBNodeNewlyReached() ? ": is newly reached." :

   275 	   ": is not newly reached.");

   276       } else {

   277 	cout << "invalid" << /*endl*/", " <<

   278 	  /*" aNode: " <<*/ node_name.get(bfs.aNode()) <<

   279 	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<

   280 	  /*" bNode: " <<*/

   281 	  "invalid.";

   282       }

   283       cout << endl;

   284       ++bfs;

   285     }

   287     cout << "    /-->    ------------->            "<< endl;

   288     cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;

   289     cout << "  / |          |    /  /->     \\     "<< endl;

   290     cout << " /  |          |   /  |    ^    \\  "<< endl;

   291     cout << "s   |          |  /   |    |     \\->  t "<< endl;

   292     cout << " \\  |          | /    |    |     /->  "<< endl;

   293     cout << "  \\ |       --/ /     |    |    /     "<< endl;

   294     cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;

   295     cout << "    \\-->    ------------->         "<< endl;

   297     cout << "dfs from t ..." << endl;

   298     DfsIterator5< GW, GW::NodeMap<bool> > dfs(wG);

   299     dfs.pushAndSetReached(t);

   300     while (!dfs.finished()) {

   301       ++dfs;

   302       //cout << "edge: ";

   303       if (wG.valid(GW::OutEdgeIt(dfs))) {

   304 	cout << edge_name.get(GW::OutEdgeIt(dfs)) << /*endl*/", " <<

   305 	  /*" aNode: " <<*/ node_name.get(wG.aNode(dfs)) <<

   306 	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<

   307 	  /*" bNode: " <<*/ node_name.get(wG.bNode(dfs)) <<

   308 	  (dfs.isBNodeNewlyReached() ? ": is newly reached." :

   309 	   ": is not newly reached.");

   310       } else {

   311 	cout << "invalid" << /*endl*/", " <<

   312 	  /*" aNode: " <<*/ node_name.get(dfs.aNode()) <<

   313 	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<

   314 	  /*" bNode: " <<*/

   315 	  "invalid.";

   316       }

   317       cout << endl;

   318     }

   319   }

   321   return 0;

   322 }

author	marci
	Wed, 17 Mar 2004 18:18:26 +0000
changeset 198	5cec393baade
parent 158	4f54d89fa9d2
child 234	348f8fd374ee
permissions	-rw-r--r--