marci@75: #include <iostream>
marci@75: #include <vector>
marci@75: #include <string>
marci@75: 
marci@75: #include <list_graph.hh>
marci@75: #include <bfs_iterator.hh>
marci@75: #include <graph_wrapper.h>
marci@75: 
alpar@107: using namespace hugo;
marci@158: using std::cout; 
marci@158: using std::endl;
marci@158: using std::string;
marci@158: 
marci@158: template <typename Graph, typename NodeNameMap>
marci@158: class EdgeNameMap {
marci@158:   Graph& graph;
marci@158:   NodeNameMap& node_name_map;
marci@158: public:
marci@158:   EdgeNameMap(Graph& _graph, NodeNameMap& _node_name_map) : 
marci@158:     graph(_graph), node_name_map(_node_name_map) { }
marci@158:   string get(typename Graph::EdgeIt e) const { 
marci@158:     return 
marci@158:       (node_name_map.get(graph.tail(e))+"->"+node_name_map.get(graph.head(e)));
marci@158:   }
marci@158: };
marci@75: 
marci@75: int main (int, char*[])
marci@75: {
marci@75:   typedef ListGraph::NodeIt NodeIt;
marci@75:   typedef ListGraph::EdgeIt EdgeIt;
marci@158:   //typedef ListGraph::EachNodeIt EachNodeIt;
marci@158:   //typedef ListGraph::EachEdgeIt EachEdgeIt;
marci@158:   //typedef ListGraph::OutEdgeIt OutEdgeIt;
marci@158:   //typedef ListGraph::InEdgeIt InEdgeIt;
marci@158:   //typedef ListGraph::SymEdgeIt SymEdgeIt;
marci@75:  
marci@75:   ListGraph G;
marci@75: 
marci@75:   NodeIt s=G.addNode();
marci@75:   NodeIt v1=G.addNode();
marci@75:   NodeIt v2=G.addNode();
marci@75:   NodeIt v3=G.addNode();
marci@75:   NodeIt v4=G.addNode();
marci@75:   NodeIt t=G.addNode();
marci@75:   
marci@158:   ListGraph::NodeMap<string> node_name(G);
marci@158:   node_name.set(s, "s");
marci@158:   node_name.set(v1, "v1");
marci@158:   node_name.set(v2, "v2");
marci@158:   node_name.set(v3, "v3");
marci@158:   node_name.set(v4, "v4");
marci@158:   node_name.set(t, "t");
marci@158: 
marci@75:   G.addEdge(s, v1);
marci@75:   G.addEdge(s, v2);
marci@75:   G.addEdge(v1, v2);
marci@75:   G.addEdge(v2, v1);
marci@75:   G.addEdge(v1, v3);
marci@75:   G.addEdge(v3, v2);
marci@75:   G.addEdge(v2, v4);
marci@75:   G.addEdge(v4, v3);
marci@75:   G.addEdge(v3, t);
marci@75:   G.addEdge(v4, t);
marci@75: 
marci@158:   cout << "    /-->    ------------->            "<< endl;
marci@158:   cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;
marci@158:   cout << "  / |          |    /  /->     \\     "<< endl;
marci@158:   cout << " /  |          |   /  |    ^    \\  "<< endl;
marci@158:   cout << "s   |          |  /   |    |     \\->  t "<< endl;
marci@158:   cout << " \\  |          | /    |    |     /->  "<< endl;
marci@158:   cout << "  \\ |       --/ /     |    |    /     "<< endl;
marci@158:   cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;
marci@158:   cout << "    \\-->    ------------->         "<< endl;
marci@158:   
marci@158: /*
marci@158:   {
marci@158:   cout << "iterator bfs demo 4 ..." << endl;
marci@158:   BfsIterator4< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > bfs(G);
marci@158:   bfs.pushAndSetReached(s);
marci@158:   while (!bfs.finished()) {
marci@158:   if (OutEdgeIt(bfs).valid()) {
marci@158:   cout << "OutEdgeIt: " << bfs; 
marci@158:   cout << " aNode: " << G.aNode(bfs); 
marci@158:   cout << " bNode: " << G.bNode(bfs) << " ";
marci@158:   } else { 
marci@158:   cout << "OutEdgeIt: " << "invalid"; 
marci@158:   cout << " aNode: " << bfs.aNode(); 
marci@158:   cout << " bNode: " << "invalid" << " ";
marci@75:   }
marci@158:   if (bfs.isBNodeNewlyReached()) { 
marci@158:   cout << "bNodeIsNewlyReached ";
marci@158:   } else { 
marci@158:   cout << "bNodeIsNotNewlyReached ";
marci@158:   } 
marci@158:   if (bfs.isANodeExamined()) { 
marci@158:   cout << "aNodeIsExamined ";
marci@158:   } else { 
marci@158:   cout << "aNodeIsNotExamined ";
marci@158:   } 
marci@158:   cout << endl;
marci@158:   ++bfs;
marci@158:   }
marci@158:   }
marci@158: 
marci@75:   {
marci@158:   cout << "iterator dfs demo 4 ..." << endl;
marci@158:   DfsIterator4< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > dfs(G);
marci@158:   dfs.pushAndSetReached(s);
marci@158:   while (!dfs.finished()) {
marci@158:   ++dfs;
marci@158:   if (OutEdgeIt(dfs).valid()) {
marci@158:   cout << "OutEdgeIt: " << dfs; 
marci@158:   cout << " aNode: " << G.aNode(dfs); 
marci@158:   cout << " bNode: " << G.bNode(dfs) << " ";
marci@158:   } else { 
marci@158:   cout << "OutEdgeIt: " << "invalid"; 
marci@158:   cout << " aNode: " << dfs.aNode(); 
marci@158:   cout << " bNode: " << "invalid" << " ";
marci@158:   }
marci@158:   if (dfs.isBNodeNewlyReached()) { 
marci@158:   cout << "bNodeIsNewlyReached ";
marci@158:   } else { 
marci@158:   cout << "bNodeIsNotNewlyReached ";
marci@158:   } 
marci@158:   if (dfs.isANodeExamined()) { 
marci@158:   cout << "aNodeIsExamined ";
marci@158:   } else { 
marci@158:   cout << "aNodeIsNotExamined ";
marci@158:   } 
marci@158:   cout << endl;
marci@158:   //++dfs;
marci@158:   }
marci@158:   }
marci@158: */
marci@158: 
marci@158: //   typedef TrivGraphWrapper<const ListGraph> CGW;
marci@158: //   CGW wG(G);
marci@158: 
marci@158: //   cout << "bfs and dfs demo on the directed graph" << endl;
marci@158: //   for(CGW::EachNodeIt n=wG.first<CGW::EachNodeIt>(); n.valid(); ++n) { 
marci@158: //     cout << n << ": ";
marci@158: //     cout << "out edges: ";
marci@158: //     for(CGW::OutEdgeIt e=wG.first<CGW::OutEdgeIt>(n); e.valid(); ++e) 
marci@158: //       cout << e << " ";
marci@158: //     cout << "in edges: ";
marci@158: //     for(CGW::InEdgeIt e=wG.first<CGW::InEdgeIt>(n); e.valid(); ++e) 
marci@158: //       cout << e << " ";
marci@158: //     cout << endl;
marci@158: //   }
marci@158: 
marci@158:   {
marci@158:     typedef TrivGraphWrapper<const ListGraph> GW;
marci@158:     GW wG(G);
marci@158: 
marci@158:     EdgeNameMap< GW, ListGraph::NodeMap<string> > edge_name(wG, node_name);
marci@158:     
marci@158:     cout << "bfs and dfs iterator demo on the directed graph" << endl;
marci@158:     for(GW::EachNodeIt n=wG.first<GW::EachNodeIt>(); wG.valid(n); wG.next(n)) { 
marci@158:       cout << node_name.get(n) << ": ";
marci@158:       cout << "out edges: ";
marci@158:       for(GW::OutEdgeIt e=wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e)) 
marci@158: 	cout << edge_name.get(e) << " ";
marci@158:       cout << "in edges: ";
marci@158:       for(GW::InEdgeIt e=wG.first<GW::InEdgeIt>(n); wG.valid(e); wG.next(e)) 
marci@158: 	cout << edge_name.get(e) << " ";
marci@158:       cout << endl;
marci@158:     }
marci@158: 
marci@158:     cout << "bfs from s ..." << endl;
marci@158:     BfsIterator5< GW, GW::NodeMap<bool> > bfs(wG);
marci@75:     bfs.pushAndSetReached(s);
marci@75:     while (!bfs.finished()) {
marci@158:       //cout << "edge: ";
marci@158:       if (wG.valid(bfs)) {
marci@158: 	cout << edge_name.get(bfs) << /*endl*/", " << 
marci@158: 	  /*" aNode: " <<*/ node_name.get(wG.aNode(bfs)) << 
marci@158: 	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
marci@158: 	  /*" bNode: " <<*/ node_name.get(wG.bNode(bfs)) << 
marci@158: 	  (bfs.isBNodeNewlyReached() ? ": is newly reached." : 
marci@158: 	   ": is not newly reached.");
marci@75:       } else { 
marci@158: 	cout << "invalid" << /*endl*/", " << 
marci@158: 	  /*" aNode: " <<*/ node_name.get(bfs.aNode()) << 
marci@158: 	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
marci@158: 	  /*" bNode: " <<*/ 
marci@158: 	  "invalid.";
marci@75:       }
marci@158:       cout << endl;
marci@158:       ++bfs;
marci@158:     }
marci@158: 
marci@158:     cout << "    /-->    ------------->            "<< endl;
marci@158:     cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;
marci@158:     cout << "  / |          |    /  /->     \\     "<< endl;
marci@158:     cout << " /  |          |   /  |    ^    \\  "<< endl;
marci@158:     cout << "s   |          |  /   |    |     \\->  t "<< endl;
marci@158:     cout << " \\  |          | /    |    |     /->  "<< endl;
marci@158:     cout << "  \\ |       --/ /     |    |    /     "<< endl;
marci@158:     cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;
marci@158:     cout << "    \\-->    ------------->         "<< endl;
marci@158: 
marci@158:     cout << "dfs from s ..." << endl;
marci@158:     DfsIterator5< GW, GW::NodeMap<bool> > dfs(wG);
marci@158:     dfs.pushAndSetReached(s);
marci@158:     while (!dfs.finished()) {
marci@158:       ++dfs;
marci@158:       //cout << "edge: ";
marci@158:       if (wG.valid(dfs)) {
marci@158: 	cout << edge_name.get(dfs) << /*endl*/", " << 
marci@158: 	  /*" aNode: " <<*/ node_name.get(wG.aNode(dfs)) << 
marci@158: 	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
marci@158: 	  /*" bNode: " <<*/ node_name.get(wG.bNode(dfs)) << 
marci@158: 	  (dfs.isBNodeNewlyReached() ? ": is newly reached." : 
marci@158: 	   ": is not newly reached.");
marci@75:       } else { 
marci@158: 	cout << "invalid" << /*endl*/", " << 
marci@158: 	  /*" aNode: " <<*/ node_name.get(dfs.aNode()) << 
marci@158: 	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
marci@158: 	  /*" bNode: " <<*/ 
marci@158: 	  "invalid.";
marci@158:       }
marci@158:       cout << endl;
marci@158:     }
marci@158:   }
marci@158: 
marci@158: 
marci@158:   {
marci@158:     typedef RevGraphWrapper<const ListGraph> GW;
marci@158:     GW wG(G);
marci@158:     
marci@158:     EdgeNameMap< GW, ListGraph::NodeMap<string> > edge_name(wG, node_name);
marci@158:     
marci@158:     cout << "bfs and dfs iterator demo on the reversed directed graph" << endl;
marci@158:     for(GW::EachNodeIt n=wG.first<GW::EachNodeIt>(); wG.valid(n); wG.next(n)) { 
marci@158:       cout << node_name.get(n) << ": ";
marci@158:       cout << "out edges: ";
marci@158:       for(GW::OutEdgeIt e=wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e)) 
marci@158: 	cout << edge_name.get(e) << " ";
marci@158:       cout << "in edges: ";
marci@158:       for(GW::InEdgeIt e=wG.first<GW::InEdgeIt>(n); wG.valid(e); wG.next(e)) 
marci@158: 	cout << edge_name.get(e) << " ";
marci@158:       cout << endl;
marci@158:     }
marci@158: 
marci@158:     cout << "bfs from t ..." << endl;
marci@158:     BfsIterator5< GW, GW::NodeMap<bool> > bfs(wG);
marci@158:     bfs.pushAndSetReached(t);
marci@158:     while (!bfs.finished()) {
marci@158:       //cout << "edge: ";
marci@158:       if (wG.valid(bfs)) {
marci@158: 	cout << edge_name.get(bfs) << /*endl*/", " << 
marci@158: 	  /*" aNode: " <<*/ node_name.get(wG.aNode(bfs)) << 
marci@158: 	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
marci@158: 	  /*" bNode: " <<*/ node_name.get(wG.bNode(bfs)) << 
marci@158: 	  (bfs.isBNodeNewlyReached() ? ": is newly reached." : 
marci@158: 	   ": is not newly reached.");
marci@75:       } else { 
marci@158: 	cout << "invalid" << /*endl*/", " << 
marci@158: 	  /*" aNode: " <<*/ node_name.get(bfs.aNode()) << 
marci@158: 	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
marci@158: 	  /*" bNode: " <<*/ 
marci@158: 	  "invalid.";
marci@158:       }
marci@158:       cout << endl;
marci@75:       ++bfs;
marci@75:     }
marci@158: 
marci@158:     cout << "    /-->    ------------->            "<< endl;
marci@158:     cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;
marci@158:     cout << "  / |          |    /  /->     \\     "<< endl;
marci@158:     cout << " /  |          |   /  |    ^    \\  "<< endl;
marci@158:     cout << "s   |          |  /   |    |     \\->  t "<< endl;
marci@158:     cout << " \\  |          | /    |    |     /->  "<< endl;
marci@158:     cout << "  \\ |       --/ /     |    |    /     "<< endl;
marci@158:     cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;
marci@158:     cout << "    \\-->    ------------->         "<< endl;
marci@158:     
marci@158:     cout << "dfs from t ..." << endl;
marci@158:     DfsIterator5< GW, GW::NodeMap<bool> > dfs(wG);
marci@158:     dfs.pushAndSetReached(t);
marci@158:     while (!dfs.finished()) {
marci@158:       ++dfs;
marci@158:       //cout << "edge: ";
marci@158:       if (wG.valid(dfs)) {
marci@158: 	cout << edge_name.get(dfs) << /*endl*/", " << 
marci@158: 	  /*" aNode: " <<*/ node_name.get(wG.aNode(dfs)) << 
marci@158: 	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
marci@158: 	  /*" bNode: " <<*/ node_name.get(wG.bNode(dfs)) << 
marci@158: 	  (dfs.isBNodeNewlyReached() ? ": is newly reached." : 
marci@158: 	   ": is not newly reached.");
marci@158:       } else { 
marci@158: 	cout << "invalid" << /*endl*/", " << 
marci@158: 	  /*" aNode: " <<*/ node_name.get(dfs.aNode()) << 
marci@158: 	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
marci@158: 	  /*" bNode: " <<*/ 
marci@158: 	  "invalid.";
marci@158:       }
marci@158:       cout << endl;
marci@158:     }
marci@75:   }
marci@75: 
marci@99:   {
marci@158:     typedef UndirGraphWrapper<const ListGraph> GW;
marci@158:     GW wG(G);
marci@158:     
marci@158:     EdgeNameMap< GW, ListGraph::NodeMap<string> > edge_name(wG, node_name);
marci@158:     
marci@158:     cout << "bfs and dfs iterator demo on the undirected graph" << endl;
marci@158:     for(GW::EachNodeIt n=wG.first<GW::EachNodeIt>(); wG.valid(n); wG.next(n)) { 
marci@158:       cout << node_name.get(n) << ": ";
marci@158:       cout << "out edges: ";
marci@158:       for(GW::OutEdgeIt e=wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e)) 
marci@158: 	cout << edge_name.get(e) << " ";
marci@158:       cout << "in edges: ";
marci@158:       for(GW::InEdgeIt e=wG.first<GW::InEdgeIt>(n); wG.valid(e); wG.next(e)) 
marci@158: 	cout << edge_name.get(e) << " ";
marci@158:       cout << endl;
marci@158:     }
marci@158: 
marci@158:     cout << "bfs from t ..." << endl;
marci@158:     BfsIterator5< GW, GW::NodeMap<bool> > bfs(wG);
marci@158:     bfs.pushAndSetReached(t);
marci@158:     while (!bfs.finished()) {
marci@158:       //cout << "edge: ";
marci@158:       if (wG.valid(GW::OutEdgeIt(bfs))) {
marci@158: 	cout << edge_name.get(GW::OutEdgeIt(bfs)) << /*endl*/", " << 
marci@158: 	  /*" aNode: " <<*/ node_name.get(wG.aNode(bfs)) << 
marci@158: 	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
marci@158: 	  /*" bNode: " <<*/ node_name.get(wG.bNode(bfs)) << 
marci@158: 	  (bfs.isBNodeNewlyReached() ? ": is newly reached." : 
marci@158: 	   ": is not newly reached.");
marci@158:       } else { 
marci@158: 	cout << "invalid" << /*endl*/", " << 
marci@158: 	  /*" aNode: " <<*/ node_name.get(bfs.aNode()) << 
marci@158: 	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
marci@158: 	  /*" bNode: " <<*/ 
marci@158: 	  "invalid.";
marci@158:       }
marci@158:       cout << endl;
marci@158:       ++bfs;
marci@158:     }
marci@158: 
marci@158:     cout << "    /-->    ------------->            "<< endl;
marci@158:     cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;
marci@158:     cout << "  / |          |    /  /->     \\     "<< endl;
marci@158:     cout << " /  |          |   /  |    ^    \\  "<< endl;
marci@158:     cout << "s   |          |  /   |    |     \\->  t "<< endl;
marci@158:     cout << " \\  |          | /    |    |     /->  "<< endl;
marci@158:     cout << "  \\ |       --/ /     |    |    /     "<< endl;
marci@158:     cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;
marci@158:     cout << "    \\-->    ------------->         "<< endl;
marci@158:     
marci@158:     cout << "dfs from t ..." << endl;
marci@158:     DfsIterator5< GW, GW::NodeMap<bool> > dfs(wG);
marci@158:     dfs.pushAndSetReached(t);
marci@99:     while (!dfs.finished()) {
marci@99:       ++dfs;
marci@158:       //cout << "edge: ";
marci@158:       if (wG.valid(GW::OutEdgeIt(dfs))) {
marci@158: 	cout << edge_name.get(GW::OutEdgeIt(dfs)) << /*endl*/", " << 
marci@158: 	  /*" aNode: " <<*/ node_name.get(wG.aNode(dfs)) << 
marci@158: 	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
marci@158: 	  /*" bNode: " <<*/ node_name.get(wG.bNode(dfs)) << 
marci@158: 	  (dfs.isBNodeNewlyReached() ? ": is newly reached." : 
marci@158: 	   ": is not newly reached.");
marci@99:       } else { 
marci@158: 	cout << "invalid" << /*endl*/", " << 
marci@158: 	  /*" aNode: " <<*/ node_name.get(dfs.aNode()) << 
marci@158: 	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
marci@158: 	  /*" bNode: " <<*/ 
marci@158: 	  "invalid.";
marci@99:       }
marci@158:       cout << endl;
marci@99:     }
marci@99:   }
marci@99: 
marci@75:   return 0;
marci@75: }