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