src/work/alpar/dijkstra/dijkstra.cc
author athos
Tue, 04 May 2004 12:00:13 +0000
changeset 523 4da6fb104664
parent 257 7f832b4e5391
permissions -rw-r--r--
Started.
     1 #include <iostream>
     2 #include <fstream>
     3 
     4 #include <smart_graph.h>
     5 #include <list_graph.h>
     6 #include <dimacs.h>
     7 #include <dijkstra.h>
     8 #include <time_measure.h>
     9 
    10 #include <bin_heap.h>
    11 #include <fib_heap.h>
    12 
    13 using namespace hugo;
    14 
    15 int main(int, char **) {
    16   typedef SmartGraph::Node Node;
    17   typedef SmartGraph::NodeIt NodeIt;
    18   typedef SmartGraph::InEdgeIt InEdgeIt; 
    19 
    20   SmartGraph G;
    21   Node s, t;
    22   SmartGraph::EdgeMap<int> cap(G);
    23   Timer tim;
    24   std::cout << "DIMACS load ..." << std::endl;
    25   readDimacsMaxFlow(std::cin, G, s, t, cap);
    26   std::cout << "               " << tim <<std::endl;
    27 
    28   std::cout << "dijkstra demo ..." << std::endl;
    29   
    30   //double pre_time=currTime();
    31   tim.reset();
    32 //   Dijkstra <SmartGraph,
    33 //     SmartGraph::EdgeMap<int>,
    34 //     FibHeap<SmartGraph::Node, int, SmartGraph::NodeMap<int> >
    35 //     > dijkstra_test(G, cap); 
    36   
    37   Dijkstra <SmartGraph, SmartGraph::EdgeMap<int>, FibHeap >
    38     dijkstra_test(G, cap); 
    39   
    40   dijkstra_test.run(s);
    41   //double post_time=currTime();
    42   
    43   std::cout << "running time with fib_heap: " 
    44     // << post_time-pre_time << " sec"
    45 	    << tim
    46 	    << std::endl; 
    47  
    48   //pre_time=currTime();
    49   tim.reset();
    50 //   Dijkstra < SmartGraph,
    51 //     SmartGraph::EdgeMap<int>,
    52 //     BinHeap<SmartGraph::Node, int, SmartGraph::NodeMap<int> > > 
    53 //     dijkstra_test2(G, cap);
    54   
    55   Dijkstra <SmartGraph, SmartGraph::EdgeMap<int>, BinHeap >
    56     dijkstra_test2(G, cap); 
    57   
    58   dijkstra_test2.run(s);
    59   //post_time=currTime();
    60   
    61   std::cout << "running time with bin_heap: " 
    62     //    << post_time-pre_time << " sec"
    63 	    << tim
    64 	    << std::endl; 
    65   
    66 
    67   int hiba_fib=0;
    68   int hiba_bin=0;
    69   NodeIt u;
    70   for ( G.first(u) ; G.valid(u); G.next(u) ) {
    71     InEdgeIt e;
    72     for ( G.first(e,u); G.valid(e); G.next(e) ) {
    73       Node v=G.tail(e);
    74       if ( dijkstra_test.dist(u) - dijkstra_test.dist(v) > cap[e] )
    75 	{
    76 	  std::cout<<"Hibas el a fibonaccis Dijkstraban: " 
    77 		   << dijkstra_test.dist(u) - dijkstra_test.dist(v) - 
    78 	    cap[e]<<std::endl;
    79 	  ++hiba_fib;
    80 	}
    81       if ( dijkstra_test2.dist(u) - dijkstra_test2.dist(v) > cap[e] )
    82 	{
    83 	  std::cout<<"Hibas el a binarisos Dijkstraban: " 
    84 		   << dijkstra_test2.dist(u) - dijkstra_test2.dist(v) - 
    85 	    cap[e]<<std::endl;
    86 	  ++hiba_bin;
    87 	}
    88       if ( e==dijkstra_test.pred(u) && 
    89 	   dijkstra_test.dist(u) - dijkstra_test.dist(v) != cap[e] )
    90 	{
    91 	  std::cout<<"Hibas fael a fibonaccis Dijkstraban: "<<
    92 	    dijkstra_test.dist(u) - dijkstra_test.dist(v)- cap[e]<<std::endl;
    93 	  ++hiba_fib;
    94 	}
    95       if ( e==dijkstra_test2.pred(u) && 
    96 	   dijkstra_test2.dist(u) - dijkstra_test2.dist(v) != cap[e] )
    97 	{
    98 	  std::cout<<"Hibas fael a binarisos Dijkstraban: "<<
    99 	    dijkstra_test2.dist(u) - dijkstra_test2.dist(v)- cap[e]<<std::endl;
   100 	  ++hiba_bin;
   101 	}
   102     }
   103  
   104     if ( dijkstra_test.dist(u) != dijkstra_test2.dist(u) ) 
   105       std::cout << "Nem egyezik meg a tavolsag!"<<std::endl;
   106 
   107 
   108  }
   109 
   110   std::cout << "Hibas elek szama a fibonaccis Dijkstraban: " 
   111 	    << hiba_fib << " a " << G.edgeNum() <<"-bol."<< std::endl;
   112   
   113   std::cout << "Hibas elek szama a binarisos Dijkstraban: " 
   114 	    << hiba_bin << " a " << G.edgeNum() <<"-bol."<< std::endl;
   115   
   116   return 0;
   117 }