COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/jacint/dijkstra.cc @ 358:caf183989ec4

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

bin_heap.hh atnevezese

File size: 2.6 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  readDimacsMaxFlow(std::cin, G, s, t, cap);
24
25  std::cout << "dijkstra demo ..." << std::endl;
26 
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();
32   
33    std::cout << "running time with fib_heap: "
34            << post_time-pre_time << " sec"<< std::endl;
35 
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();
41 
42  std::cout << "running time with bin_heap: "
43            << post_time-pre_time << " sec"<< std::endl;
44 
45
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    }
82 
83    if ( dijkstra_test.dist(u) != dijkstra_test2.dist(u) )
84      std::cout << "Nem egyezik meg a tavolsag!"<<std::endl;
85
86
87 }
88
89  std::cout << "Hibas elek szama a fibonaccis Dijkstraban: "
90            << hiba_fib << " a " << G.edgeNum() <<"-bol."<< std::endl;
91 
92  std::cout << "Hibas elek szama a binarisos Dijkstraban: "
93            << hiba_bin << " a " << G.edgeNum() <<"-bol."<< std::endl;
94 
95
96
97
98  return 0;
99}
Note: See TracBrowser for help on using the repository browser.