diff -r ee5959aa4410 -r c280de819a73 src/work/marci/iterator_bfs_demo.cc
--- a/src/work/marci/iterator_bfs_demo.cc	Sun Apr 17 18:57:22 2005 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,388 +0,0 @@
-// -*- c++ -*-
-#include <iostream>
-#include <vector>
-#include <string>
-
-#include <sage_graph.h>
-#include <lemon/smart_graph.h>
-#include <bfs_dfs.h>
-#include <lemon/graph_wrapper.h>
-
-using namespace lemon;
-
-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 operator[](typename Graph::Edge e) const { 
-    return 
-      (node_name_map[graph.source(e)]+"->"+node_name_map[graph.target(e)]);
-  }
-};
-
-int main (int, char*[])
-{
-  typedef SmartGraph Graph;
-  //typedef SageGraph Graph;
-
-  typedef Graph::Node Node;
-  typedef Graph::Edge Edge;
- 
-  Graph G;
-
-  Node s=G.addNode();
-  Node v1=G.addNode();
-  Node v2=G.addNode();
-  Node v3=G.addNode();
-  Node v4=G.addNode();
-  Node t=G.addNode();
-  
-  Graph::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);
-  G.addEdge(v2, v1);
-  G.addEdge(v1, v3);
-  G.addEdge(v3, v2);
-  G.addEdge(v2, v4);
-  G.addEdge(v4, v3);
-  G.addEdge(v3, t);
-  G.addEdge(v4, t);
-
-  cout << "    /-->    ------------->            "<< endl;
-  cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;
-  cout << "  / |          |    /  /->     \\     "<< endl;
-  cout << " /  |          |   /  |    ^    \\  "<< endl;
-  cout << "s   |          |  /   |    |     \\->  t "<< endl;
-  cout << " \\  |          | /    |    |     /->  "<< endl;
-  cout << "  \\ |       --/ /     |    |    /     "<< endl;
-  cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;
-  cout << "    \\-->    ------------->         "<< endl;
-  
-  {
-    EdgeNameMap< Graph, Graph::NodeMap<string> > edge_name(G, node_name);
-    
-    cout << "bfs and dfs iterator demo on the directed graph" << endl;
-    for(Graph::NodeIt n(G); n!=INVALID; ++n) { 
-      cout << node_name[n] << ": ";
-      cout << "out edges: ";
-      for(Graph::OutEdgeIt e(G, n); e!=INVALID; ++e) 
-	cout << edge_name[e] << " ";
-      cout << "in edges: ";
-      for(Graph::InEdgeIt e(G, n); e!=INVALID; ++e) 
-	cout << edge_name[e] << " ";
-      cout << endl;
-    }
-
-    cout << "bfs from s ..." << endl;
-    BfsIterator< Graph, Graph::NodeMap<bool> > bfs(G);
-    bfs.pushAndSetReached(s);
-    while (!bfs.finished()) {
-      //cout << "edge: ";
-      if (Graph::Edge(bfs)!=INVALID) {
-	cout << edge_name[bfs] << /*endl*/", " << 
-	  node_name[G.source(bfs)] << 
-	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
-	  node_name[G.target(bfs)] << 
-	  (bfs.isBNodeNewlyReached() ? ": is newly reached." : 
-	   ": is not newly reached.");
-      } else { 
-	cout << "invalid" << /*endl*/", " << 
-	  node_name[bfs.source()] << 
-	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
-	  
-	  "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 s ..." << endl;
-    DfsIterator< Graph, Graph::NodeMap<bool> > dfs(G);
-    dfs.pushAndSetReached(s);
-    while (!dfs.finished()) {
-      ++dfs;
-      //cout << "edge: ";
-      if (Graph::Edge(dfs)!=INVALID) {
-	cout << edge_name[dfs] << /*endl*/", " << 
-	  node_name[G.source(dfs)] << 
-	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
-	  node_name[G.target(dfs)] << 
-	  (dfs.isBNodeNewlyReached() ? ": is newly reached." : 
-	   ": is not newly reached.");
-      } else { 
-	cout << "invalid" << /*endl*/", " << 
-	  node_name[dfs.source()] << 
-	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
-	  
-	  "invalid.";
-      }
-      cout << endl;
-    }
-  }
-
-
-  {
-    typedef RevGraphWrapper<const Graph> GW;
-    GW gw(G);
-    
-    EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);
-    
-    cout << "bfs and dfs iterator demo on the reversed directed graph" << endl;
-    for(GW::NodeIt n(gw); n!=INVALID; ++n) { 
-      cout << node_name[GW::Node(n)] << ": ";
-      cout << "out edges: ";
-      for(GW::OutEdgeIt e(gw, n); e!=INVALID; ++e) 
-	cout << edge_name[e] << " ";
-      cout << "in edges: ";
-      for(GW::InEdgeIt e(gw, n); e!=INVALID; ++e) 
-	cout << edge_name[e] << " ";
-      cout << endl;
-    }
-
-    cout << "bfs from t ..." << endl;
-    BfsIterator< GW, GW::NodeMap<bool> > bfs(gw);
-    bfs.pushAndSetReached(t);
-    while (!bfs.finished()) {
-      //cout << "edge: ";
-      if (GW::Edge(bfs)!=INVALID) {
-	cout << edge_name[GW::Edge(bfs)] << /*endl*/", " << 
-	  node_name[gw.source(bfs)] << 
-	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
-	  node_name[gw.target(bfs)] << 
-	  (bfs.isBNodeNewlyReached() ? ": is newly reached." : 
-	   ": is not newly reached.");
-      } else { 
-	cout << "invalid" << /*endl*/", " << 
-	  node_name[bfs.source()] << 
-	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
-	  
-	  "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;
-    DfsIterator< GW, GW::NodeMap<bool> > dfs(gw);
-    dfs.pushAndSetReached(t);
-    while (!dfs.finished()) {
-      ++dfs;
-      //cout << "edge: ";
-      if (GW::Edge(dfs)!=INVALID) {
-	cout << edge_name[GW::Edge(dfs)] << /*endl*/", " << 
-	  node_name[gw.source(dfs)] << 
-	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
-	  node_name[gw.target(dfs)] << 
-	  (dfs.isBNodeNewlyReached() ? ": is newly reached." : 
-	   ": is not newly reached.");
-      } else { 
-	cout << "invalid" << /*endl*/", " << 
-	  node_name[dfs.source()] << 
-	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
-	  
-	  "invalid.";
-      }
-      cout << endl;
-    }
-  }
-
-//   {
-//     typedef UndirGraphWrapper<const Graph> GW;
-//     GW gw(G);
-    
-//     EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);
-    
-//     cout << "bfs and dfs iterator demo on the undirected graph" << endl;
-//     for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) { 
-//       cout << node_name[GW::Node(n)] << ": ";
-//       cout << "out edges: ";
-//       for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e)) 
-// 	cout << edge_name[e] << " ";
-//       cout << "in edges: ";
-//       for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e)) 
-// 	cout << edge_name[e] << " ";
-//       cout << endl;
-//     }
-// //     for(GW::EdgeIt e=gw.first<GW::EdgeIt>(); gw.valid(e); gw.next(e)) { 
-// //       cout << edge_name.get(e) << " ";
-// //     }
-// //     cout << endl;
-
-//     cout << "bfs from t ..." << endl;
-//     BfsIterator< GW, GW::NodeMap<bool> > bfs(gw);
-//     bfs.pushAndSetReached(t);
-//     while (!bfs.finished()) {
-//       //cout << "edge: ";
-//       if (gw.valid(GW::OutEdgeIt(bfs))) {
-// 	cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " << 
-// 	  node_name[gw.aNode(bfs)] << 
-// 	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
-// 	  node_name[gw.bNode(bfs)] << 
-// 	  (bfs.isBNodeNewlyReached() ? ": is newly reached." : 
-// 	   ": is not newly reached.");
-//       } else { 
-// 	cout << "invalid" << /*endl*/", " << 
-// 	  node_name[bfs.aNode()] << 
-// 	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
-	  
-// 	  "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;
-//     DfsIterator< GW, GW::NodeMap<bool> > dfs(gw);
-//     dfs.pushAndSetReached(t);
-//     while (!dfs.finished()) {
-//       ++dfs;
-//       //cout << "edge: ";
-//       if (gw.valid(GW::OutEdgeIt(dfs))) {
-// 	cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " << 
-// 	  node_name[gw.aNode(dfs)] << 
-// 	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
-// 	  node_name[gw.bNode(dfs)] << 
-// 	  (dfs.isBNodeNewlyReached() ? ": is newly reached." : 
-// 	   ": is not newly reached.");
-//       } else { 
-// 	cout << "invalid" << /*endl*/", " << 
-// 	  node_name[dfs.aNode()] << 
-// 	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
-	  
-// 	  "invalid.";
-//       }
-//       cout << endl;
-//     }
-//   }
-
-
-
-  {
-    typedef BidirGraphWrapper<const Graph> GW;
-    GW gw(G);
-    
-    EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);
-    
-    cout << "bfs and dfs iterator demo on the bidirected graph" << endl;
-//     for(GW::EdgeIt e(gw); e!=INVALID; ++e) {
-//       cout << node_name[gw.source(e)] << "->" << node_name[gw.target(e)] << " ";
-//     } 
-    for(GW::NodeIt n(gw); n!=INVALID; ++n) { 
-      cout << node_name[GW::Node(n)] << ": ";
-      cout << "out edges: ";
-      for(GW::OutEdgeIt e(gw, n); e!=INVALID; ++e) 
-	cout << edge_name[e] << " ";
-      cout << "in edges: ";
-      for(GW::InEdgeIt e(gw, n); e!=INVALID; ++e) 
-	cout << edge_name[e] << " ";
-      cout << endl;
-    }
-//     for(GW::EdgeIt e=gw.first<GW::EdgeIt>(); gw.valid(e); gw.next(e)) { 
-//       cout << edge_name.get(e) << " ";
-//     }
-//     cout << endl;
-
-    cout << "bfs from t ..." << endl;
-    BfsIterator< GW, GW::NodeMap<bool> > bfs(gw);
-    bfs.pushAndSetReached(t);
-    while (!bfs.finished()) {
-      //cout << "edge: ";
-      if (GW::Edge(bfs)!=INVALID) {
-	cout << edge_name[GW::Edge(bfs)] << /*endl*/", " << 
-	  node_name[gw.source(bfs)] << 
-	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
-	  node_name[gw.target(bfs)] << 
-	  (bfs.isBNodeNewlyReached() ? ": is newly reached." : 
-	   ": is not newly reached.");
-      } else { 
-	cout << "invalid" << /*endl*/", " << 
-	  node_name[bfs.source()] << 
-	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
-	  
-	  "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;
-    DfsIterator< GW, GW::NodeMap<bool> > dfs(gw);
-    dfs.pushAndSetReached(t);
-    while (!dfs.finished()) {
-      ++dfs;
-      //cout << "edge: ";
-      if (GW::Edge(dfs)!=INVALID) {
-	cout << edge_name[GW::Edge(dfs)] << /*endl*/", " << 
-	  node_name[gw.source(dfs)] << 
-	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
-	  node_name[gw.target(dfs)] << 
-	  (dfs.isBNodeNewlyReached() ? ": is newly reached." : 
-	   ": is not newly reached.");
-      } else { 
-	cout << "invalid" << /*endl*/", " << 
-	  node_name[dfs.source()] << 
-	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
-	  
-	  "invalid.";
-      }
-      cout << endl;
-    }
-  }
-
-  return 0;
-}