# HG changeset patch
# User marci
# Date 1078748947 0
# Node ID 4f54d89fa9d256865ad215007cb7ce0599cd938f
# Parent  ee17030e5f47afbe8ce660783a6b98abf8737458
a lot of interesting and very useful wrapper graphs

diff -r ee17030e5f47 -r 4f54d89fa9d2 src/work/bfs_iterator.hh
--- a/src/work/bfs_iterator.hh	Sun Mar 07 19:33:34 2004 +0000
+++ b/src/work/bfs_iterator.hh	Mon Mar 08 12:29:07 2004 +0000
@@ -623,10 +623,11 @@
  };  
 
 
-  template <typename GraphWrapper, typename OutEdgeIt, 
+  template <typename GraphWrapper, /*typename OutEdgeIt,*/ 
 	    typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >
   class BfsIterator5 {
     typedef typename GraphWrapper::NodeIt NodeIt;
+    typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
     GraphWrapper G;
     std::queue<NodeIt> bfs_queue;
     ReachedMap& reached;
@@ -640,6 +641,13 @@
     BfsIterator5(const GraphWrapper& _G) : 
       G(_G), reached(*(new ReachedMap(G /*, false*/))), 
       own_reached_map(true) { }
+//     BfsIterator5(const typename GraphWrapper::BaseGraph& _G, 
+// 		 ReachedMap& _reached) : 
+//       G(_G), reached(_reached), 
+//       own_reached_map(false) { }
+//     BfsIterator5(const typename GraphWrapper::BaseGraph& _G) : 
+//       G(_G), reached(*(new ReachedMap(G /*, false*/))), 
+//       own_reached_map(true) { }
     ~BfsIterator5() { if (own_reached_map) delete &reached; }
     void pushAndSetReached(NodeIt s) { 
       reached.set(s, true);
@@ -660,7 +668,7 @@
 	bfs_queue.push(s);
       }
     }
-    BfsIterator5<GraphWrapper, OutEdgeIt, ReachedMap>& 
+    BfsIterator5<GraphWrapper, /*OutEdgeIt,*/ ReachedMap>& 
     operator++() { 
       if (G.valid(actual_edge)/*.valid()*/) { 
 	/*++*/G.next(actual_edge);
@@ -758,10 +766,11 @@
     const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
   };
 
-  template <typename GraphWrapper, typename OutEdgeIt, 
+  template <typename GraphWrapper, /*typename OutEdgeIt,*/ 
 	    typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >
   class DfsIterator5 {
     typedef typename GraphWrapper::NodeIt NodeIt;
+    typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
     GraphWrapper G;
     std::stack<OutEdgeIt> dfs_stack;
     bool b_node_newly_reached;
@@ -782,7 +791,7 @@
       reached.set(s, true);
       dfs_stack.push(G.template first<OutEdgeIt>(s)); 
     }
-    DfsIterator5<GraphWrapper, OutEdgeIt, ReachedMap>& 
+    DfsIterator5<GraphWrapper, /*OutEdgeIt,*/ ReachedMap>& 
     operator++() { 
       actual_edge=dfs_stack.top();
       //actual_node=G.aNode(actual_edge);
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;
 }
diff -r ee17030e5f47 -r 4f54d89fa9d2 src/work/marci/graph_wrapper.h
--- a/src/work/marci/graph_wrapper.h	Sun Mar 07 19:33:34 2004 +0000
+++ b/src/work/marci/graph_wrapper.h	Mon Mar 08 12:29:07 2004 +0000
@@ -62,16 +62,16 @@
     template<typename T> class NodeMap : public Graph::NodeMap<T> { 
     public:
       NodeMap(const TrivGraphWrapper<Graph>& _G) : 
-	Graph::NodeMap<T>(*(_G.G)) { }
+	Graph::NodeMap<T>(_G.getGraph()) { }
       NodeMap(const TrivGraphWrapper<Graph>& _G, T a) : 
-	Graph::NodeMap<T>(*(_G.G), a) { }
+	Graph::NodeMap<T>(_G.getGraph(), a) { }
     };
     template<typename T> class EdgeMap : public Graph::EdgeMap<T> { 
     public:
       EdgeMap(const TrivGraphWrapper<Graph>& _G) : 
-	Graph::EdgeMap<T>(*(_G.G)) { }
+	Graph::EdgeMap<T>(_G.getGraph()) { }
       EdgeMap(const TrivGraphWrapper<Graph>& _G, T a) : 
-	Graph::EdgeMap<T>(*(_G.G), a) { }
+	Graph::EdgeMap<T>(_G.getGraph(), a) { }
     };
     
     void setGraph(Graph& _graph) { graph = &_graph; }
@@ -140,16 +140,16 @@
     template<typename T> class NodeMap : public Graph::NodeMap<T> { 
     public:
       NodeMap(const RevGraphWrapper<Graph>& _G) : 
-	Graph::NodeMap<T>(*(_G.G)) { }
+	Graph::NodeMap<T>(_G.getGraph()) { }
       NodeMap(const RevGraphWrapper<Graph>& _G, T a) : 
-	Graph::NodeMap<T>(*(_G.G), a) { }
+	Graph::NodeMap<T>(_G.getGraph(), a) { }
     };
     template<typename T> class EdgeMap : public Graph::EdgeMap<T> { 
     public:
       EdgeMap(const RevGraphWrapper<Graph>& _G) : 
-	Graph::EdgeMap<T>(*(_G.G)) { }
+	Graph::EdgeMap<T>(_G.getGraph()) { }
       EdgeMap(const RevGraphWrapper<Graph>& _G, T a) : 
-	Graph::EdgeMap<T>(*(_G.G), a) { }
+	Graph::EdgeMap<T>(_G.getGraph(), a) { }
     };
 
     void setGraph(Graph& _graph) { graph = &_graph; }
@@ -160,6 +160,150 @@
   };
 
 
+  template<typename Graph>
+  class UndirGraphWrapper {
+    Graph* graph;
+  
+  public:
+    typedef Graph BaseGraph;
+
+    typedef typename Graph::NodeIt NodeIt;
+    typedef typename Graph::EachNodeIt EachNodeIt;
+
+    //typedef typename Graph::EdgeIt EdgeIt;
+    //typedef typename Graph::OutEdgeIt OutEdgeIt;
+    //typedef typename Graph::InEdgeIt InEdgeIt;
+    //typedef typename Graph::SymEdgeIt SymEdgeIt;
+    //typedef typename Graph::EachEdgeIt EachEdgeIt;
+
+    //private:
+    typedef typename Graph::EdgeIt GraphEdgeIt;
+    typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
+    typedef typename Graph::InEdgeIt GraphInEdgeIt;
+    //public:
+
+    class EdgeIt {
+      friend class UndirGraphWrapper<Graph>;
+      bool out_or_in; //true iff out
+      GraphOutEdgeIt out;
+      GraphInEdgeIt in;
+    public:
+      EdgeIt() : out_or_in(true), out(), in() { }
+      operator GraphEdgeIt() const {
+	if (out_or_in) return(out); else return(in);
+      }
+    };
+
+    class OutEdgeIt : public EdgeIt {
+      friend class UndirGraphWrapper<Graph>;
+      //bool out_or_in; //true iff out
+      //GraphOutEdgeIt out;
+      //GraphInEdgeIt in;
+    public:
+      OutEdgeIt() : EdgeIt() { }
+      OutEdgeIt(const UndirGraphWrapper& _G, const NodeIt& n) : EdgeIt() { 
+	_G.graph->getFirst(out, n);
+	if (!(_G.graph->valid(out))) {
+	  out_or_in=false;
+	  _G.graph->getFirst(in, n);
+	}
+      }
+    };
+
+    OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const {
+      e.out_or_in=true;
+      graph->getFirst(e.out, n);
+      if (!(graph->valid(e.out))) {
+	e.out_or_in=false;
+	graph->getFirst(e.in, n);
+      }
+      return e;
+    }
+
+    OutEdgeIt& next(OutEdgeIt& e) const {
+      if (e.out_or_in) {
+	NodeIt n=graph->tail(e.out);
+	graph->next(e.out);
+	if (!graph->valid(e.out)) {
+	  e.out_or_in=false;
+	  graph->getFirst(e.in, n);
+	}
+      } else {
+	graph->next(e.in);
+      }
+      return e;
+    }
+
+    NodeIt aNode(const OutEdgeIt& e) const { 
+      if (e.out_or_in) return graph->tail(e); else return graph->head(e); }
+    NodeIt bNode(const OutEdgeIt& e) const { 
+      if (e.out_or_in) return graph->head(e); else return graph->tail(e); }
+
+    typedef OutEdgeIt InEdgeIt; 
+
+    template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
+//     template<typename I, typename P> I& getFirst(I& i, const P& p) const { 
+//       return graph->getFirst(i, p); }
+    
+    template<typename I> I getNext(const I& i) const { 
+      return graph->getNext(i); }
+    template<typename I> I& next(I &i) const { return graph->next(i); }    
+
+    template< typename It > It first() const { 
+      It e; getFirst(e); return e; }
+
+    template< typename It > It first(const NodeIt& v) const { 
+      It e; getFirst(e, v); return e; }
+
+    NodeIt head(const EdgeIt& e) const { return graph->head(e); }
+    NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
+
+    template<typename I> bool valid(const I& i) const 
+      { return graph->valid(i); }
+  
+    //template<typename I> void setInvalid(const I &i);
+    //{ return graph->setInvalid(i); }
+
+    int nodeNum() const { return graph->nodeNum(); }
+    int edgeNum() const { return graph->edgeNum(); }
+  
+//     template<typename I> NodeIt aNode(const I& e) const { 
+//       return graph->aNode(e); }
+//     template<typename I> NodeIt bNode(const I& e) const { 
+//       return graph->bNode(e); }
+  
+    NodeIt addNode() const { return graph->addNode(); }
+    EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const { 
+      return graph->addEdge(tail, head); }
+  
+    template<typename I> void erase(const I& i) const { graph->erase(i); }
+  
+    void clear() const { graph->clear(); }
+    
+    template<typename T> class NodeMap : public Graph::NodeMap<T> { 
+    public:
+      NodeMap(const UndirGraphWrapper<Graph>& _G) : 
+	Graph::NodeMap<T>(_G.getGraph()) { }
+      NodeMap(const UndirGraphWrapper<Graph>& _G, T a) : 
+	Graph::NodeMap<T>(_G.getGraph(), a) { }
+    };
+    template<typename T> class EdgeMap : public Graph::EdgeMap<T> { 
+    public:
+      EdgeMap(const UndirGraphWrapper<Graph>& _G) : 
+	Graph::EdgeMap<T>(_G.getGraph()) { }
+      EdgeMap(const UndirGraphWrapper<Graph>& _G, T a) : 
+	Graph::EdgeMap<T>(_G.getGraph(), a) { }
+    };
+    
+    void setGraph(Graph& _graph) { graph = &_graph; }
+    Graph& getGraph() const { return (*graph); }
+  
+    //TrivGraphWrapper() : graph(0) { }
+    UndirGraphWrapper(Graph& _graph) : graph(&_graph) { }
+  };
+
+
+
 //   template<typename Graph>
 //   class SymGraphWrapper
 //   {
@@ -247,6 +391,8 @@
       G(&_G), flow(&_flow), capacity(&_capacity) { }
 //     ResGraphWrapper(const ResGraphWrapper& res_graph_wrapper) : 
 //       G(res_graph_wrapper.G), flow(res_graph_wrapper.flow), capacity(res_graph_wrapper.capacity) { }
+    void setGraph(Graph& _graph) { graph = &_graph; }
+    Graph& getGraph() const { return (*graph); }
     class EdgeIt; 
     class OutEdgeIt; 
     friend class EdgeIt; 
@@ -499,9 +645,9 @@
     template<typename T> class NodeMap : public Graph::NodeMap<T> { 
     public:
       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) 
-	: Graph::NodeMap<T>(*(_G.G)) { }
+	: Graph::NodeMap<T>(_G.getGraph()) { }
       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, 
-	      T a) : Graph::NodeMap<T>(*(_G.G), a) { }
+	      T a) : Graph::NodeMap<T>(_G.getGraph(), a) { }
     };
 
 //     template <typename T>
@@ -518,8 +664,8 @@
     class EdgeMap {
       typename Graph::EdgeMap<T> forward_map, backward_map; 
     public:
-      EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(*(_G.G)), backward_map(*(_G.G)) { }
-      EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(*(_G.G), a), backward_map(*(_G.G), a) { }
+      EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(_G.getGraph()), backward_map(_G.getGraph()) { }
+      EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(_G.getGraph(), a), backward_map(_G.getGraph(), a) { }
       void set(EdgeIt e, T a) { 
 	if (e.out_or_in) 
 	  forward_map.set(e.out, a);