#include <iostream>

#include <fstream>

#include <smart_graph.h>

#include <list_graph.h>

#include <dimacs.h>

#include <dijkstra.h>

#include <time_measure.h>

#include <bin_heap.hh>

#include <fib_heap.h>

using namespace hugo;

int main(int, char **) {

  typedef SmartGraph::Node Node;

  typedef SmartGraph::NodeIt NodeIt;

  typedef SmartGraph::InEdgeIt InEdgeIt; 

  SmartGraph G;

  Node s, t;

  SmartGraph::EdgeMap<int> cap(G);

  readDimacsMaxFlow(std::cin, G, s, t, cap);

  std::cout << "dijkstra demo ..." << std::endl;

  double pre_time=currTime();

    Dijkstra<SmartGraph, int, FibHeap<SmartGraph::Node, int, 

    SmartGraph::NodeMap<int> > > dijkstra_test(G, cap); 

    dijkstra_test.run(s);

  double post_time=currTime();

  std::cout << "running time with fib_heap: " 

	    << post_time-pre_time << " sec"<< std::endl; 

  pre_time=currTime();

  Dijkstra<SmartGraph, int, BinHeap<SmartGraph::Node, int, 

    SmartGraph::NodeMap<int> > > dijkstra_test2(G, cap);

  dijkstra_test2.run(s);

  post_time=currTime();

  std::cout << "running time with bin_heap: " 

	    << post_time-pre_time << " sec"<< std::endl; 

  int hiba_fib=0;

  int hiba_bin=0;

  NodeIt u;

  for ( G.first(u) ; G.valid(u); G.next(u) ) {

    InEdgeIt e;

    for ( G.first(e,u); G.valid(e); G.next(e) ) {

      Node v=G.tail(e);

      if ( dijkstra_test.dist(u) - dijkstra_test.dist(v) > cap.get(e) )

	{

	  std::cout<<"Hibas el a fibonaccis Dijkstraban: " 

		   << dijkstra_test.dist(u) - dijkstra_test.dist(v) - 

	    cap.get(e)<<std::endl;

	  ++hiba_fib;

	}

      if ( dijkstra_test2.dist(u) - dijkstra_test2.dist(v) > cap.get(e) )

	{

	  std::cout<<"Hibas el a binarisos Dijkstraban: " 

		   << dijkstra_test2.dist(u) - dijkstra_test2.dist(v) - 

	    cap.get(e)<<std::endl;

	  ++hiba_bin;

	}

      if ( e==dijkstra_test.pred(u) && 

	   dijkstra_test.dist(u) - dijkstra_test.dist(v) != cap.get(e) )

	{

	  std::cout<<"Hibas fael a fibonaccis Dijkstraban: "<<

	    dijkstra_test.dist(u) - dijkstra_test.dist(v)- cap.get(e)<<std::endl;

	  ++hiba_fib;

	}

      if ( e==dijkstra_test2.pred(u) && 

	   dijkstra_test2.dist(u) - dijkstra_test2.dist(v) != cap.get(e) )

	{

	  std::cout<<"Hibas fael a binarisos Dijkstraban: "<<

	    dijkstra_test2.dist(u) - dijkstra_test2.dist(v)- cap.get(e)<<std::endl;

	  ++hiba_bin;

	}

    }

    if ( dijkstra_test.dist(u) != dijkstra_test2.dist(u) ) 

      std::cout << "Nem egyezik meg a tavolsag!"<<std::endl;

 }

  std::cout << "Hibas elek szama a fibonaccis Dijkstraban: " 

	    << hiba_fib << " a " << G.edgeNum() <<"-bol."<< std::endl;

  std::cout << "Hibas elek szama a binarisos Dijkstraban: " 

	    << hiba_bin << " a " << G.edgeNum() <<"-bol."<< std::endl;

  return 0;

}