// -*- c++ -*-
#include <iostream>
#include <fstream>

//#include <sage_graph.h>
#include <lemon/smart_graph.h>
#include <lemon/list_graph.h>
#include <lemon/dimacs.h>
#include <lemon/time_measure.h>
//#include <lemon/for_each_macros.h>
#include <bfs_mm.h>
#include <lemon/bfs.h>

using namespace lemon;

using std::cout;
using std::endl;

int main() {
  //  typedef SageGraph Graph; 
  typedef SmartGraph Graph ;
  //typedef ListGraph Graph; 
  typedef Graph::Node Node;
  typedef Graph::NodeIt NodeIt;
  typedef Graph::Edge Edge;
  typedef Graph::EdgeIt EdgeIt;
  typedef Graph::OutEdgeIt OutEdgeIt;

  Graph g;
  readDimacs(std::cin, g);
  NodeIt s(g);

  cout << g.nodeNum() << endl;
  cout << g.edgeNum() << endl;

  Graph::NodeMap<Edge> pred(g);
  cout << "iteration time of bfs written by hand..." << endl;
  Timer ts;
  ts.reset();
  for (int i=0; i<100; ++i)
  {
    Graph::NodeMap<bool> reached(g);
    reached.set(s, true);
    pred.set(s, INVALID);
    std::queue<Node> bfs_queue;
    bfs_queue.push(s);
    while (!bfs_queue.empty()) {
      Node v=bfs_queue.front();	
      bfs_queue.pop();
      for(OutEdgeIt e(g,v); e!=INVALID; ++e) {
	Node w=g.head(e);
	if (!reached[w]) {
	  bfs_queue.push(w);
	  reached.set(w, true);
	  pred.set(w, e);
	}
      }
    }
  }
  std::cout << ts << std::endl;

  cout << "iteration time with bfs iterator..." << endl;
  ts.reset();      
  for (int i=0; i<100; ++i)
  {
    Graph::NodeMap<bool> reached(g);
    marci::BfsIterator< Graph, Graph::NodeMap<bool> > bfs(g, reached);
    bfs.pushAndSetReached(s);
    pred.set(s, INVALID);
    while (!bfs.finished()) { 
      ++bfs; 
      if (Graph::Edge(bfs)!=INVALID && bfs.isBNodeNewlyReached()) 
	pred.set(bfs.head(), Graph::Edge(bfs));
    }
  }
  std::cout << ts << std::endl;

  cout << "iteration time with bfs aplar..." << endl;
  ts.reset();      
  for (int i=0; i<100; ++i)
  {
    Bfs<Graph> bfs(g);
    bfs.setPredMap(pred);
    bfs.run(s);
  }
  std::cout << ts << std::endl;


  return 0;
}