marci@45: #include <iostream> marci@45: #include <vector> marci@45: #include <string> marci@45: marci@45: #include <list_graph.hh> marci@45: #include <bfs_iterator.hh> marci@45: alpar@107: using namespace hugo; marci@45: marci@45: int main (int, char*[]) marci@45: { marci@45: typedef ListGraph::NodeIt NodeIt; marci@45: typedef ListGraph::EdgeIt EdgeIt; marci@45: typedef ListGraph::EachNodeIt EachNodeIt; marci@45: typedef ListGraph::EachEdgeIt EachEdgeIt; marci@45: typedef ListGraph::OutEdgeIt OutEdgeIt; marci@45: typedef ListGraph::InEdgeIt InEdgeIt; marci@45: typedef ListGraph::SymEdgeIt SymEdgeIt; marci@45: marci@45: ListGraph G; marci@45: marci@45: NodeIt s=G.addNode(); marci@45: NodeIt v1=G.addNode(); marci@45: NodeIt v2=G.addNode(); marci@45: NodeIt v3=G.addNode(); marci@45: NodeIt v4=G.addNode(); marci@45: NodeIt t=G.addNode(); marci@45: marci@45: G.addEdge(s, v1); marci@45: G.addEdge(s, v2); marci@45: G.addEdge(v1, v2); marci@45: G.addEdge(v2, v1); marci@45: G.addEdge(v1, v3); marci@45: G.addEdge(v3, v2); marci@45: G.addEdge(v2, v4); marci@45: G.addEdge(v4, v3); marci@45: G.addEdge(v3, t); marci@45: G.addEdge(v4, t); marci@45: marci@45: std::cout << "bfs and dfs demo on the directed graph" << std::endl; marci@45: for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) { marci@45: std::cout << i << ": "; marci@45: std::cout << "out edges: "; marci@45: for(OutEdgeIt j=G.first<OutEdgeIt>(i); j.valid(); ++j) marci@45: std::cout << j << " "; marci@45: std::cout << "in edges: "; marci@45: for(InEdgeIt j=G.first<InEdgeIt>(i); j.valid(); ++j) marci@45: std::cout << j << " "; marci@45: std::cout << std::endl; marci@45: } marci@45: marci@45: //std::cout << std::endl; marci@45: //EachNodeIt u1=G.first<EachNodeIt>(); marci@45: //EachEdgeIt u=G.first<EachEdgeIt>(); marci@45: //OutEdgeIt u=G.first<OutEdgeIt>(s); marci@45: //InEdgeIt u=G.first<InEdgeIt>(s); marci@45: //SymEdgeIt u=G.first<SymEdgeIt>(s); marci@45: //OutEdgeIt u=G.first<OutEdgeIt>(s); marci@45: //EachNodeIt u=G.first<EachNodeIt>(); marci@45: //EachEdgeIt u=G.first<EachEdgeIt>(); marci@45: //OutEdgeIt u=G.first<OutEdgeIt>(s); marci@45: //InEdgeIt u=G.first<InEdgeIt>(s); marci@45: //SymEdgeIt u=G.first<SymEdgeIt>(s); marci@45: //u=G.first(s); marci@45: //u=G.first_ize(s, OutEdgeIt()); marci@45: //std::cout << "ize " << u << std::endl; marci@45: marci@45: /* marci@45: { marci@45: std::cout << "iterator bfs demo..." << std::endl; marci@45: NodePropertyVector<ListGraph, bool> reached(G, false); marci@45: reached.set(s, true); marci@45: std::queue<ListGraph::OutEdgeIt> bfs_queue; marci@45: bfs_queue.push(G.firstOutEdge(G.firstNode())); marci@45: BfsIterator< ListGraph, ListGraph::OutEdgeIt, NodePropertyVector<ListGraph, bool> > bfs(G, bfs_queue, reached); marci@45: for ( ; !bfs.finished(); ++bfs) { marci@45: if (OutEdgeIt(bfs).valid()) { marci@45: std::cout << "OutEdgeIt: " << bfs; marci@45: std::cout << " aNode: " << G.aNode(bfs); marci@45: std::cout << " bNode: " << G.bNode(bfs) << " "; marci@45: } else { marci@45: std::cout << "OutEdgeIt: " << "invalid"; marci@45: std::cout << " aNode: " << G.aNode(bfs); marci@45: std::cout << " bNode: " << "invalid" << " "; marci@45: } marci@45: if (bfs.bNodeIsNewlyReached()) { marci@45: std::cout << "bNodeIsNewlyReached "; marci@45: } else { marci@45: std::cout << "bNodeIsNotNewlyReached "; marci@45: } marci@45: if (bfs.aNodeIsExamined()) { marci@45: std::cout << "aNodeIsExamined "; marci@45: } else { marci@45: std::cout << "aNodeIsNotExamined "; marci@45: } marci@45: std::cout<<std::endl; marci@45: } marci@45: } marci@45: marci@45: { marci@45: std::cout << "iterator dfs demo..." << std::endl; marci@45: NodePropertyVector<ListGraph, bool> reached(G, false); marci@45: reached.set(s, true); marci@45: std::stack<ListGraph::OutEdgeIt> dfs_stack; marci@45: dfs_stack.push(G.firstOutEdge(G.firstNode())); marci@45: DfsIterator< ListGraph, ListGraph::OutEdgeIt, NodePropertyVector<ListGraph, bool> > dfs(G, dfs_stack, reached); marci@45: for(; !dfs.finished(); ++dfs) { marci@45: if (OutEdgeIt(dfs).valid()) { marci@45: std::cout << "OutEdgeIt: " << dfs; marci@45: std::cout << " aNode: " << G.aNode(dfs); marci@45: std::cout << " bNode: " << G.bNode(dfs) << " "; marci@45: } else { marci@45: std::cout << "OutEdgeIt: " << "invalid"; marci@45: std::cout << " aNode: " << G.aNode(dfs); marci@45: std::cout << " bNode: " << "invalid" << " "; marci@45: } marci@45: if (dfs.bNodeIsNewlyReached()) { marci@45: std::cout << "bNodeIsNewlyReached "; marci@45: } else { marci@45: std::cout << "bNodeIsNotNewlyReached "; marci@45: } marci@45: if (dfs.aNodeIsLeaved()) { marci@45: std::cout << "aNodeIsLeaved "; marci@45: } else { marci@45: std::cout << "aNodeIsNotLeaved "; marci@45: } marci@45: std::cout<<std::endl; marci@45: } marci@45: if (OutEdgeIt(dfs).valid()) { marci@45: std::cout << "OutEdgeIt: " << dfs; marci@45: std::cout << " aNode: " << G.aNode(dfs); marci@45: std::cout << " bNode: " << G.bNode(dfs) << " "; marci@45: } else { marci@45: std::cout << "OutEdgeIt: " << "invalid"; marci@45: std::cout << " aNode: " << G.aNode(dfs); marci@45: std::cout << " bNode: " << "invalid" << " "; marci@45: } marci@45: if (dfs.bNodeIsNewlyReached()) { marci@45: std::cout << "bNodeIsNewlyReached "; marci@45: } else { marci@45: std::cout << "bNodeIsNotNewlyReached "; marci@45: } marci@45: if (dfs.aNodeIsLeaved()) { marci@45: std::cout << "aNodeIsLeaved "; marci@45: } else { marci@45: std::cout << "aNodeIsNotLeaved "; marci@45: } marci@45: std::cout<<std::endl; marci@45: } marci@45: */ marci@45: marci@45: { marci@45: std::cout << "iterator bfs demo 1 ..." << std::endl; marci@45: ListGraph::NodeMap<bool> reached(G, false); marci@45: reached.set(s, true); marci@45: std::queue<ListGraph::OutEdgeIt> bfs_queue; marci@45: bfs_queue.push(G.first<OutEdgeIt>(s)); marci@45: BfsIterator1< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > bfs(G, bfs_queue, reached); marci@45: while (!bfs.finished()) { marci@45: if (OutEdgeIt(bfs).valid()) { marci@45: std::cout << "OutEdgeIt: " << bfs; marci@45: std::cout << " aNode: " << G.aNode(bfs); marci@45: std::cout << " bNode: " << G.bNode(bfs) << " "; marci@45: } else { marci@45: std::cout << "OutEdgeIt: " << "invalid"; marci@45: std::cout << " aNode: " << G.aNode(bfs); marci@45: std::cout << " bNode: " << "invalid" << " "; marci@45: } marci@45: if (bfs.bNodeIsNewlyReached()) { marci@45: std::cout << "bNodeIsNewlyReached "; marci@45: } else { marci@45: std::cout << "bNodeIsNotNewlyReached "; marci@45: } marci@45: if (bfs.aNodeIsExamined()) { marci@45: std::cout << "aNodeIsExamined "; marci@45: } else { marci@45: std::cout << "aNodeIsNotExamined "; marci@45: } marci@45: std::cout<<std::endl; marci@45: bfs.next(); marci@45: } marci@45: } marci@45: marci@59: { marci@59: std::cout << "iterator bfs demo 2 ..." << std::endl; marci@59: //ListGraph::NodeMap<bool> reached(G, false); marci@59: //reached.set(s, true); marci@59: //std::queue<ListGraph::OutEdgeIt> bfs_queue; marci@59: //bfs_queue.push(G.first<OutEdgeIt>(s)); marci@59: BfsIterator2< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > bfs(G); marci@59: bfs.pushAndSetReached(s); marci@59: while (!bfs.finished()) { marci@59: if (OutEdgeIt(bfs).valid()) { marci@59: std::cout << "OutEdgeIt: " << bfs; marci@59: std::cout << " aNode: " << G.aNode(bfs); marci@59: std::cout << " bNode: " << G.bNode(bfs) << " "; marci@59: } else { marci@59: std::cout << "OutEdgeIt: " << "invalid"; marci@59: std::cout << " aNode: " << G.aNode(bfs); marci@59: std::cout << " bNode: " << "invalid" << " "; marci@59: } marci@59: if (bfs.isBNodeNewlyReached()) { marci@59: std::cout << "bNodeIsNewlyReached "; marci@59: } else { marci@59: std::cout << "bNodeIsNotNewlyReached "; marci@59: } marci@59: if (bfs.isANodeExamined()) { marci@59: std::cout << "aNodeIsExamined "; marci@59: } else { marci@59: std::cout << "aNodeIsNotExamined "; marci@59: } marci@59: std::cout<<std::endl; marci@59: ++bfs; marci@59: } marci@59: } marci@59: marci@59: marci@59: marci@45: marci@45: { marci@45: std::cout << "iterator dfs demo 1..." << std::endl; marci@45: ListGraph::NodeMap<bool> reached(G, false); marci@45: reached.set(s, true); marci@45: std::stack<ListGraph::OutEdgeIt> dfs_stack; marci@45: dfs_stack.push(G.first<OutEdgeIt>(s)); marci@45: DfsIterator1< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > dfs(G, dfs_stack, reached); marci@45: do { marci@45: dfs.next(); marci@45: if (OutEdgeIt(dfs).valid()) { marci@45: std::cout << "OutEdgeIt: " << dfs; marci@45: std::cout << " aNode: " << G.aNode(dfs); marci@45: std::cout << " bNode: " << G.bNode(dfs) << " "; marci@45: } else { marci@45: std::cout << "OutEdgeIt: " << "invalid"; marci@45: std::cout << " aNode: " << G.aNode(dfs); marci@45: std::cout << " bNode: " << "invalid" << " "; marci@45: } marci@45: if (dfs.bNodeIsNewlyReached()) { marci@45: std::cout << "bNodeIsNewlyReached "; marci@45: } else { marci@45: std::cout << "bNodeIsNotNewlyReached "; marci@45: } marci@45: if (dfs.aNodeIsLeaved()) { marci@45: std::cout << "aNodeIsLeaved "; marci@45: } else { marci@45: std::cout << "aNodeIsNotLeaved "; marci@45: } marci@45: std::cout<<std::endl; marci@45: } while (!dfs.finished()); marci@45: } marci@45: marci@45: marci@45: { marci@45: std::cout << "iterator bfs demo from node 5 with replacing \n OutEdgeIt by InEdgeIt ..." << std::endl; marci@45: ListGraph::NodeMap<bool> reached(G, false); marci@45: reached.set(t, true); marci@45: std::queue<ListGraph::InEdgeIt> bfs_queue; marci@45: bfs_queue.push(G.first<InEdgeIt>(t)); marci@45: BfsIterator1< ListGraph, ListGraph::InEdgeIt, ListGraph::NodeMap<bool> > bfs(G, bfs_queue, reached); marci@45: while (!bfs.finished()) { marci@45: if (InEdgeIt(bfs).valid()) { marci@45: std::cout << "InEdgeIt: " << bfs; marci@45: std::cout << " aNode: " << G.aNode(bfs); marci@45: std::cout << " bNode: " << G.bNode(bfs) << " "; marci@45: } else { marci@45: std::cout << "InEdgeIt: " << "invalid"; marci@45: std::cout << " aNode: " << G.aNode(bfs); marci@45: std::cout << " bNode: " << "invalid" << " "; marci@45: } marci@45: if (bfs.bNodeIsNewlyReached()) { marci@45: std::cout << "bNodeIsNewlyReached "; marci@45: } else { marci@45: std::cout << "bNodeIsNotNewlyReached "; marci@45: } marci@45: if (bfs.aNodeIsExamined()) { marci@45: std::cout << "aNodeIsExamined "; marci@45: } else { marci@45: std::cout << "aNodeIsNotExamined "; marci@45: } marci@45: std::cout<<std::endl; marci@45: bfs.next(); marci@45: } marci@45: } marci@45: marci@45: marci@45: { marci@45: std::cout << "the graph is considered as an undirected graph \n by replacing InEdgeIt by SymEdgeIt ..." << std::endl; marci@45: ListGraph::NodeMap<bool> reached(G, false); marci@45: reached.set(t, true); marci@45: std::queue<ListGraph::SymEdgeIt> bfs_queue; marci@45: bfs_queue.push(G.first<SymEdgeIt>(t)); marci@45: BfsIterator1< ListGraph, ListGraph::SymEdgeIt, ListGraph::NodeMap<bool> > bfs(G, bfs_queue, reached); marci@45: while (!bfs.finished()) { marci@45: if (SymEdgeIt(bfs).valid()) { marci@45: std::cout << "SymEdgeIt: " << bfs; marci@45: std::cout << " aNode: " << G.aNode(bfs); marci@45: std::cout << " bNode: " << G.bNode(bfs) << " "; marci@45: } else { marci@45: std::cout << "SymEdgeIt: " << "invalid"; marci@45: std::cout << " aNode: " << G.aNode(bfs); marci@45: std::cout << " bNode: " << "invalid" << " "; marci@45: } marci@45: if (bfs.bNodeIsNewlyReached()) { marci@45: std::cout << "bNodeIsNewlyReached "; marci@45: } else { marci@45: std::cout << "bNodeIsNotNewlyReached "; marci@45: } marci@45: if (bfs.aNodeIsExamined()) { marci@45: std::cout << "aNodeIsExamined "; marci@45: } else { marci@45: std::cout << "aNodeIsNotExamined "; marci@45: } marci@45: std::cout<<std::endl; marci@45: bfs.next(); marci@45: } marci@45: } marci@45: marci@45: return 0; marci@45: }