lemon-0.x: src/work/alpar/dijkstra/dijkstra.cc@b63ea19e502e

     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   Timer tim;

    24   std::cout << "DIMACS load ..." << std::endl;

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

    26   std::cout << "               " << tim <<std::endl;

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

    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);

    37   Dijkstra <SmartGraph, SmartGraph::EdgeMap<int>, FibHeap >

    38     dijkstra_test(G, cap);

    40   dijkstra_test.run(s);

    41   //double post_time=currTime();

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

    44     // << post_time-pre_time << " sec"

    45 	    << tim

    46 	    << std::endl;

    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);

    55   Dijkstra <SmartGraph, SmartGraph::EdgeMap<int>, BinHeap >

    56     dijkstra_test2(G, cap);

    58   dijkstra_test2.run(s);

    59   //post_time=currTime();

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

    62     //    << post_time-pre_time << " sec"

    63 	    << tim

    64 	    << std::endl;

    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     }

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

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

   108  }

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

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

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

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

   116   return 0;

   117 }

author	alpar
	Sat, 17 Apr 2004 13:15:53 +0000
changeset 348	b63ea19e502e
parent 257	7f832b4e5391
permissions	-rw-r--r--