Mercuriallemon-0.x / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
src/work/iterator_bfs_demo.cc
changeset 160 f1a7005e9dff
parent 107 8d62f0072ff0
child 174 44700ed9ffaa
equal deleted inserted replaced
2:ea80413231b1 3:d5b3d49532e2 
     5 #include <list_graph.hh>
 
     5 #include <list_graph.hh>
 
     6 #include <bfs_iterator.hh>
 
     6 #include <bfs_iterator.hh>
 
     7 #include <graph_wrapper.h>
 
     7 #include <graph_wrapper.h>
 
     8 
     8 
     9 using namespace hugo;
 
     9 using namespace hugo;
 
       
    10 using std::cout; 
       
    11 using std::endl;
 
       
    12 using std::string;
 
       
    13 
       
    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 };
 
    10 
    26 
    11 int main (int, char*[])
 
    27 int main (int, char*[])
 
    12 {
 
    28 {
 
    13   typedef ListGraph::NodeIt NodeIt;
 
    29   typedef ListGraph::NodeIt NodeIt;
 
    14   typedef ListGraph::EdgeIt EdgeIt;
 
    30   typedef ListGraph::EdgeIt EdgeIt;
 
    15   typedef ListGraph::EachNodeIt EachNodeIt;
 
    31   //typedef ListGraph::EachNodeIt EachNodeIt;
 
    16   typedef ListGraph::EachEdgeIt EachEdgeIt;
 
    32   //typedef ListGraph::EachEdgeIt EachEdgeIt;
 
    17   typedef ListGraph::OutEdgeIt OutEdgeIt;
 
    33   //typedef ListGraph::OutEdgeIt OutEdgeIt;
 
    18   typedef ListGraph::InEdgeIt InEdgeIt;
 
    34   //typedef ListGraph::InEdgeIt InEdgeIt;
 
    19   typedef ListGraph::SymEdgeIt SymEdgeIt;
 
    35   //typedef ListGraph::SymEdgeIt SymEdgeIt;
 
    20  
    36  
    21   ListGraph G;
 
    37   ListGraph G;
 
    22 
    38 
    23   NodeIt s=G.addNode();
 
    39   NodeIt s=G.addNode();
 
    24   NodeIt v1=G.addNode();
 
    40   NodeIt v1=G.addNode();
 
    25   NodeIt v2=G.addNode();
 
    41   NodeIt v2=G.addNode();
 
    26   NodeIt v3=G.addNode();
 
    42   NodeIt v3=G.addNode();
 
    27   NodeIt v4=G.addNode();
 
    43   NodeIt v4=G.addNode();
 
    28   NodeIt t=G.addNode();
 
    44   NodeIt t=G.addNode();
 
    29   
    45   
       
    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");
 
       
    53 
    30   G.addEdge(s, v1);
 
    54   G.addEdge(s, v1);
 
    31   G.addEdge(s, v2);
 
    55   G.addEdge(s, v2);
 
    32   G.addEdge(v1, v2);
 
    56   G.addEdge(v1, v2);
 
    33   G.addEdge(v2, v1);
 
    57   G.addEdge(v2, v1);
 
    34   G.addEdge(v1, v3);
 
    58   G.addEdge(v1, v3);
 
    36   G.addEdge(v2, v4);
 
    60   G.addEdge(v2, v4);
 
    37   G.addEdge(v4, v3);
 
    61   G.addEdge(v4, v3);
 
    38   G.addEdge(v3, t);
 
    62   G.addEdge(v3, t);
 
    39   G.addEdge(v4, t);
 
    63   G.addEdge(v4, t);
 
    40 
    64 
    41   std::cout << "bfs and dfs demo on the directed graph" << std::endl;
 
    65   cout << "    /-->    ------------->            "<< endl;
 
    42   for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) { 
    66   cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;
 
    43     std::cout << i << ": ";
 
    67   cout << "  / |          |    /  /->     \\     "<< endl;
 
    44     std::cout << "out edges: ";
 
    68   cout << " /  |          |   /  |    ^    \\  "<< endl;
 
    45     for(OutEdgeIt j=G.first<OutEdgeIt>(i); j.valid(); ++j) 
    69   cout << "s   |          |  /   |    |     \\->  t "<< endl;
 
    46       std::cout << j << " ";
 
    70   cout << " \\  |          | /    |    |     /->  "<< endl;
 
    47     std::cout << "in edges: ";
 
    71   cout << "  \\ |       --/ /     |    |    /     "<< endl;
 
    48     for(InEdgeIt j=G.first<InEdgeIt>(i); j.valid(); ++j) 
    72   cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;
 
    49       std::cout << j << " ";
 
    73   cout << "    \\-->    ------------->         "<< endl;
 
    50     std::cout << std::endl;
 
       
    51   }
 
       
    52   
    74   
    53   {
 
    75 /*
 
    54     std::cout << "iterator bfs demo 4 ..." << std::endl;
 
    76   {
 
    55     BfsIterator4< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > bfs(G);
 
    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   }
 
       
   104 
       
   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 */
 
       
   135 
       
   136 //   typedef TrivGraphWrapper<const ListGraph> CGW;
 
       
   137 //   CGW wG(G);
 
       
   138 
       
   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 //   }
 
       
   150 
       
   151   {
 
       
   152     typedef TrivGraphWrapper<const ListGraph> GW;
 
       
   153     GW wG(G);
 
       
   154 
       
   155     EdgeNameMap< GW, ListGraph::NodeMap<string> > edge_name(wG, node_name);
 
       
   156     
       
   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     }
 
       
   168 
       
   169     cout << "bfs from s ..." << endl;
 
       
   170     BfsIterator5< GW, GW::NodeMap<bool> > bfs(wG);
 
    56     bfs.pushAndSetReached(s);
 
   171     bfs.pushAndSetReached(s);
 
    57     while (!bfs.finished()) {
 
   172     while (!bfs.finished()) {
 
    58       if (OutEdgeIt(bfs).valid()) {
 
   173       //cout << "edge: ";
 
    59 	std::cout << "OutEdgeIt: " << bfs; 
   174       if (wG.valid(bfs)) {
 
    60 	std::cout << " aNode: " << G.aNode(bfs); 
   175 	cout << edge_name.get(bfs) << /*endl*/", " << 
    61 	std::cout << " bNode: " << G.bNode(bfs) << " ";
 
   176 	  /*" aNode: " <<*/ node_name.get(wG.aNode(bfs)) << 
    62       } else { 
   177 	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
    63 	std::cout << "OutEdgeIt: " << "invalid"; 
   178 	  /*" bNode: " <<*/ node_name.get(wG.bNode(bfs)) << 
    64 	std::cout << " aNode: " << bfs.aNode(); 
   179 	  (bfs.isBNodeNewlyReached() ? ": is newly reached." : 
    65 	std::cout << " bNode: " << "invalid" << " ";
 
   180 	   ": is not newly reached.");
 
    66       }
 
   181       } else { 
    67       if (bfs.isBNodeNewlyReached()) { 
   182 	cout << "invalid" << /*endl*/", " << 
    68 	std::cout << "bNodeIsNewlyReached ";
 
   183 	  /*" aNode: " <<*/ node_name.get(bfs.aNode()) << 
    69       } else { 
   184 	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
    70 	std::cout << "bNodeIsNotNewlyReached ";
 
   185 	  /*" bNode: " <<*/ 
    71       } 
   186 	  "invalid.";
 
    72       if (bfs.isANodeExamined()) { 
   187       }
 
    73 	std::cout << "aNodeIsExamined ";
 
   188       cout << endl;
 
    74       } else { 
       
    75 	std::cout << "aNodeIsNotExamined ";
 
       
    76       } 
       
    77       std::cout<<std::endl;
 
       
    78       ++bfs;
 
   189       ++bfs;
 
    79     }
 
   190     }
 
    80   }
 
   191 
    81 
   192     cout << "    /-->    ------------->            "<< endl;
 
    82   {
 
   193     cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;
 
    83     std::cout << "iterator dfs demo 4 ..." << std::endl;
 
   194     cout << "  / |          |    /  /->     \\     "<< endl;
 
    84     DfsIterator4< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > dfs(G);
 
   195     cout << " /  |          |   /  |    ^    \\  "<< endl;
 
       
   196     cout << "s   |          |  /   |    |     \\->  t "<< endl;
 
       
   197     cout << " \\  |          | /    |    |     /->  "<< endl;
 
       
   198     cout << "  \\ |       --/ /     |    |    /     "<< endl;
 
       
   199     cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;
 
       
   200     cout << "    \\-->    ------------->         "<< endl;
 
       
   201 
       
   202     cout << "dfs from s ..." << endl;
 
       
   203     DfsIterator5< GW, GW::NodeMap<bool> > dfs(wG);
 
    85     dfs.pushAndSetReached(s);
 
   204     dfs.pushAndSetReached(s);
 
    86     while (!dfs.finished()) {
 
   205     while (!dfs.finished()) {
 
    87       ++dfs;
 
   206       ++dfs;
 
    88       if (OutEdgeIt(dfs).valid()) {
 
   207       //cout << "edge: ";
 
    89 	std::cout << "OutEdgeIt: " << dfs; 
   208       if (wG.valid(dfs)) {
 
    90 	std::cout << " aNode: " << G.aNode(dfs); 
   209 	cout << edge_name.get(dfs) << /*endl*/", " << 
    91 	std::cout << " bNode: " << G.bNode(dfs) << " ";
 
   210 	  /*" aNode: " <<*/ node_name.get(wG.aNode(dfs)) << 
    92       } else { 
   211 	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
    93 	std::cout << "OutEdgeIt: " << "invalid"; 
   212 	  /*" bNode: " <<*/ node_name.get(wG.bNode(dfs)) << 
    94 	std::cout << " aNode: " << dfs.aNode(); 
   213 	  (dfs.isBNodeNewlyReached() ? ": is newly reached." : 
    95 	std::cout << " bNode: " << "invalid" << " ";
 
   214 	   ": is not newly reached.");
 
    96       }
 
   215       } else { 
    97       if (dfs.isBNodeNewlyReached()) { 
   216 	cout << "invalid" << /*endl*/", " << 
    98 	std::cout << "bNodeIsNewlyReached ";
 
   217 	  /*" aNode: " <<*/ node_name.get(dfs.aNode()) << 
    99       } else { 
   218 	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
   100 	std::cout << "bNodeIsNotNewlyReached ";
 
   219 	  /*" bNode: " <<*/ 
   101       } 
   220 	  "invalid.";
 
   102       if (dfs.isANodeExamined()) { 
   221       }
 
   103 	std::cout << "aNodeIsExamined ";
 
   222       cout << endl;
 
   104       } else { 
   223     }
 
   105 	std::cout << "aNodeIsNotExamined ";
 
   224   }
 
   106       } 
   225 
   107       std::cout<<std::endl;
 
   226 
   108       //++dfs;
 
   227   {
 
   109     }
 
   228     typedef RevGraphWrapper<const ListGraph> GW;
 
   110   }
 
   229     GW wG(G);
 
   111 
   230     
   112 
   231     EdgeNameMap< GW, ListGraph::NodeMap<string> > edge_name(wG, node_name);
 
   113   typedef ConstTrivGraphWrapper<ListGraph> CTGW;
 
   232     
   114   CTGW wG(G);
 
   233     cout << "bfs and dfs iterator demo on the reversed directed graph" << endl;
 
   115 
   234     for(GW::EachNodeIt n=wG.first<GW::EachNodeIt>(); wG.valid(n); wG.next(n)) { 
   116   std::cout << "bfs and dfs demo on the directed graph" << std::endl;
 
   235       cout << node_name.get(n) << ": ";
 
   117   for(CTGW::EachNodeIt i=wG.first<CTGW::EachNodeIt>(); i.valid(); ++i) { 
   236       cout << "out edges: ";
 
   118     std::cout << i << ": ";
 
   237       for(GW::OutEdgeIt e=wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e)) 
   119     std::cout << "out edges: ";
 
   238 	cout << edge_name.get(e) << " ";
 
   120     for(CTGW::OutEdgeIt j=wG.first<CTGW::OutEdgeIt>(i); j.valid(); ++j) 
   239       cout << "in edges: ";
 
   121       std::cout << j << " ";
 
   240       for(GW::InEdgeIt e=wG.first<GW::InEdgeIt>(n); wG.valid(e); wG.next(e)) 
   122     std::cout << "in edges: ";
 
   241 	cout << edge_name.get(e) << " ";
 
   123     for(CTGW::InEdgeIt j=wG.first<CTGW::InEdgeIt>(i); j.valid(); ++j) 
   242       cout << endl;
 
   124       std::cout << j << " ";
 
   243     }
 
   125     std::cout << std::endl;
 
   244 
   126   }
 
   245     cout << "bfs from t ..." << endl;
 
   127 
   246     BfsIterator5< GW, GW::NodeMap<bool> > bfs(wG);
 
   128 
   247     bfs.pushAndSetReached(t);
 
   129   {
 
       
   130     std::cout << "iterator bfs demo 5 ..." << std::endl;
 
       
   131     BfsIterator5< CTGW, CTGW::NodeMap<bool> > bfs(wG);
 
       
   132     bfs.pushAndSetReached(s);
 
       
   133     while (!bfs.finished()) {
 
   248     while (!bfs.finished()) {
 
   134       if (OutEdgeIt(bfs).valid()) {
 
   249       //cout << "edge: ";
 
   135 	std::cout << "OutEdgeIt: " << bfs; 
   250       if (wG.valid(bfs)) {
 
   136 	std::cout << " aNode: " << wG.aNode(bfs); 
   251 	cout << edge_name.get(bfs) << /*endl*/", " << 
   137 	std::cout << " bNode: " << wG.bNode(bfs) << " ";
 
   252 	  /*" aNode: " <<*/ node_name.get(wG.aNode(bfs)) << 
   138       } else { 
   253 	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
   139 	std::cout << "OutEdgeIt: " << "invalid"; 
   254 	  /*" bNode: " <<*/ node_name.get(wG.bNode(bfs)) << 
   140 	std::cout << " aNode: " << bfs.aNode(); 
   255 	  (bfs.isBNodeNewlyReached() ? ": is newly reached." : 
   141 	std::cout << " bNode: " << "invalid" << " ";
 
   256 	   ": is not newly reached.");
 
   142       }
 
   257       } else { 
   143       if (bfs.isBNodeNewlyReached()) { 
   258 	cout << "invalid" << /*endl*/", " << 
   144 	std::cout << "bNodeIsNewlyReached ";
 
   259 	  /*" aNode: " <<*/ node_name.get(bfs.aNode()) << 
   145       } else { 
   260 	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
   146 	std::cout << "bNodeIsNotNewlyReached ";
 
   261 	  /*" bNode: " <<*/ 
   147       } 
   262 	  "invalid.";
 
   148       if (bfs.isANodeExamined()) { 
   263       }
 
   149 	std::cout << "aNodeIsExamined ";
 
   264       cout << endl;
 
   150       } else { 
       
   151 	std::cout << "aNodeIsNotExamined ";
 
       
   152       } 
       
   153       std::cout<<std::endl;
 
       
   154       ++bfs;
 
   265       ++bfs;
 
   155     }
 
   266     }
 
   156   }
 
   267 
   157 
   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;
 
       
   277     
       
   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   }
 
       
   301 
       
   302   {
 
       
   303     typedef UndirGraphWrapper<const ListGraph> GW;
 
       
   304     GW wG(G);
 
       
   305     
       
   306     EdgeNameMap< GW, ListGraph::NodeMap<string> > edge_name(wG, node_name);
 
       
   307     
       
   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     }
 
       
   319 
       
   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     }
 
       
   342 
       
   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;
 
       
   352     
       
   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   }
 
   158 
   376 
   159   return 0;
 
   377   return 0;
 
   160 }
 
   378 }
lemon-0.x