marci@358: // -*- c++ -*-
marci@358: #include <iostream>
marci@358: #include <fstream>
marci@358: 
marci@944: //#include <sage_graph.h>
alpar@921: #include <lemon/smart_graph.h>
marci@944: #include <lemon/list_graph.h>
alpar@921: #include <lemon/dimacs.h>
alpar@921: #include <lemon/time_measure.h>
alpar@921: //#include <lemon/for_each_macros.h>
marci@944: #include <bfs_mm.h>
marci@944: #include <lemon/bfs.h>
marci@358: 
alpar@921: using namespace lemon;
marci@358: 
marci@773: using std::cout;
marci@773: using std::endl;
marci@773: 
marci@358: int main() {
marci@944:   //  typedef SageGraph Graph; 
marci@944:   typedef SmartGraph Graph ;
marci@944:   //typedef ListGraph Graph; 
marci@358:   typedef Graph::Node Node;
marci@358:   typedef Graph::NodeIt NodeIt;
marci@358:   typedef Graph::Edge Edge;
marci@358:   typedef Graph::EdgeIt EdgeIt;
marci@358:   typedef Graph::OutEdgeIt OutEdgeIt;
marci@358: 
marci@577:   Graph g;
marci@577:   readDimacs(std::cin, g);
marci@944:   NodeIt s(g);
marci@773: 
marci@773:   cout << g.nodeNum() << endl;
marci@773:   cout << g.edgeNum() << endl;
marci@577: 
marci@777:   Graph::NodeMap<Edge> pred(g);
marci@773:   cout << "iteration time of bfs written by hand..." << endl;
marci@358:   Timer ts;
marci@944:   ts.reset();
marci@944:   for (int i=0; i<100; ++i)
marci@358:   {
marci@577:     Graph::NodeMap<bool> reached(g);
marci@358:     reached.set(s, true);
marci@358:     pred.set(s, INVALID);
marci@358:     std::queue<Node> bfs_queue;
marci@773:     bfs_queue.push(s);
marci@358:     while (!bfs_queue.empty()) {
marci@358:       Node v=bfs_queue.front();	
marci@358:       bfs_queue.pop();
marci@944:       for(OutEdgeIt e(g,v); e!=INVALID; ++e) {
marci@577: 	Node w=g.head(e);
marci@358: 	if (!reached[w]) {
marci@358: 	  bfs_queue.push(w);
marci@358: 	  reached.set(w, true);
marci@358: 	  pred.set(w, e);
marci@358: 	}
marci@358:       }
marci@358:     }
marci@358:   }
marci@944:   std::cout << ts << std::endl;
marci@358: 
marci@773:   cout << "iteration time with bfs iterator..." << endl;
marci@944:   ts.reset();      
marci@944:   for (int i=0; i<100; ++i)
marci@358:   {
marci@944:     Graph::NodeMap<bool> reached(g);
marci@944:     marci::BfsIterator< Graph, Graph::NodeMap<bool> > bfs(g, reached);
marci@358:     bfs.pushAndSetReached(s);
marci@358:     pred.set(s, INVALID);
marci@358:     while (!bfs.finished()) { 
marci@358:       ++bfs; 
marci@944:       if (Graph::Edge(bfs)!=INVALID && bfs.isBNodeNewlyReached()) 
marci@777: 	pred.set(bfs.head(), Graph::Edge(bfs));
marci@358:     }
marci@358:   }
marci@944:   std::cout << ts << std::endl;
marci@944: 
marci@944:   cout << "iteration time with bfs aplar..." << endl;
marci@944:   ts.reset();      
marci@944:   for (int i=0; i<100; ++i)
marci@944:   {
marci@944:     Bfs<Graph> bfs(g);
marci@944:     bfs.setPredMap(pred);
marci@944:     bfs.run(s);
marci@944:   }
marci@944:   std::cout << ts << std::endl;
marci@944: 
marci@358: 
marci@358:   return 0;
marci@358: }