alpar@222: #include <iostream>
alpar@222: #include <fstream>
alpar@222: 
alpar@222: #include <smart_graph.h>
alpar@222: #include <list_graph.h>
alpar@222: #include <dimacs.h>
alpar@222: #include <dijkstra.h>
alpar@222: #include <time_measure.h>
alpar@222: 
alpar@222: #include <bin_heap.hh>
alpar@222: #include <fib_heap.h>
alpar@222: 
alpar@222: using namespace hugo;
alpar@222: 
alpar@222: int main(int, char **) {
alpar@222:   typedef SmartGraph::Node Node;
alpar@222:   typedef SmartGraph::NodeIt NodeIt;
alpar@222:   typedef SmartGraph::InEdgeIt InEdgeIt; 
alpar@222: 
alpar@222:   SmartGraph G;
alpar@222:   Node s, t;
alpar@222:   SmartGraph::EdgeMap<int> cap(G);
alpar@222:   Timer tim;
alpar@222:   std::cout << "DIMACS load ..." << std::endl;
alpar@222:   readDimacsMaxFlow(std::cin, G, s, t, cap);
alpar@222:   std::cout << "               " << tim <<std::endl;
alpar@222: 
alpar@222:   std::cout << "dijkstra demo ..." << std::endl;
alpar@222:   
alpar@222:   //double pre_time=currTime();
alpar@222:   tim.reset();
alpar@222:   Dijkstra <SmartGraph,
alpar@222:     SmartGraph::EdgeMap<int>,
alpar@222:     FibHeap<SmartGraph::Node, int, SmartGraph::NodeMap<int> >
alpar@222:     > dijkstra_test(G, cap); 
alpar@222:   
alpar@222:   dijkstra_test.run(s);
alpar@222:   //double post_time=currTime();
alpar@222:   
alpar@222:   std::cout << "running time with fib_heap: " 
alpar@222:     // << post_time-pre_time << " sec"
alpar@222: 	    << tim
alpar@222: 	    << std::endl; 
alpar@222:  
alpar@222:   //pre_time=currTime();
alpar@222:   tim.reset();
alpar@222:   Dijkstra < SmartGraph,
alpar@222:     SmartGraph::EdgeMap<int>,
alpar@222:     BinHeap<SmartGraph::Node, int, SmartGraph::NodeMap<int> > > 
alpar@222:     dijkstra_test2(G, cap);
alpar@222:   
alpar@222:   dijkstra_test2.run(s);
alpar@222:   //post_time=currTime();
alpar@222:   
alpar@222:   std::cout << "running time with bin_heap: " 
alpar@222:     //    << post_time-pre_time << " sec"
alpar@222: 	    << tim
alpar@222: 	    << std::endl; 
alpar@222:   
alpar@222: 
alpar@222:   int hiba_fib=0;
alpar@222:   int hiba_bin=0;
alpar@222:   NodeIt u;
alpar@222:   for ( G.first(u) ; G.valid(u); G.next(u) ) {
alpar@222:     InEdgeIt e;
alpar@222:     for ( G.first(e,u); G.valid(e); G.next(e) ) {
alpar@222:       Node v=G.tail(e);
alpar@222:       if ( dijkstra_test.dist(u) - dijkstra_test.dist(v) > cap[e] )
alpar@222: 	{
alpar@222: 	  std::cout<<"Hibas el a fibonaccis Dijkstraban: " 
alpar@222: 		   << dijkstra_test.dist(u) - dijkstra_test.dist(v) - 
alpar@222: 	    cap[e]<<std::endl;
alpar@222: 	  ++hiba_fib;
alpar@222: 	}
alpar@222:       if ( dijkstra_test2.dist(u) - dijkstra_test2.dist(v) > cap[e] )
alpar@222: 	{
alpar@222: 	  std::cout<<"Hibas el a binarisos Dijkstraban: " 
alpar@222: 		   << dijkstra_test2.dist(u) - dijkstra_test2.dist(v) - 
alpar@222: 	    cap[e]<<std::endl;
alpar@222: 	  ++hiba_bin;
alpar@222: 	}
alpar@222:       if ( e==dijkstra_test.pred(u) && 
alpar@222: 	   dijkstra_test.dist(u) - dijkstra_test.dist(v) != cap[e] )
alpar@222: 	{
alpar@222: 	  std::cout<<"Hibas fael a fibonaccis Dijkstraban: "<<
alpar@222: 	    dijkstra_test.dist(u) - dijkstra_test.dist(v)- cap[e]<<std::endl;
alpar@222: 	  ++hiba_fib;
alpar@222: 	}
alpar@222:       if ( e==dijkstra_test2.pred(u) && 
alpar@222: 	   dijkstra_test2.dist(u) - dijkstra_test2.dist(v) != cap[e] )
alpar@222: 	{
alpar@222: 	  std::cout<<"Hibas fael a binarisos Dijkstraban: "<<
alpar@222: 	    dijkstra_test2.dist(u) - dijkstra_test2.dist(v)- cap[e]<<std::endl;
alpar@222: 	  ++hiba_bin;
alpar@222: 	}
alpar@222:     }
alpar@222:  
alpar@222:     if ( dijkstra_test.dist(u) != dijkstra_test2.dist(u) ) 
alpar@222:       std::cout << "Nem egyezik meg a tavolsag!"<<std::endl;
alpar@222: 
alpar@222: 
alpar@222:  }
alpar@222: 
alpar@222:   std::cout << "Hibas elek szama a fibonaccis Dijkstraban: " 
alpar@222: 	    << hiba_fib << " a " << G.edgeNum() <<"-bol."<< std::endl;
alpar@222:   
alpar@222:   std::cout << "Hibas elek szama a binarisos Dijkstraban: " 
alpar@222: 	    << hiba_bin << " a " << G.edgeNum() <<"-bol."<< std::endl;
alpar@222:   
alpar@222: 
alpar@222: 
alpar@222: 
alpar@222:   return 0;
alpar@222: }