marci@301: // -*- c++ -*- marci@301: #include marci@301: #include marci@301: #include marci@301: marci@301: #include marci@301: #include marci@301: #include marci@301: #include marci@301: marci@301: using namespace hugo; marci@301: using std::cout; marci@301: using std::endl; marci@301: using std::string; marci@301: marci@301: template 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: { marci@301: //typedef SmartGraph Graph; marci@301: typedef ListGraph 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 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: // typedef TrivGraphWrapper CGW; marci@301: // CGW gw(G); marci@301: marci@301: // cout << "bfs and dfs demo on the directed graph" << endl; marci@301: // for(CGW::NodeIt n=gw.first(); n.valid(); ++n) { marci@301: // cout << n << ": "; marci@301: // cout << "out edges: "; marci@301: // for(CGW::OutEdgeIt e=gw.first(n); e.valid(); ++e) marci@301: // cout << e << " "; marci@301: // cout << "in edges: "; marci@301: // for(CGW::InEdgeIt e=gw.first(n); e.valid(); ++e) marci@301: // cout << e << " "; marci@301: // cout << endl; marci@301: // } marci@301: marci@301: { marci@312: EdgeNameMap< Graph, Graph::NodeMap > edge_name(G, node_name); marci@301: marci@301: cout << "bfs and dfs iterator demo on the directed graph" << endl; marci@312: for(Graph::NodeIt n(G); G.valid(n); G.next(n)) { marci@304: cout << node_name[n] << ": "; marci@301: cout << "out edges: "; marci@312: for(Graph::OutEdgeIt e(G, n); G.valid(e); G.next(e)) marci@304: cout << edge_name[e] << " "; marci@301: cout << "in edges: "; marci@312: for(Graph::InEdgeIt e(G, n); G.valid(e); G.next(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 > bfs(G); marci@301: bfs.pushAndSetReached(s); marci@301: while (!bfs.finished()) { marci@301: //cout << "edge: "; marci@312: if (G.valid(bfs)) { marci@304: cout << edge_name[bfs] << /*endl*/", " << marci@312: node_name[G.aNode(bfs)] << marci@301: (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << marci@312: node_name[G.bNode(bfs)] << marci@301: (bfs.isBNodeNewlyReached() ? ": is newly reached." : marci@301: ": is not newly reached."); marci@301: } else { marci@301: cout << "invalid" << /*endl*/", " << marci@304: node_name[bfs.aNode()] << 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 > dfs(G); marci@301: dfs.pushAndSetReached(s); marci@301: while (!dfs.finished()) { marci@301: ++dfs; marci@301: //cout << "edge: "; marci@312: if (G.valid(dfs)) { marci@304: cout << edge_name[dfs] << /*endl*/", " << marci@312: node_name[G.aNode(dfs)] << marci@301: (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << marci@312: node_name[G.bNode(dfs)] << marci@301: (dfs.isBNodeNewlyReached() ? ": is newly reached." : marci@301: ": is not newly reached."); marci@301: } else { marci@301: cout << "invalid" << /*endl*/", " << marci@304: node_name[dfs.aNode()] << 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 GW; marci@301: GW gw(G); marci@301: marci@301: EdgeNameMap< GW, Graph::NodeMap > edge_name(gw, node_name); marci@301: marci@301: cout << "bfs and dfs iterator demo on the reversed directed graph" << endl; marci@301: for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) { marci@317: cout << node_name[GW::Node(n)] << ": "; marci@301: cout << "out edges: "; marci@301: for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e)) marci@304: cout << edge_name[e] << " "; marci@301: cout << "in edges: "; marci@301: for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(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 > bfs(gw); marci@301: bfs.pushAndSetReached(t); marci@301: while (!bfs.finished()) { marci@301: //cout << "edge: "; marci@317: if (gw.valid(GW::OutEdgeIt(bfs))) { marci@317: cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " << marci@304: node_name[gw.aNode(bfs)] << marci@301: (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << marci@304: node_name[gw.bNode(bfs)] << marci@301: (bfs.isBNodeNewlyReached() ? ": is newly reached." : marci@301: ": is not newly reached."); marci@301: } else { marci@301: cout << "invalid" << /*endl*/", " << marci@304: node_name[bfs.aNode()] << 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 > dfs(gw); marci@301: dfs.pushAndSetReached(t); marci@301: while (!dfs.finished()) { marci@301: ++dfs; marci@301: //cout << "edge: "; marci@317: if (gw.valid(GW::OutEdgeIt(dfs))) { marci@317: cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " << marci@304: node_name[gw.aNode(dfs)] << marci@301: (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << marci@304: node_name[gw.bNode(dfs)] << marci@301: (dfs.isBNodeNewlyReached() ? ": is newly reached." : marci@301: ": is not newly reached."); marci@301: } else { marci@301: cout << "invalid" << /*endl*/", " << marci@304: node_name[dfs.aNode()] << 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@312: typedef UndirGraphWrapper GW; marci@301: GW gw(G); marci@301: marci@301: EdgeNameMap< GW, Graph::NodeMap > edge_name(gw, node_name); marci@301: marci@301: cout << "bfs and dfs iterator demo on the undirected graph" << endl; marci@301: for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) { marci@317: cout << node_name[GW::Node(n)] << ": "; marci@301: cout << "out edges: "; marci@301: for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e)) marci@304: cout << edge_name[e] << " "; marci@301: cout << "in edges: "; marci@301: for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e)) marci@304: cout << edge_name[e] << " "; marci@301: cout << endl; marci@301: } marci@301: // for(GW::EdgeIt e=gw.first(); 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 > bfs(gw); marci@301: bfs.pushAndSetReached(t); marci@301: while (!bfs.finished()) { marci@301: //cout << "edge: "; marci@301: if (gw.valid(GW::OutEdgeIt(bfs))) { marci@304: cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " << marci@304: node_name[gw.aNode(bfs)] << marci@301: (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << marci@304: node_name[gw.bNode(bfs)] << marci@301: (bfs.isBNodeNewlyReached() ? ": is newly reached." : marci@301: ": is not newly reached."); marci@301: } else { marci@301: cout << "invalid" << /*endl*/", " << marci@304: node_name[bfs.aNode()] << 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 > dfs(gw); marci@301: dfs.pushAndSetReached(t); marci@301: while (!dfs.finished()) { marci@301: ++dfs; marci@301: //cout << "edge: "; marci@301: if (gw.valid(GW::OutEdgeIt(dfs))) { marci@304: cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " << marci@304: node_name[gw.aNode(dfs)] << marci@301: (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << marci@304: node_name[gw.bNode(dfs)] << marci@301: (dfs.isBNodeNewlyReached() ? ": is newly reached." : marci@301: ": is not newly reached."); marci@301: } else { marci@301: cout << "invalid" << /*endl*/", " << marci@304: node_name[dfs.aNode()] << 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: }