COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/alpar/dijkstra/dijkstra.cc @ 224:5bc1c83257f8

Last change on this file since 224:5bc1c83257f8 was 222:0c6bd3a98edf, checked in by Alpar Juttner, 20 years ago

Aprosagok...

File size: 2.9 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.hh>
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_test.run(s);
38  //double post_time=currTime();
39 
40  std::cout << "running time with fib_heap: "
41    // << post_time-pre_time << " sec"
42            << tim
43            << std::endl;
44 
45  //pre_time=currTime();
46  tim.reset();
47  Dijkstra < SmartGraph,
48    SmartGraph::EdgeMap<int>,
49    BinHeap<SmartGraph::Node, int, SmartGraph::NodeMap<int> > >
50    dijkstra_test2(G, cap);
51 
52  dijkstra_test2.run(s);
53  //post_time=currTime();
54 
55  std::cout << "running time with bin_heap: "
56    //    << post_time-pre_time << " sec"
57            << tim
58            << std::endl;
59 
60
61  int hiba_fib=0;
62  int hiba_bin=0;
63  NodeIt u;
64  for ( G.first(u) ; G.valid(u); G.next(u) ) {
65    InEdgeIt e;
66    for ( G.first(e,u); G.valid(e); G.next(e) ) {
67      Node v=G.tail(e);
68      if ( dijkstra_test.dist(u) - dijkstra_test.dist(v) > cap[e] )
69        {
70          std::cout<<"Hibas el a fibonaccis Dijkstraban: "
71                   << dijkstra_test.dist(u) - dijkstra_test.dist(v) -
72            cap[e]<<std::endl;
73          ++hiba_fib;
74        }
75      if ( dijkstra_test2.dist(u) - dijkstra_test2.dist(v) > cap[e] )
76        {
77          std::cout<<"Hibas el a binarisos Dijkstraban: "
78                   << dijkstra_test2.dist(u) - dijkstra_test2.dist(v) -
79            cap[e]<<std::endl;
80          ++hiba_bin;
81        }
82      if ( e==dijkstra_test.pred(u) &&
83           dijkstra_test.dist(u) - dijkstra_test.dist(v) != cap[e] )
84        {
85          std::cout<<"Hibas fael a fibonaccis Dijkstraban: "<<
86            dijkstra_test.dist(u) - dijkstra_test.dist(v)- cap[e]<<std::endl;
87          ++hiba_fib;
88        }
89      if ( e==dijkstra_test2.pred(u) &&
90           dijkstra_test2.dist(u) - dijkstra_test2.dist(v) != cap[e] )
91        {
92          std::cout<<"Hibas fael a binarisos Dijkstraban: "<<
93            dijkstra_test2.dist(u) - dijkstra_test2.dist(v)- cap[e]<<std::endl;
94          ++hiba_bin;
95        }
96    }
97 
98    if ( dijkstra_test.dist(u) != dijkstra_test2.dist(u) )
99      std::cout << "Nem egyezik meg a tavolsag!"<<std::endl;
100
101
102 }
103
104  std::cout << "Hibas elek szama a fibonaccis Dijkstraban: "
105            << hiba_fib << " a " << G.edgeNum() <<"-bol."<< std::endl;
106 
107  std::cout << "Hibas elek szama a binarisos Dijkstraban: "
108            << hiba_bin << " a " << G.edgeNum() <<"-bol."<< std::endl;
109 
110
111
112
113  return 0;
114}
Note: See TracBrowser for help on using the repository browser.