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