lemon-0.x: src/work/marci/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_dfs.h>

     9 #include <hugo/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 operator[](typename Graph::Edge e) const {

    24     return

    25       (node_name_map[graph.tail(e)]+"->"+node_name_map[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;

    37   Graph G;

    39   Node s=G.addNode();

    40   Node v1=G.addNode();

    41   Node v2=G.addNode();

    42   Node v3=G.addNode();

    43   Node v4=G.addNode();

    44   Node t=G.addNode();

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

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

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

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

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

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

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

    54   G.addEdge(s, v1);

    55   G.addEdge(s, v2);

    56   G.addEdge(v1, v2);

    57   G.addEdge(v2, v1);

    58   G.addEdge(v1, v3);

    59   G.addEdge(v3, v2);

    60   G.addEdge(v2, v4);

    61   G.addEdge(v4, v3);

    62   G.addEdge(v3, t);

    63   G.addEdge(v4, t);

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

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

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

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

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

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

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

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

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

    75 //   typedef TrivGraphWrapper<const Graph> CGW;

    76 //   CGW gw(G);

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

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

    80 //     cout << n << ": ";

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

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

    83 //       cout << e << " ";

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

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

    86 //       cout << e << " ";

    87 //     cout << endl;

    88 //   }

    90   {

    91     EdgeNameMap< Graph, Graph::NodeMap<string> > edge_name(G, node_name);

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

    94     for(Graph::NodeIt n(G); G.valid(n); G.next(n)) {

    95       cout << node_name[n] << ": ";

    96       cout << "out edges: ";

    97       for(Graph::OutEdgeIt e(G, n); G.valid(e); G.next(e))

    98 	cout << edge_name[e] << " ";

    99       cout << "in edges: ";

   100       for(Graph::InEdgeIt e(G, n); G.valid(e); G.next(e))

   101 	cout << edge_name[e] << " ";

   102       cout << endl;

   103     }

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

   106     BfsIterator< Graph, Graph::NodeMap<bool> > bfs(G);

   107     bfs.pushAndSetReached(s);

   108     while (!bfs.finished()) {

   109       //cout << "edge: ";

   110       if (G.valid(bfs)) {

   111 	cout << edge_name[bfs] << /*endl*/", " <<

   112 	  node_name[G.aNode(bfs)] <<

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

   114 	  node_name[G.bNode(bfs)] <<

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

   116 	   ": is not newly reached.");

   117       } else {

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

   119 	  node_name[bfs.aNode()] <<

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

   122 	  "invalid.";

   123       }

   124       cout << endl;

   125       ++bfs;

   126     }

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

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

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

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

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

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

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

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

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

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

   139     DfsIterator< Graph, Graph::NodeMap<bool> > dfs(G);

   140     dfs.pushAndSetReached(s);

   141     while (!dfs.finished()) {

   142       ++dfs;

   143       //cout << "edge: ";

   144       if (G.valid(dfs)) {

   145 	cout << edge_name[dfs] << /*endl*/", " <<

   146 	  node_name[G.aNode(dfs)] <<

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

   148 	  node_name[G.bNode(dfs)] <<

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

   150 	   ": is not newly reached.");

   151       } else {

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

   153 	  node_name[dfs.aNode()] <<

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

   156 	  "invalid.";

   157       }

   158       cout << endl;

   159     }

   160   }

   163   {

   164     typedef RevGraphWrapper<const Graph> GW;

   165     GW gw(G);

   167     EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);

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

   170     for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) {

   171       cout << node_name[GW::Node(n)] << ": ";

   172       cout << "out edges: ";

   173       for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e))

   174 	cout << edge_name[e] << " ";

   175       cout << "in edges: ";

   176       for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e))

   177 	cout << edge_name[e] << " ";

   178       cout << endl;

   179     }

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

   182     BfsIterator< GW, GW::NodeMap<bool> > bfs(gw);

   183     bfs.pushAndSetReached(t);

   184     while (!bfs.finished()) {

   185       //cout << "edge: ";

   186       if (gw.valid(GW::OutEdgeIt(bfs))) {

   187 	cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " <<

   188 	  node_name[gw.aNode(bfs)] <<

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

   190 	  node_name[gw.bNode(bfs)] <<

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

   192 	   ": is not newly reached.");

   193       } else {

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

   195 	  node_name[bfs.aNode()] <<

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

   198 	  "invalid.";

   199       }

   200       cout << endl;

   201       ++bfs;

   202     }

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

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

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

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

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

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

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

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

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

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

   215     DfsIterator< GW, GW::NodeMap<bool> > dfs(gw);

   216     dfs.pushAndSetReached(t);

   217     while (!dfs.finished()) {

   218       ++dfs;

   219       //cout << "edge: ";

   220       if (gw.valid(GW::OutEdgeIt(dfs))) {

   221 	cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " <<

   222 	  node_name[gw.aNode(dfs)] <<

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

   224 	  node_name[gw.bNode(dfs)] <<

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

   226 	   ": is not newly reached.");

   227       } else {

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

   229 	  node_name[dfs.aNode()] <<

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

   232 	  "invalid.";

   233       }

   234       cout << endl;

   235     }

   236   }

   238   {

   239     typedef UndirGraphWrapper<const Graph> GW;

   240     GW gw(G);

   242     EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);

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

   245     for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) {

   246       cout << node_name[GW::Node(n)] << ": ";

   247       cout << "out edges: ";

   248       for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e))

   249 	cout << edge_name[e] << " ";

   250       cout << "in edges: ";

   251       for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e))

   252 	cout << edge_name[e] << " ";

   253       cout << endl;

   254     }

   255 //     for(GW::EdgeIt e=gw.first<GW::EdgeIt>(); gw.valid(e); gw.next(e)) {

   256 //       cout << edge_name.get(e) << " ";

   257 //     }

   258 //     cout << endl;

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

   261     BfsIterator< GW, GW::NodeMap<bool> > bfs(gw);

   262     bfs.pushAndSetReached(t);

   263     while (!bfs.finished()) {

   264       //cout << "edge: ";

   265       if (gw.valid(GW::OutEdgeIt(bfs))) {

   266 	cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " <<

   267 	  node_name[gw.aNode(bfs)] <<

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

   269 	  node_name[gw.bNode(bfs)] <<

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

   271 	   ": is not newly reached.");

   272       } else {

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

   274 	  node_name[bfs.aNode()] <<

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

   277 	  "invalid.";

   278       }

   279       cout << endl;

   280       ++bfs;

   281     }

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

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

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

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

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

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

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

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

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

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

   294     DfsIterator< GW, GW::NodeMap<bool> > dfs(gw);

   295     dfs.pushAndSetReached(t);

   296     while (!dfs.finished()) {

   297       ++dfs;

   298       //cout << "edge: ";

   299       if (gw.valid(GW::OutEdgeIt(dfs))) {

   300 	cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " <<

   301 	  node_name[gw.aNode(dfs)] <<

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

   303 	  node_name[gw.bNode(dfs)] <<

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

   305 	   ": is not newly reached.");

   306       } else {

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

   308 	  node_name[dfs.aNode()] <<

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

   311 	  "invalid.";

   312       }

   313       cout << endl;

   314     }

   315   }

   319   {

   320     typedef BidirGraphWrapper<const Graph> GW;

   321     GW gw(G);

   323     EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);

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

   326     for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) {

   327       cout << node_name[GW::Node(n)] << ": ";

   328       cout << "out edges: ";

   329       for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e))

   330 	cout << edge_name[e] << " ";

   331       cout << "in edges: ";

   332       for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e))

   333 	cout << edge_name[e] << " ";

   334       cout << endl;

   335     }

   336 //     for(GW::EdgeIt e=gw.first<GW::EdgeIt>(); gw.valid(e); gw.next(e)) {

   337 //       cout << edge_name.get(e) << " ";

   338 //     }

   339 //     cout << endl;

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

   342     BfsIterator< GW, GW::NodeMap<bool> > bfs(gw);

   343     bfs.pushAndSetReached(t);

   344     while (!bfs.finished()) {

   345       //cout << "edge: ";

   346       if (gw.valid(GW::OutEdgeIt(bfs))) {

   347 	cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " <<

   348 	  node_name[gw.aNode(bfs)] <<

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

   350 	  node_name[gw.bNode(bfs)] <<

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

   352 	   ": is not newly reached.");

   353       } else {

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

   355 	  node_name[bfs.aNode()] <<

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

   358 	  "invalid.";

   359       }

   360       cout << endl;

   361       ++bfs;

   362     }

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

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

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

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

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

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

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

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

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

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

   375     DfsIterator< GW, GW::NodeMap<bool> > dfs(gw);

   376     dfs.pushAndSetReached(t);

   377     while (!dfs.finished()) {

   378       ++dfs;

   379       //cout << "edge: ";

   380       if (gw.valid(GW::OutEdgeIt(dfs))) {

   381 	cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " <<

   382 	  node_name[gw.aNode(dfs)] <<

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

   384 	  node_name[gw.bNode(dfs)] <<

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

   386 	   ": is not newly reached.");

   387       } else {

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

   389 	  node_name[dfs.aNode()] <<

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

   392 	  "invalid.";

   393       }

   394       cout << endl;

   395     }

   396   }

   400   return 0;

   401 }

author	marci
	Tue, 11 May 2004 12:09:06 +0000
changeset 605	b3c57602c516
parent 569	3b6afd33c221
child 642	e812963087f0
permissions	-rw-r--r--