marci@181: // -*- c++ -*- marci@181: #include marci@181: #include marci@181: #include marci@181: marci@181: #include marci@181: marci@181: #include marci@181: #include marci@181: #include marci@181: #include marci@189: #include marci@181: alpar@921: using namespace lemon; marci@181: using std::cout; marci@181: using std::endl; marci@181: using std::string; marci@181: marci@181: template 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 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 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 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(); n.valid(); ++n) { marci@181: // cout << n << ": "; marci@181: // cout << "out edges: "; marci@181: // for(CGW::OutEdgeIt e=wG.first(n); e.valid(); ++e) marci@181: // cout << e << " "; marci@181: // cout << "in edges: "; marci@181: // for(CGW::InEdgeIt e=wG.first(n); e.valid(); ++e) marci@181: // cout << e << " "; marci@181: // cout << endl; marci@181: // } marci@181: marci@181: { marci@181: typedef TrivGraphWrapper GW; marci@181: GW wG(G); marci@181: marci@181: EdgeNameMap< GW, Graph::NodeMap > 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(); 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(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(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 > 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 > 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 GW; marci@181: GW wG(G); marci@181: marci@181: EdgeNameMap< GW, Graph::NodeMap > 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(); 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(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(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 > 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 > 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 GW; marci@181: GW wG(G); marci@181: marci@181: EdgeNameMap< GW, Graph::NodeMap > 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(); 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(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(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 > 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 > 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: }