lemon-0.x: src/work/iterator_bfs

     1 #include <iostream>

     2 #include <vector>

     3 #include <string>

     5 #include <list_graph.hh>

     6 #include <bfs_iterator.hh>

     7 #include <graph_wrapper.h>

     9 using namespace hugo;

    10 using std::cout;

    11 using std::endl;

    12 using std::string;

    14 template <typename Graph, typename NodeNameMap>

    15 class EdgeNameMap {

    16   Graph& graph;

    17   NodeNameMap& node_name_map;

    18 public:

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

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

    21   string get(typename Graph::EdgeIt e) const {

    22     return

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

    24   }

    25 };

    27 int main (int, char*[])

    28 {

    29   typedef ListGraph::NodeIt NodeIt;

    30   typedef ListGraph::EdgeIt EdgeIt;

    31   //typedef ListGraph::EachNodeIt EachNodeIt;

    32   //typedef ListGraph::EachEdgeIt EachEdgeIt;

    33   //typedef ListGraph::OutEdgeIt OutEdgeIt;

    34   //typedef ListGraph::InEdgeIt InEdgeIt;

    35   //typedef ListGraph::SymEdgeIt SymEdgeIt;

    37   ListGraph G;

    39   NodeIt s=G.addNode();

    40   NodeIt v1=G.addNode();

    41   NodeIt v2=G.addNode();

    42   NodeIt v3=G.addNode();

    43   NodeIt v4=G.addNode();

    44   NodeIt t=G.addNode();

    46   ListGraph::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 /*

    76   {

    77   cout << "iterator bfs demo 4 ..." << endl;

    78   BfsIterator4< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > bfs(G);

    79   bfs.pushAndSetReached(s);

    80   while (!bfs.finished()) {

    81   if (OutEdgeIt(bfs).valid()) {

    82   cout << "OutEdgeIt: " << bfs;

    83   cout << " aNode: " << G.aNode(bfs);

    84   cout << " bNode: " << G.bNode(bfs) << " ";

    85   } else {

    86   cout << "OutEdgeIt: " << "invalid";

    87   cout << " aNode: " << bfs.aNode();

    88   cout << " bNode: " << "invalid" << " ";

    89   }

    90   if (bfs.isBNodeNewlyReached()) {

    91   cout << "bNodeIsNewlyReached ";

    92   } else {

    93   cout << "bNodeIsNotNewlyReached ";

    94   }

    95   if (bfs.isANodeExamined()) {

    96   cout << "aNodeIsExamined ";

    97   } else {

    98   cout << "aNodeIsNotExamined ";

    99   }

   100   cout << endl;

   101   ++bfs;

   102   }

   103   }

   105   {

   106   cout << "iterator dfs demo 4 ..." << endl;

   107   DfsIterator4< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > dfs(G);

   108   dfs.pushAndSetReached(s);

   109   while (!dfs.finished()) {

   110   ++dfs;

   111   if (OutEdgeIt(dfs).valid()) {

   112   cout << "OutEdgeIt: " << dfs;

   113   cout << " aNode: " << G.aNode(dfs);

   114   cout << " bNode: " << G.bNode(dfs) << " ";

   115   } else {

   116   cout << "OutEdgeIt: " << "invalid";

   117   cout << " aNode: " << dfs.aNode();

   118   cout << " bNode: " << "invalid" << " ";

   119   }

   120   if (dfs.isBNodeNewlyReached()) {

   121   cout << "bNodeIsNewlyReached ";

   122   } else {

   123   cout << "bNodeIsNotNewlyReached ";

   124   }

   125   if (dfs.isANodeExamined()) {

   126   cout << "aNodeIsExamined ";

   127   } else {

   128   cout << "aNodeIsNotExamined ";

   129   }

   130   cout << endl;

   131   //++dfs;

   132   }

   133   }

   134 */

   136 //   typedef TrivGraphWrapper<const ListGraph> CGW;

   137 //   CGW wG(G);

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

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

   141 //     cout << n << ": ";

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

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

   144 //       cout << e << " ";

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

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

   147 //       cout << e << " ";

   148 //     cout << endl;

   149 //   }

   151   {

   152     typedef TrivGraphWrapper<const ListGraph> GW;

   153     GW wG(G);

   155     EdgeNameMap< GW, ListGraph::NodeMap<string> > edge_name(wG, node_name);

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

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

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

   160       cout << "out edges: ";

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

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

   163       cout << "in edges: ";

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

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

   166       cout << endl;

   167     }

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

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

   171     bfs.pushAndSetReached(s);

   172     while (!bfs.finished()) {

   173       //cout << "edge: ";

   174       if (wG.valid(bfs)) {

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

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

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

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

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

   180 	   ": is not newly reached.");

   181       } else {

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

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

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

   185 	  /*" bNode: " <<*/

   186 	  "invalid.";

   187       }

   188       cout << endl;

   189       ++bfs;

   190     }

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

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

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

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

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

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

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

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

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

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

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

   204     dfs.pushAndSetReached(s);

   205     while (!dfs.finished()) {

   206       ++dfs;

   207       //cout << "edge: ";

   208       if (wG.valid(dfs)) {

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

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

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

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

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

   214 	   ": is not newly reached.");

   215       } else {

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

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

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

   219 	  /*" bNode: " <<*/

   220 	  "invalid.";

   221       }

   222       cout << endl;

   223     }

   224   }

   227   {

   228     typedef RevGraphWrapper<const ListGraph> GW;

   229     GW wG(G);

   231     EdgeNameMap< GW, ListGraph::NodeMap<string> > edge_name(wG, node_name);

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

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

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

   236       cout << "out edges: ";

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

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

   239       cout << "in edges: ";

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

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

   242       cout << endl;

   243     }

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

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

   247     bfs.pushAndSetReached(t);

   248     while (!bfs.finished()) {

   249       //cout << "edge: ";

   250       if (wG.valid(bfs)) {

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

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

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

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

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

   256 	   ": is not newly reached.");

   257       } else {

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

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

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

   261 	  /*" bNode: " <<*/

   262 	  "invalid.";

   263       }

   264       cout << endl;

   265       ++bfs;

   266     }

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

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

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

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

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

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

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

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

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

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

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

   280     dfs.pushAndSetReached(t);

   281     while (!dfs.finished()) {

   282       ++dfs;

   283       //cout << "edge: ";

   284       if (wG.valid(dfs)) {

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

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

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

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

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

   290 	   ": is not newly reached.");

   291       } else {

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

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

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

   295 	  /*" bNode: " <<*/

   296 	  "invalid.";

   297       }

   298       cout << endl;

   299     }

   300   }

   302   {

   303     typedef UndirGraphWrapper<const ListGraph> GW;

   304     GW wG(G);

   306     EdgeNameMap< GW, ListGraph::NodeMap<string> > edge_name(wG, node_name);

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

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

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

   311       cout << "out edges: ";

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

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

   314       cout << "in edges: ";

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

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

   317       cout << endl;

   318     }

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

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

   322     bfs.pushAndSetReached(t);

   323     while (!bfs.finished()) {

   324       //cout << "edge: ";

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

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

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

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

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

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

   331 	   ": is not newly reached.");

   332       } else {

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

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

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

   336 	  /*" bNode: " <<*/

   337 	  "invalid.";

   338       }

   339       cout << endl;

   340       ++bfs;

   341     }

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

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

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

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

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

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

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

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

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

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

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

   355     dfs.pushAndSetReached(t);

   356     while (!dfs.finished()) {

   357       ++dfs;

   358       //cout << "edge: ";

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

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

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

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

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

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

   365 	   ": is not newly reached.");

   366       } else {

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

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

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

   370 	  /*" bNode: " <<*/

   371 	  "invalid.";

   372       }

   373       cout << endl;

   374     }

   375   }

   377   return 0;

   378 }

author	jacint
	Thu, 11 Mar 2004 23:31:13 +0000
changeset 173	de9849252e78
parent 107	8d62f0072ff0
child 174	44700ed9ffaa
permissions	-rw-r--r--