marci@301: // -*- c++ -*-
marci@301: #include <iostream>
marci@301: #include <vector>
marci@301: #include <string>
marci@301: 
marci@642: #include <sage_graph.h>
alpar@774: #include <hugo/smart_graph.h>
marci@602: #include <bfs_dfs.h>
marci@557: #include <hugo/graph_wrapper.h>
marci@301: 
marci@301: using namespace hugo;
marci@777: 
marci@301: using std::cout; 
marci@301: using std::endl;
marci@301: using std::string;
marci@301: 
marci@301: template <typename Graph, typename NodeNameMap>
marci@301: class EdgeNameMap {
marci@301:   Graph& graph;
marci@301:   NodeNameMap& node_name_map;
marci@301: public:
marci@301:   EdgeNameMap(Graph& _graph, NodeNameMap& _node_name_map) : 
marci@301:     graph(_graph), node_name_map(_node_name_map) { }
marci@304:   string operator[](typename Graph::Edge e) const { 
marci@301:     return 
marci@304:       (node_name_map[graph.tail(e)]+"->"+node_name_map[graph.head(e)]);
marci@301:   }
marci@301: };
marci@301: 
marci@301: int main (int, char*[])
marci@301: {
alpar@774:   typedef SmartGraph Graph;
alpar@774:   //typedef SageGraph Graph;
marci@301: 
marci@301:   typedef Graph::Node Node;
marci@301:   typedef Graph::Edge Edge;
marci@301:  
marci@301:   Graph G;
marci@301: 
marci@301:   Node s=G.addNode();
marci@301:   Node v1=G.addNode();
marci@301:   Node v2=G.addNode();
marci@301:   Node v3=G.addNode();
marci@301:   Node v4=G.addNode();
marci@301:   Node t=G.addNode();
marci@301:   
marci@301:   Graph::NodeMap<string> node_name(G);
marci@301:   node_name.set(s, "s");
marci@301:   node_name.set(v1, "v1");
marci@301:   node_name.set(v2, "v2");
marci@301:   node_name.set(v3, "v3");
marci@301:   node_name.set(v4, "v4");
marci@301:   node_name.set(t, "t");
marci@301: 
marci@301:   G.addEdge(s, v1);
marci@301:   G.addEdge(s, v2);
marci@301:   G.addEdge(v1, v2);
marci@301:   G.addEdge(v2, v1);
marci@301:   G.addEdge(v1, v3);
marci@301:   G.addEdge(v3, v2);
marci@301:   G.addEdge(v2, v4);
marci@301:   G.addEdge(v4, v3);
marci@301:   G.addEdge(v3, t);
marci@301:   G.addEdge(v4, t);
marci@301: 
marci@301:   cout << "    /-->    ------------->            "<< endl;
marci@301:   cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;
marci@301:   cout << "  / |          |    /  /->     \\     "<< endl;
marci@301:   cout << " /  |          |   /  |    ^    \\  "<< endl;
marci@301:   cout << "s   |          |  /   |    |     \\->  t "<< endl;
marci@301:   cout << " \\  |          | /    |    |     /->  "<< endl;
marci@301:   cout << "  \\ |       --/ /     |    |    /     "<< endl;
marci@301:   cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;
marci@301:   cout << "    \\-->    ------------->         "<< endl;
marci@301:   
marci@301:   {
marci@312:     EdgeNameMap< Graph, Graph::NodeMap<string> > edge_name(G, node_name);
marci@301:     
marci@301:     cout << "bfs and dfs iterator demo on the directed graph" << endl;
alpar@774:     for(Graph::NodeIt n(G); n!=INVALID; ++n) { 
marci@304:       cout << node_name[n] << ": ";
marci@301:       cout << "out edges: ";
alpar@774:       for(Graph::OutEdgeIt e(G, n); e!=INVALID; ++e) 
marci@304: 	cout << edge_name[e] << " ";
marci@301:       cout << "in edges: ";
alpar@774:       for(Graph::InEdgeIt e(G, n); e!=INVALID; ++e) 
marci@304: 	cout << edge_name[e] << " ";
marci@301:       cout << endl;
marci@301:     }
marci@301: 
marci@301:     cout << "bfs from s ..." << endl;
marci@360:     BfsIterator< Graph, Graph::NodeMap<bool> > bfs(G);
marci@301:     bfs.pushAndSetReached(s);
marci@301:     while (!bfs.finished()) {
marci@301:       //cout << "edge: ";
marci@777:       if (Graph::Edge(bfs)!=INVALID) {
marci@304: 	cout << edge_name[bfs] << /*endl*/", " << 
alpar@774: 	  node_name[G.tail(bfs)] << 
marci@301: 	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
alpar@774: 	  node_name[G.head(bfs)] << 
marci@301: 	  (bfs.isBNodeNewlyReached() ? ": is newly reached." : 
marci@301: 	   ": is not newly reached.");
marci@301:       } else { 
marci@301: 	cout << "invalid" << /*endl*/", " << 
marci@777: 	  node_name[bfs.tail()] << 
marci@301: 	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
marci@301: 	  
marci@301: 	  "invalid.";
marci@301:       }
marci@301:       cout << endl;
marci@301:       ++bfs;
marci@301:     }
marci@301: 
marci@301:     cout << "    /-->    ------------->            "<< endl;
marci@301:     cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;
marci@301:     cout << "  / |          |    /  /->     \\     "<< endl;
marci@301:     cout << " /  |          |   /  |    ^    \\  "<< endl;
marci@301:     cout << "s   |          |  /   |    |     \\->  t "<< endl;
marci@301:     cout << " \\  |          | /    |    |     /->  "<< endl;
marci@301:     cout << "  \\ |       --/ /     |    |    /     "<< endl;
marci@301:     cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;
marci@301:     cout << "    \\-->    ------------->         "<< endl;
marci@301: 
marci@301:     cout << "dfs from s ..." << endl;
marci@360:     DfsIterator< Graph, Graph::NodeMap<bool> > dfs(G);
marci@301:     dfs.pushAndSetReached(s);
marci@301:     while (!dfs.finished()) {
marci@301:       ++dfs;
marci@301:       //cout << "edge: ";
marci@777:       if (Graph::Edge(dfs)!=INVALID) {
marci@304: 	cout << edge_name[dfs] << /*endl*/", " << 
alpar@774: 	  node_name[G.tail(dfs)] << 
marci@301: 	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
alpar@774: 	  node_name[G.head(dfs)] << 
marci@301: 	  (dfs.isBNodeNewlyReached() ? ": is newly reached." : 
marci@301: 	   ": is not newly reached.");
marci@301:       } else { 
marci@301: 	cout << "invalid" << /*endl*/", " << 
marci@777: 	  node_name[dfs.tail()] << 
marci@301: 	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
marci@301: 	  
marci@301: 	  "invalid.";
marci@301:       }
marci@301:       cout << endl;
marci@301:     }
marci@301:   }
marci@301: 
marci@301: 
marci@301:   {
marci@312:     typedef RevGraphWrapper<const Graph> GW;
marci@301:     GW gw(G);
marci@301:     
marci@301:     EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);
marci@301:     
marci@301:     cout << "bfs and dfs iterator demo on the reversed directed graph" << endl;
alpar@774:     for(GW::NodeIt n(gw); n!=INVALID; ++n) { 
marci@317:       cout << node_name[GW::Node(n)] << ": ";
marci@301:       cout << "out edges: ";
alpar@774:       for(GW::OutEdgeIt e(gw, n); e!=INVALID; ++e) 
marci@304: 	cout << edge_name[e] << " ";
marci@301:       cout << "in edges: ";
alpar@774:       for(GW::InEdgeIt e(gw, n); e!=INVALID; ++e) 
marci@304: 	cout << edge_name[e] << " ";
marci@301:       cout << endl;
marci@301:     }
marci@301: 
marci@301:     cout << "bfs from t ..." << endl;
marci@360:     BfsIterator< GW, GW::NodeMap<bool> > bfs(gw);
marci@301:     bfs.pushAndSetReached(t);
marci@301:     while (!bfs.finished()) {
marci@301:       //cout << "edge: ";
marci@777:       if (GW::Edge(bfs)!=INVALID) {
marci@777: 	cout << edge_name[GW::Edge(bfs)] << /*endl*/", " << 
alpar@774: 	  node_name[gw.tail(bfs)] << 
marci@301: 	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
alpar@774: 	  node_name[gw.head(bfs)] << 
marci@301: 	  (bfs.isBNodeNewlyReached() ? ": is newly reached." : 
marci@301: 	   ": is not newly reached.");
marci@301:       } else { 
marci@301: 	cout << "invalid" << /*endl*/", " << 
marci@777: 	  node_name[bfs.tail()] << 
marci@301: 	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
marci@301: 	  
marci@301: 	  "invalid.";
marci@301:       }
marci@301:       cout << endl;
marci@301:       ++bfs;
marci@301:     }
marci@301: 
marci@301:     cout << "    /-->    ------------->            "<< endl;
marci@301:     cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;
marci@301:     cout << "  / |          |    /  /->     \\     "<< endl;
marci@301:     cout << " /  |          |   /  |    ^    \\  "<< endl;
marci@301:     cout << "s   |          |  /   |    |     \\->  t "<< endl;
marci@301:     cout << " \\  |          | /    |    |     /->  "<< endl;
marci@301:     cout << "  \\ |       --/ /     |    |    /     "<< endl;
marci@301:     cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;
marci@301:     cout << "    \\-->    ------------->         "<< endl;
marci@301:     
marci@301:     cout << "dfs from t ..." << endl;
marci@360:     DfsIterator< GW, GW::NodeMap<bool> > dfs(gw);
marci@301:     dfs.pushAndSetReached(t);
marci@301:     while (!dfs.finished()) {
marci@301:       ++dfs;
marci@301:       //cout << "edge: ";
marci@777:       if (GW::Edge(dfs)!=INVALID) {
marci@777: 	cout << edge_name[GW::Edge(dfs)] << /*endl*/", " << 
alpar@774: 	  node_name[gw.tail(dfs)] << 
marci@301: 	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
alpar@774: 	  node_name[gw.head(dfs)] << 
marci@301: 	  (dfs.isBNodeNewlyReached() ? ": is newly reached." : 
marci@301: 	   ": is not newly reached.");
marci@301:       } else { 
marci@301: 	cout << "invalid" << /*endl*/", " << 
marci@777: 	  node_name[dfs.tail()] << 
marci@301: 	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
marci@301: 	  
marci@301: 	  "invalid.";
marci@301:       }
marci@301:       cout << endl;
marci@301:     }
marci@301:   }
marci@301: 
alpar@774: //   {
alpar@774: //     typedef UndirGraphWrapper<const Graph> GW;
alpar@774: //     GW gw(G);
alpar@774:     
alpar@774: //     EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);
alpar@774:     
alpar@774: //     cout << "bfs and dfs iterator demo on the undirected graph" << endl;
alpar@774: //     for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) { 
alpar@774: //       cout << node_name[GW::Node(n)] << ": ";
alpar@774: //       cout << "out edges: ";
alpar@774: //       for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e)) 
alpar@774: // 	cout << edge_name[e] << " ";
alpar@774: //       cout << "in edges: ";
alpar@774: //       for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e)) 
alpar@774: // 	cout << edge_name[e] << " ";
alpar@774: //       cout << endl;
alpar@774: //     }
alpar@774: // //     for(GW::EdgeIt e=gw.first<GW::EdgeIt>(); gw.valid(e); gw.next(e)) { 
alpar@774: // //       cout << edge_name.get(e) << " ";
alpar@774: // //     }
alpar@774: // //     cout << endl;
alpar@774: 
alpar@774: //     cout << "bfs from t ..." << endl;
alpar@774: //     BfsIterator< GW, GW::NodeMap<bool> > bfs(gw);
alpar@774: //     bfs.pushAndSetReached(t);
alpar@774: //     while (!bfs.finished()) {
alpar@774: //       //cout << "edge: ";
alpar@774: //       if (gw.valid(GW::OutEdgeIt(bfs))) {
alpar@774: // 	cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " << 
alpar@774: // 	  node_name[gw.aNode(bfs)] << 
alpar@774: // 	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
alpar@774: // 	  node_name[gw.bNode(bfs)] << 
alpar@774: // 	  (bfs.isBNodeNewlyReached() ? ": is newly reached." : 
alpar@774: // 	   ": is not newly reached.");
alpar@774: //       } else { 
alpar@774: // 	cout << "invalid" << /*endl*/", " << 
alpar@774: // 	  node_name[bfs.aNode()] << 
alpar@774: // 	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
alpar@774: 	  
alpar@774: // 	  "invalid.";
alpar@774: //       }
alpar@774: //       cout << endl;
alpar@774: //       ++bfs;
alpar@774: //     }
alpar@774: 
alpar@774: //     cout << "    /-->    ------------->            "<< endl;
alpar@774: //     cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;
alpar@774: //     cout << "  / |          |    /  /->     \\     "<< endl;
alpar@774: //     cout << " /  |          |   /  |    ^    \\  "<< endl;
alpar@774: //     cout << "s   |          |  /   |    |     \\->  t "<< endl;
alpar@774: //     cout << " \\  |          | /    |    |     /->  "<< endl;
alpar@774: //     cout << "  \\ |       --/ /     |    |    /     "<< endl;
alpar@774: //     cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;
alpar@774: //     cout << "    \\-->    ------------->         "<< endl;
alpar@774:     
alpar@774: //     cout << "dfs from t ..." << endl;
alpar@774: //     DfsIterator< GW, GW::NodeMap<bool> > dfs(gw);
alpar@774: //     dfs.pushAndSetReached(t);
alpar@774: //     while (!dfs.finished()) {
alpar@774: //       ++dfs;
alpar@774: //       //cout << "edge: ";
alpar@774: //       if (gw.valid(GW::OutEdgeIt(dfs))) {
alpar@774: // 	cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " << 
alpar@774: // 	  node_name[gw.aNode(dfs)] << 
alpar@774: // 	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
alpar@774: // 	  node_name[gw.bNode(dfs)] << 
alpar@774: // 	  (dfs.isBNodeNewlyReached() ? ": is newly reached." : 
alpar@774: // 	   ": is not newly reached.");
alpar@774: //       } else { 
alpar@774: // 	cout << "invalid" << /*endl*/", " << 
alpar@774: // 	  node_name[dfs.aNode()] << 
alpar@774: // 	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
alpar@774: 	  
alpar@774: // 	  "invalid.";
alpar@774: //       }
alpar@774: //       cout << endl;
alpar@774: //     }
alpar@774: //   }
alpar@774: 
alpar@774: 
alpar@774: 
marci@301:   {
alpar@774:     typedef BidirGraphWrapper<const Graph> GW;
marci@301:     GW gw(G);
marci@301:     
marci@301:     EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);
marci@301:     
alpar@774:     cout << "bfs and dfs iterator demo on the bidirected graph" << endl;
alpar@774: //     for(GW::EdgeIt e(gw); e!=INVALID; ++e) {
alpar@774: //       cout << node_name[gw.tail(e)] << "->" << node_name[gw.head(e)] << " ";
alpar@774: //     } 
alpar@774:     for(GW::NodeIt n(gw); n!=INVALID; ++n) { 
marci@317:       cout << node_name[GW::Node(n)] << ": ";
marci@301:       cout << "out edges: ";
alpar@774:       for(GW::OutEdgeIt e(gw, n); e!=INVALID; ++e) 
marci@304: 	cout << edge_name[e] << " ";
marci@301:       cout << "in edges: ";
alpar@774:       for(GW::InEdgeIt e(gw, n); e!=INVALID; ++e) 
marci@304: 	cout << edge_name[e] << " ";
marci@301:       cout << endl;
marci@301:     }
marci@301: //     for(GW::EdgeIt e=gw.first<GW::EdgeIt>(); gw.valid(e); gw.next(e)) { 
marci@301: //       cout << edge_name.get(e) << " ";
marci@301: //     }
marci@301: //     cout << endl;
marci@301: 
marci@301:     cout << "bfs from t ..." << endl;
marci@360:     BfsIterator< GW, GW::NodeMap<bool> > bfs(gw);
marci@301:     bfs.pushAndSetReached(t);
marci@301:     while (!bfs.finished()) {
marci@301:       //cout << "edge: ";
marci@777:       if (GW::Edge(bfs)!=INVALID) {
marci@777: 	cout << edge_name[GW::Edge(bfs)] << /*endl*/", " << 
alpar@774: 	  node_name[gw.tail(bfs)] << 
marci@301: 	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
alpar@774: 	  node_name[gw.head(bfs)] << 
marci@301: 	  (bfs.isBNodeNewlyReached() ? ": is newly reached." : 
marci@301: 	   ": is not newly reached.");
marci@301:       } else { 
marci@301: 	cout << "invalid" << /*endl*/", " << 
marci@777: 	  node_name[bfs.tail()] << 
marci@301: 	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
marci@301: 	  
marci@301: 	  "invalid.";
marci@301:       }
marci@301:       cout << endl;
marci@301:       ++bfs;
marci@301:     }
marci@301: 
marci@301:     cout << "    /-->    ------------->            "<< endl;
marci@301:     cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;
marci@301:     cout << "  / |          |    /  /->     \\     "<< endl;
marci@301:     cout << " /  |          |   /  |    ^    \\  "<< endl;
marci@301:     cout << "s   |          |  /   |    |     \\->  t "<< endl;
marci@301:     cout << " \\  |          | /    |    |     /->  "<< endl;
marci@301:     cout << "  \\ |       --/ /     |    |    /     "<< endl;
marci@301:     cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;
marci@301:     cout << "    \\-->    ------------->         "<< endl;
marci@301:     
marci@301:     cout << "dfs from t ..." << endl;
marci@360:     DfsIterator< GW, GW::NodeMap<bool> > dfs(gw);
marci@301:     dfs.pushAndSetReached(t);
marci@301:     while (!dfs.finished()) {
marci@301:       ++dfs;
marci@301:       //cout << "edge: ";
marci@777:       if (GW::Edge(dfs)!=INVALID) {
marci@777: 	cout << edge_name[GW::Edge(dfs)] << /*endl*/", " << 
alpar@774: 	  node_name[gw.tail(dfs)] << 
marci@301: 	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
alpar@774: 	  node_name[gw.head(dfs)] << 
marci@301: 	  (dfs.isBNodeNewlyReached() ? ": is newly reached." : 
marci@301: 	   ": is not newly reached.");
marci@301:       } else { 
marci@301: 	cout << "invalid" << /*endl*/", " << 
marci@777: 	  node_name[dfs.tail()] << 
marci@301: 	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
marci@301: 	  
marci@301: 	  "invalid.";
marci@301:       }
marci@301:       cout << endl;
marci@301:     }
marci@301:   }
marci@301: 
marci@301:   return 0;
marci@301: }