lemon-0.x: src/work/jacint/dijkstra.cc@7b97540cd743

     1 #include <iostream>

     2 #include <fstream>

     4 #include <smart_graph.h>

     5 #include <list_graph.h>

     6 #include <dimacs.h>

     7 #include <dijkstra.h>

     8 #include <time_measure.h>

    10 #include <bin_heap.h>

    11 #include <fib_heap.h>

    13 using namespace hugo;

    15 int main(int, char **) {

    16   typedef SmartGraph::Node Node;

    17   typedef SmartGraph::NodeIt NodeIt;

    18   typedef SmartGraph::InEdgeIt InEdgeIt;

    20   SmartGraph G;

    21   Node s, t;

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

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

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

    27   double pre_time=currTime();

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

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

    30   dijkstra_test.run(s);

    31   double post_time=currTime();

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

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

    36   pre_time=currTime();

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

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

    39   dijkstra_test2.run(s);

    40   post_time=currTime();

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

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

    46   int hiba_fib=0;

    47   int hiba_bin=0;

    48   NodeIt u;

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

    50     InEdgeIt e;

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

    52       Node v=G.tail(e);

    53       if ( dijkstra_test.dist(u) - dijkstra_test.dist(v) > cap[e] )

    54 	{

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

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

    57 	    cap[e]<<std::endl;

    58 	  ++hiba_fib;

    59 	}

    60       if ( dijkstra_test2.dist(u) - dijkstra_test2.dist(v) > cap[e] )

    61 	{

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

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

    64 	    cap[e]<<std::endl;

    65 	  ++hiba_bin;

    66 	}

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

    68 	   dijkstra_test.dist(u) - dijkstra_test.dist(v) != cap[e] )

    69 	{

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

    71 	    dijkstra_test.dist(u) - dijkstra_test.dist(v)- cap[e]<<std::endl;

    72 	  ++hiba_fib;

    73 	}

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

    75 	   dijkstra_test2.dist(u) - dijkstra_test2.dist(v) != cap[e] )

    76 	{

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

    78 	    dijkstra_test2.dist(u) - dijkstra_test2.dist(v)- cap[e]<<std::endl;

    79 	  ++hiba_bin;

    80 	}

    81     }

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

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

    87  }

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

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

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

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

    98   return 0;

    99 }

author	marci
	Thu, 08 Apr 2004 12:03:49 +0000
changeset 315	7b97540cd743
parent 217	fc549fac0dd0
child 372	e6a156fc186d
permissions	-rw-r--r--