marci@174: // -*- c++ -*- marci@75: #include marci@75: #include marci@75: #include marci@75: marci@174: #include marci@174: #include marci@174: #include marci@75: #include 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 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@174: string get(typename Graph::Edge 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@174: //typedef SmartGraph Graph; marci@174: typedef ListGraph Graph; marci@174: marci@174: typedef Graph::Node Node; marci@174: typedef Graph::Edge Edge; marci@174: //typedef Graph::NodeIt NodeIt; marci@174: //typedef Graph::EdgeIt EdgeIt; marci@174: //typedef Graph::OutEdgeIt OutEdgeIt; marci@174: //typedef Graph::InEdgeIt InEdgeIt; marci@174: //typedef Graph::SymEdgeIt SymEdgeIt; marci@75: marci@174: Graph G; marci@75: marci@174: Node s=G.addNode(); marci@174: Node v1=G.addNode(); marci@174: Node v2=G.addNode(); marci@174: Node v3=G.addNode(); marci@174: Node v4=G.addNode(); marci@174: Node t=G.addNode(); marci@75: marci@174: Graph::NodeMap 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@174: // typedef TrivGraphWrapper CGW; marci@158: // CGW wG(G); marci@158: marci@158: // cout << "bfs and dfs demo on the directed graph" << endl; marci@174: // for(CGW::NodeIt n=wG.first(); n.valid(); ++n) { marci@158: // cout << n << ": "; marci@158: // cout << "out edges: "; marci@158: // for(CGW::OutEdgeIt e=wG.first(n); e.valid(); ++e) marci@158: // cout << e << " "; marci@158: // cout << "in edges: "; marci@158: // for(CGW::InEdgeIt e=wG.first(n); e.valid(); ++e) marci@158: // cout << e << " "; marci@158: // cout << endl; marci@158: // } marci@158: marci@158: { marci@174: typedef TrivGraphWrapper GW; marci@158: GW wG(G); marci@158: marci@174: EdgeNameMap< GW, Graph::NodeMap > edge_name(wG, node_name); marci@158: marci@158: cout << "bfs and dfs iterator demo on the directed graph" << endl; marci@174: for(GW::NodeIt n=wG.first(); 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(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(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 > 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 > 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@174: typedef RevGraphWrapper GW; marci@158: GW wG(G); marci@158: marci@174: EdgeNameMap< GW, Graph::NodeMap > edge_name(wG, node_name); marci@158: marci@158: cout << "bfs and dfs iterator demo on the reversed directed graph" << endl; marci@174: for(GW::NodeIt n=wG.first(); 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(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(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 > 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 > 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@174: typedef UndirGraphWrapper GW; marci@158: GW wG(G); marci@158: marci@174: EdgeNameMap< GW, Graph::NodeMap > edge_name(wG, node_name); marci@158: marci@158: cout << "bfs and dfs iterator demo on the undirected graph" << endl; marci@174: for(GW::NodeIt n=wG.first(); 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(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(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 > 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 > 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: }