lemon-0.x: src/work/marci/leda_bfs

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

     2 #include <iostream>

     3 #include <vector>

     4 #include <string>

     6 #include <LEDA/graph.h>

     8 #include <list_graph.h>

     9 #include <smart_graph.h>

    10 #include <bfs_iterator.h>

    11 #include <graph_wrapper.h>

    12 #include <leda_graph_wrapper.h>

    14 using namespace lemon;

    15 using std::cout;

    16 using std::endl;

    17 using std::string;

    19 template <typename Graph, typename NodeNameMap>

    20 class EdgeNameMap {

    21   Graph& graph;

    22   NodeNameMap& node_name_map;

    23 public:

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

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

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

    27     return

    28       (node_name_map.get(graph.source(e))+"->"+node_name_map.get(graph.target(e)));

    29   }

    30 };

    32 int main (int, char*[])

    33 {

    36   //typedef SmartGraph Graph;

    37   //typedef ListGraph Graph;

    38   typedef LedaGraphWrapper<leda::graph> Graph;

    40   typedef Graph::Node Node;

    41   typedef Graph::NodeIt NodeIt;

    42   typedef Graph::Edge Edge;

    43   typedef Graph::EdgeIt EdgeIt;

    44   typedef Graph::OutEdgeIt OutEdgeIt;

    45   typedef Graph::InEdgeIt InEdgeIt;

    48   leda::graph g;

    49   Graph G(g);

    51   Node s=G.addNode();

    52   Node v1=G.addNode();

    53   Node v2=G.addNode();

    54   Node v3=G.addNode();

    55   Node v4=G.addNode();

    56   Node t=G.addNode();

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

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

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

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

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

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

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

    66   G.addEdge(s, v1);

    67   G.addEdge(s, v2);

    68   G.addEdge(v1, v2);

    69   G.addEdge(v2, v1);

    70   G.addEdge(v1, v3);

    71   G.addEdge(v3, v2);

    72   G.addEdge(v2, v4);

    73   G.addEdge(v4, v3);

    74   G.addEdge(v3, t);

    75   G.addEdge(v4, t);

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

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

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

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

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

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

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

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

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

    87 //   typedef TrivGraphWrapper<const Graph> CGW;

    88 //   CGW wG(G);

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

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

    92 //     cout << n << ": ";

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

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

    95 //       cout << e << " ";

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

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

    98 //       cout << e << " ";

    99 //     cout << endl;

   100 //   }

   102   {

   103     typedef TrivGraphWrapper<const Graph> GW;

   104     GW wG(G);

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

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

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

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

   111       cout << "out edges: ";

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

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

   114       cout << "in edges: ";

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

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

   117       cout << endl;

   118     }

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

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

   122     bfs.pushAndSetReached(s);

   123     while (!bfs.finished()) {

   124       //cout << "edge: ";

   125       if (wG.valid(bfs)) {

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

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

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

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

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

   131 	   ": is not newly reached.");

   132       } else {

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

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

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

   136 	  /*" bNode: " <<*/

   137 	  "invalid.";

   138       }

   139       cout << endl;

   140       ++bfs;

   141     }

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

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

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

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

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

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

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

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

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

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

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

   155     dfs.pushAndSetReached(s);

   156     while (!dfs.finished()) {

   157       ++dfs;

   158       //cout << "edge: ";

   159       if (wG.valid(dfs)) {

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

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

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

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

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

   165 	   ": is not newly reached.");

   166       } else {

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

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

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

   170 	  /*" bNode: " <<*/

   171 	  "invalid.";

   172       }

   173       cout << endl;

   174     }

   175   }

   178   {

   179     typedef RevGraphWrapper<const Graph> GW;

   180     GW wG(G);

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

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

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

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

   187       cout << "out edges: ";

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

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

   190       cout << "in edges: ";

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

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

   193       cout << endl;

   194     }

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

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

   198     bfs.pushAndSetReached(t);

   199     while (!bfs.finished()) {

   200       //cout << "edge: ";

   201       if (wG.valid(bfs)) {

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

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

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

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

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

   207 	   ": is not newly reached.");

   208       } else {

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

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

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

   212 	  /*" bNode: " <<*/

   213 	  "invalid.";

   214       }

   215       cout << endl;

   216       ++bfs;

   217     }

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

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

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

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

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

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

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

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

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

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

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

   231     dfs.pushAndSetReached(t);

   232     while (!dfs.finished()) {

   233       ++dfs;

   234       //cout << "edge: ";

   235       if (wG.valid(dfs)) {

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

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

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

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

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

   241 	   ": is not newly reached.");

   242       } else {

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

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

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

   246 	  /*" bNode: " <<*/

   247 	  "invalid.";

   248       }

   249       cout << endl;

   250     }

   251   }

   253   {

   254     typedef UndirGraphWrapper<const Graph> GW;

   255     GW wG(G);

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

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

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

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

   262       cout << "out edges: ";

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

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

   265       cout << "in edges: ";

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

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

   268       cout << endl;

   269     }

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

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

   273     bfs.pushAndSetReached(t);

   274     while (!bfs.finished()) {

   275       //cout << "edge: ";

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

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

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

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

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

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

   282 	   ": is not newly reached.");

   283       } else {

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

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

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

   287 	  /*" bNode: " <<*/

   288 	  "invalid.";

   289       }

   290       cout << endl;

   291       ++bfs;

   292     }

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

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

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

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

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

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

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

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

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

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

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

   306     dfs.pushAndSetReached(t);

   307     while (!dfs.finished()) {

   308       ++dfs;

   309       //cout << "edge: ";

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

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

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

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

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

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

   316 	   ": is not newly reached.");

   317       } else {

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

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

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

   321 	  /*" bNode: " <<*/

   322 	  "invalid.";

   323       }

   324       cout << endl;

   325     }

   326   }

   328   return 0;

   329 }

author	athos
	Wed, 23 Mar 2005 10:35:36 +0000
changeset 1246	925002e098e7
parent 921	818510fa3d99
permissions	-rw-r--r--