diff -r ee17030e5f47 -r 4f54d89fa9d2 src/work/iterator_bfs_demo.cc
--- a/src/work/iterator_bfs_demo.cc	Sun Mar 07 19:33:34 2004 +0000
+++ b/src/work/iterator_bfs_demo.cc	Mon Mar 08 12:29:07 2004 +0000
@@ -7,16 +7,32 @@
 #include <graph_wrapper.h>
 
 using namespace hugo;
+using std::cout; 
+using std::endl;
+using std::string;
+
+template <typename Graph, typename NodeNameMap>
+class EdgeNameMap {
+  Graph& graph;
+  NodeNameMap& node_name_map;
+public:
+  EdgeNameMap(Graph& _graph, NodeNameMap& _node_name_map) : 
+    graph(_graph), node_name_map(_node_name_map) { }
+  string get(typename Graph::EdgeIt e) const { 
+    return 
+      (node_name_map.get(graph.tail(e))+"->"+node_name_map.get(graph.head(e)));
+  }
+};
 
 int main (int, char*[])
 {
   typedef ListGraph::NodeIt NodeIt;
   typedef ListGraph::EdgeIt EdgeIt;
-  typedef ListGraph::EachNodeIt EachNodeIt;
-  typedef ListGraph::EachEdgeIt EachEdgeIt;
-  typedef ListGraph::OutEdgeIt OutEdgeIt;
-  typedef ListGraph::InEdgeIt InEdgeIt;
-  typedef ListGraph::SymEdgeIt SymEdgeIt;
+  //typedef ListGraph::EachNodeIt EachNodeIt;
+  //typedef ListGraph::EachEdgeIt EachEdgeIt;
+  //typedef ListGraph::OutEdgeIt OutEdgeIt;
+  //typedef ListGraph::InEdgeIt InEdgeIt;
+  //typedef ListGraph::SymEdgeIt SymEdgeIt;
  
   ListGraph G;
 
@@ -27,6 +43,14 @@
   NodeIt v4=G.addNode();
   NodeIt t=G.addNode();
   
+  ListGraph::NodeMap<string> node_name(G);
+  node_name.set(s, "s");
+  node_name.set(v1, "v1");
+  node_name.set(v2, "v2");
+  node_name.set(v3, "v3");
+  node_name.set(v4, "v4");
+  node_name.set(t, "t");
+
   G.addEdge(s, v1);
   G.addEdge(s, v2);
   G.addEdge(v1, v2);
@@ -38,123 +62,317 @@
   G.addEdge(v3, t);
   G.addEdge(v4, t);
 
-  std::cout << "bfs and dfs demo on the directed graph" << std::endl;
-  for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) { 
-    std::cout << i << ": ";
-    std::cout << "out edges: ";
-    for(OutEdgeIt j=G.first<OutEdgeIt>(i); j.valid(); ++j) 
-      std::cout << j << " ";
-    std::cout << "in edges: ";
-    for(InEdgeIt j=G.first<InEdgeIt>(i); j.valid(); ++j) 
-      std::cout << j << " ";
-    std::cout << std::endl;
+  cout << "    /-->    ------------->            "<< endl;
+  cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;
+  cout << "  / |          |    /  /->     \\     "<< endl;
+  cout << " /  |          |   /  |    ^    \\  "<< endl;
+  cout << "s   |          |  /   |    |     \\->  t "<< endl;
+  cout << " \\  |          | /    |    |     /->  "<< endl;
+  cout << "  \\ |       --/ /     |    |    /     "<< endl;
+  cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;
+  cout << "    \\-->    ------------->         "<< endl;
+  
+/*
+  {
+  cout << "iterator bfs demo 4 ..." << endl;
+  BfsIterator4< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > bfs(G);
+  bfs.pushAndSetReached(s);
+  while (!bfs.finished()) {
+  if (OutEdgeIt(bfs).valid()) {
+  cout << "OutEdgeIt: " << bfs; 
+  cout << " aNode: " << G.aNode(bfs); 
+  cout << " bNode: " << G.bNode(bfs) << " ";
+  } else { 
+  cout << "OutEdgeIt: " << "invalid"; 
+  cout << " aNode: " << bfs.aNode(); 
+  cout << " bNode: " << "invalid" << " ";
   }
-  
+  if (bfs.isBNodeNewlyReached()) { 
+  cout << "bNodeIsNewlyReached ";
+  } else { 
+  cout << "bNodeIsNotNewlyReached ";
+  } 
+  if (bfs.isANodeExamined()) { 
+  cout << "aNodeIsExamined ";
+  } else { 
+  cout << "aNodeIsNotExamined ";
+  } 
+  cout << endl;
+  ++bfs;
+  }
+  }
+
   {
-    std::cout << "iterator bfs demo 4 ..." << std::endl;
-    BfsIterator4< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > bfs(G);
+  cout << "iterator dfs demo 4 ..." << endl;
+  DfsIterator4< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > dfs(G);
+  dfs.pushAndSetReached(s);
+  while (!dfs.finished()) {
+  ++dfs;
+  if (OutEdgeIt(dfs).valid()) {
+  cout << "OutEdgeIt: " << dfs; 
+  cout << " aNode: " << G.aNode(dfs); 
+  cout << " bNode: " << G.bNode(dfs) << " ";
+  } else { 
+  cout << "OutEdgeIt: " << "invalid"; 
+  cout << " aNode: " << dfs.aNode(); 
+  cout << " bNode: " << "invalid" << " ";
+  }
+  if (dfs.isBNodeNewlyReached()) { 
+  cout << "bNodeIsNewlyReached ";
+  } else { 
+  cout << "bNodeIsNotNewlyReached ";
+  } 
+  if (dfs.isANodeExamined()) { 
+  cout << "aNodeIsExamined ";
+  } else { 
+  cout << "aNodeIsNotExamined ";
+  } 
+  cout << endl;
+  //++dfs;
+  }
+  }
+*/
+
+//   typedef TrivGraphWrapper<const ListGraph> CGW;
+//   CGW wG(G);
+
+//   cout << "bfs and dfs demo on the directed graph" << endl;
+//   for(CGW::EachNodeIt n=wG.first<CGW::EachNodeIt>(); n.valid(); ++n) { 
+//     cout << n << ": ";
+//     cout << "out edges: ";
+//     for(CGW::OutEdgeIt e=wG.first<CGW::OutEdgeIt>(n); e.valid(); ++e) 
+//       cout << e << " ";
+//     cout << "in edges: ";
+//     for(CGW::InEdgeIt e=wG.first<CGW::InEdgeIt>(n); e.valid(); ++e) 
+//       cout << e << " ";
+//     cout << endl;
+//   }
+
+  {
+    typedef TrivGraphWrapper<const ListGraph> GW;
+    GW wG(G);
+
+    EdgeNameMap< GW, ListGraph::NodeMap<string> > edge_name(wG, node_name);
+    
+    cout << "bfs and dfs iterator demo on the directed graph" << endl;
+    for(GW::EachNodeIt n=wG.first<GW::EachNodeIt>(); wG.valid(n); wG.next(n)) { 
+      cout << node_name.get(n) << ": ";
+      cout << "out edges: ";
+      for(GW::OutEdgeIt e=wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e)) 
+	cout << edge_name.get(e) << " ";
+      cout << "in edges: ";
+      for(GW::InEdgeIt e=wG.first<GW::InEdgeIt>(n); wG.valid(e); wG.next(e)) 
+	cout << edge_name.get(e) << " ";
+      cout << endl;
+    }
+
+    cout << "bfs from s ..." << endl;
+    BfsIterator5< GW, GW::NodeMap<bool> > bfs(wG);
     bfs.pushAndSetReached(s);
     while (!bfs.finished()) {
-      if (OutEdgeIt(bfs).valid()) {
-	std::cout << "OutEdgeIt: " << bfs; 
-	std::cout << " aNode: " << G.aNode(bfs); 
-	std::cout << " bNode: " << G.bNode(bfs) << " ";
+      //cout << "edge: ";
+      if (wG.valid(bfs)) {
+	cout << edge_name.get(bfs) << /*endl*/", " << 
+	  /*" aNode: " <<*/ node_name.get(wG.aNode(bfs)) << 
+	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
+	  /*" bNode: " <<*/ node_name.get(wG.bNode(bfs)) << 
+	  (bfs.isBNodeNewlyReached() ? ": is newly reached." : 
+	   ": is not newly reached.");
       } else { 
-	std::cout << "OutEdgeIt: " << "invalid"; 
-	std::cout << " aNode: " << bfs.aNode(); 
-	std::cout << " bNode: " << "invalid" << " ";
+	cout << "invalid" << /*endl*/", " << 
+	  /*" aNode: " <<*/ node_name.get(bfs.aNode()) << 
+	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
+	  /*" bNode: " <<*/ 
+	  "invalid.";
       }
-      if (bfs.isBNodeNewlyReached()) { 
-	std::cout << "bNodeIsNewlyReached ";
+      cout << endl;
+      ++bfs;
+    }
+
+    cout << "    /-->    ------------->            "<< endl;
+    cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;
+    cout << "  / |          |    /  /->     \\     "<< endl;
+    cout << " /  |          |   /  |    ^    \\  "<< endl;
+    cout << "s   |          |  /   |    |     \\->  t "<< endl;
+    cout << " \\  |          | /    |    |     /->  "<< endl;
+    cout << "  \\ |       --/ /     |    |    /     "<< endl;
+    cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;
+    cout << "    \\-->    ------------->         "<< endl;
+
+    cout << "dfs from s ..." << endl;
+    DfsIterator5< GW, GW::NodeMap<bool> > dfs(wG);
+    dfs.pushAndSetReached(s);
+    while (!dfs.finished()) {
+      ++dfs;
+      //cout << "edge: ";
+      if (wG.valid(dfs)) {
+	cout << edge_name.get(dfs) << /*endl*/", " << 
+	  /*" aNode: " <<*/ node_name.get(wG.aNode(dfs)) << 
+	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
+	  /*" bNode: " <<*/ node_name.get(wG.bNode(dfs)) << 
+	  (dfs.isBNodeNewlyReached() ? ": is newly reached." : 
+	   ": is not newly reached.");
       } else { 
-	std::cout << "bNodeIsNotNewlyReached ";
-      } 
-      if (bfs.isANodeExamined()) { 
-	std::cout << "aNodeIsExamined ";
+	cout << "invalid" << /*endl*/", " << 
+	  /*" aNode: " <<*/ node_name.get(dfs.aNode()) << 
+	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
+	  /*" bNode: " <<*/ 
+	  "invalid.";
+      }
+      cout << endl;
+    }
+  }
+
+
+  {
+    typedef RevGraphWrapper<const ListGraph> GW;
+    GW wG(G);
+    
+    EdgeNameMap< GW, ListGraph::NodeMap<string> > edge_name(wG, node_name);
+    
+    cout << "bfs and dfs iterator demo on the reversed directed graph" << endl;
+    for(GW::EachNodeIt n=wG.first<GW::EachNodeIt>(); wG.valid(n); wG.next(n)) { 
+      cout << node_name.get(n) << ": ";
+      cout << "out edges: ";
+      for(GW::OutEdgeIt e=wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e)) 
+	cout << edge_name.get(e) << " ";
+      cout << "in edges: ";
+      for(GW::InEdgeIt e=wG.first<GW::InEdgeIt>(n); wG.valid(e); wG.next(e)) 
+	cout << edge_name.get(e) << " ";
+      cout << endl;
+    }
+
+    cout << "bfs from t ..." << endl;
+    BfsIterator5< GW, GW::NodeMap<bool> > bfs(wG);
+    bfs.pushAndSetReached(t);
+    while (!bfs.finished()) {
+      //cout << "edge: ";
+      if (wG.valid(bfs)) {
+	cout << edge_name.get(bfs) << /*endl*/", " << 
+	  /*" aNode: " <<*/ node_name.get(wG.aNode(bfs)) << 
+	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
+	  /*" bNode: " <<*/ node_name.get(wG.bNode(bfs)) << 
+	  (bfs.isBNodeNewlyReached() ? ": is newly reached." : 
+	   ": is not newly reached.");
       } else { 
-	std::cout << "aNodeIsNotExamined ";
-      } 
-      std::cout<<std::endl;
+	cout << "invalid" << /*endl*/", " << 
+	  /*" aNode: " <<*/ node_name.get(bfs.aNode()) << 
+	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
+	  /*" bNode: " <<*/ 
+	  "invalid.";
+      }
+      cout << endl;
       ++bfs;
     }
+
+    cout << "    /-->    ------------->            "<< endl;
+    cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;
+    cout << "  / |          |    /  /->     \\     "<< endl;
+    cout << " /  |          |   /  |    ^    \\  "<< endl;
+    cout << "s   |          |  /   |    |     \\->  t "<< endl;
+    cout << " \\  |          | /    |    |     /->  "<< endl;
+    cout << "  \\ |       --/ /     |    |    /     "<< endl;
+    cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;
+    cout << "    \\-->    ------------->         "<< endl;
+    
+    cout << "dfs from t ..." << endl;
+    DfsIterator5< GW, GW::NodeMap<bool> > dfs(wG);
+    dfs.pushAndSetReached(t);
+    while (!dfs.finished()) {
+      ++dfs;
+      //cout << "edge: ";
+      if (wG.valid(dfs)) {
+	cout << edge_name.get(dfs) << /*endl*/", " << 
+	  /*" aNode: " <<*/ node_name.get(wG.aNode(dfs)) << 
+	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
+	  /*" bNode: " <<*/ node_name.get(wG.bNode(dfs)) << 
+	  (dfs.isBNodeNewlyReached() ? ": is newly reached." : 
+	   ": is not newly reached.");
+      } else { 
+	cout << "invalid" << /*endl*/", " << 
+	  /*" aNode: " <<*/ node_name.get(dfs.aNode()) << 
+	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
+	  /*" bNode: " <<*/ 
+	  "invalid.";
+      }
+      cout << endl;
+    }
   }
 
   {
-    std::cout << "iterator dfs demo 4 ..." << std::endl;
-    DfsIterator4< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > dfs(G);
-    dfs.pushAndSetReached(s);
+    typedef UndirGraphWrapper<const ListGraph> GW;
+    GW wG(G);
+    
+    EdgeNameMap< GW, ListGraph::NodeMap<string> > edge_name(wG, node_name);
+    
+    cout << "bfs and dfs iterator demo on the undirected graph" << endl;
+    for(GW::EachNodeIt n=wG.first<GW::EachNodeIt>(); wG.valid(n); wG.next(n)) { 
+      cout << node_name.get(n) << ": ";
+      cout << "out edges: ";
+      for(GW::OutEdgeIt e=wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e)) 
+	cout << edge_name.get(e) << " ";
+      cout << "in edges: ";
+      for(GW::InEdgeIt e=wG.first<GW::InEdgeIt>(n); wG.valid(e); wG.next(e)) 
+	cout << edge_name.get(e) << " ";
+      cout << endl;
+    }
+
+    cout << "bfs from t ..." << endl;
+    BfsIterator5< GW, GW::NodeMap<bool> > bfs(wG);
+    bfs.pushAndSetReached(t);
+    while (!bfs.finished()) {
+      //cout << "edge: ";
+      if (wG.valid(GW::OutEdgeIt(bfs))) {
+	cout << edge_name.get(GW::OutEdgeIt(bfs)) << /*endl*/", " << 
+	  /*" aNode: " <<*/ node_name.get(wG.aNode(bfs)) << 
+	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
+	  /*" bNode: " <<*/ node_name.get(wG.bNode(bfs)) << 
+	  (bfs.isBNodeNewlyReached() ? ": is newly reached." : 
+	   ": is not newly reached.");
+      } else { 
+	cout << "invalid" << /*endl*/", " << 
+	  /*" aNode: " <<*/ node_name.get(bfs.aNode()) << 
+	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
+	  /*" bNode: " <<*/ 
+	  "invalid.";
+      }
+      cout << endl;
+      ++bfs;
+    }
+
+    cout << "    /-->    ------------->            "<< endl;
+    cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;
+    cout << "  / |          |    /  /->     \\     "<< endl;
+    cout << " /  |          |   /  |    ^    \\  "<< endl;
+    cout << "s   |          |  /   |    |     \\->  t "<< endl;
+    cout << " \\  |          | /    |    |     /->  "<< endl;
+    cout << "  \\ |       --/ /     |    |    /     "<< endl;
+    cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;
+    cout << "    \\-->    ------------->         "<< endl;
+    
+    cout << "dfs from t ..." << endl;
+    DfsIterator5< GW, GW::NodeMap<bool> > dfs(wG);
+    dfs.pushAndSetReached(t);
     while (!dfs.finished()) {
       ++dfs;
-      if (OutEdgeIt(dfs).valid()) {
-	std::cout << "OutEdgeIt: " << dfs; 
-	std::cout << " aNode: " << G.aNode(dfs); 
-	std::cout << " bNode: " << G.bNode(dfs) << " ";
+      //cout << "edge: ";
+      if (wG.valid(GW::OutEdgeIt(dfs))) {
+	cout << edge_name.get(GW::OutEdgeIt(dfs)) << /*endl*/", " << 
+	  /*" aNode: " <<*/ node_name.get(wG.aNode(dfs)) << 
+	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
+	  /*" bNode: " <<*/ node_name.get(wG.bNode(dfs)) << 
+	  (dfs.isBNodeNewlyReached() ? ": is newly reached." : 
+	   ": is not newly reached.");
       } else { 
-	std::cout << "OutEdgeIt: " << "invalid"; 
-	std::cout << " aNode: " << dfs.aNode(); 
-	std::cout << " bNode: " << "invalid" << " ";
+	cout << "invalid" << /*endl*/", " << 
+	  /*" aNode: " <<*/ node_name.get(dfs.aNode()) << 
+	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
+	  /*" bNode: " <<*/ 
+	  "invalid.";
       }
-      if (dfs.isBNodeNewlyReached()) { 
-	std::cout << "bNodeIsNewlyReached ";
-      } else { 
-	std::cout << "bNodeIsNotNewlyReached ";
-      } 
-      if (dfs.isANodeExamined()) { 
-	std::cout << "aNodeIsExamined ";
-      } else { 
-	std::cout << "aNodeIsNotExamined ";
-      } 
-      std::cout<<std::endl;
-      //++dfs;
+      cout << endl;
     }
   }
 
-
-  typedef ConstTrivGraphWrapper<ListGraph> CTGW;
-  CTGW wG(G);
-
-  std::cout << "bfs and dfs demo on the directed graph" << std::endl;
-  for(CTGW::EachNodeIt i=wG.first<CTGW::EachNodeIt>(); i.valid(); ++i) { 
-    std::cout << i << ": ";
-    std::cout << "out edges: ";
-    for(CTGW::OutEdgeIt j=wG.first<CTGW::OutEdgeIt>(i); j.valid(); ++j) 
-      std::cout << j << " ";
-    std::cout << "in edges: ";
-    for(CTGW::InEdgeIt j=wG.first<CTGW::InEdgeIt>(i); j.valid(); ++j) 
-      std::cout << j << " ";
-    std::cout << std::endl;
-  }
-
-
-  {
-    std::cout << "iterator bfs demo 5 ..." << std::endl;
-    BfsIterator5< CTGW, CTGW::NodeMap<bool> > bfs(wG);
-    bfs.pushAndSetReached(s);
-    while (!bfs.finished()) {
-      if (OutEdgeIt(bfs).valid()) {
-	std::cout << "OutEdgeIt: " << bfs; 
-	std::cout << " aNode: " << wG.aNode(bfs); 
-	std::cout << " bNode: " << wG.bNode(bfs) << " ";
-      } else { 
-	std::cout << "OutEdgeIt: " << "invalid"; 
-	std::cout << " aNode: " << bfs.aNode(); 
-	std::cout << " bNode: " << "invalid" << " ";
-      }
-      if (bfs.isBNodeNewlyReached()) { 
-	std::cout << "bNodeIsNewlyReached ";
-      } else { 
-	std::cout << "bNodeIsNotNewlyReached ";
-      } 
-      if (bfs.isANodeExamined()) { 
-	std::cout << "aNodeIsExamined ";
-      } else { 
-	std::cout << "aNodeIsNotExamined ";
-      } 
-      std::cout<<std::endl;
-      ++bfs;
-    }
-  }
-
-
   return 0;
 }