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@921: using namespace lemon;
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: }