COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/alpar/dijkstra/dijkstra.cc @ 524:bd8109f8e2fa

Last change on this file since 524:bd8109f8e2fa was 258:94bafec4f56f, checked in by Mihaly Barasz, 20 years ago

bin_heap.hh atnevezese

File size: 3.1 KB
Line 
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
13using namespace hugo;
14
15int 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}
Note: See TracBrowser for help on using the repository browser.