|
alpar@222
|
1 |
#include <iostream>
|
|
alpar@222
|
2 |
#include <fstream>
|
|
alpar@222
|
3 |
|
|
alpar@222
|
4 |
#include <smart_graph.h>
|
|
alpar@222
|
5 |
#include <list_graph.h>
|
|
alpar@222
|
6 |
#include <dimacs.h>
|
|
alpar@222
|
7 |
#include <dijkstra.h>
|
|
alpar@222
|
8 |
#include <time_measure.h>
|
|
alpar@222
|
9 |
|
|
alpar@222
|
10 |
#include <bin_heap.hh>
|
|
alpar@222
|
11 |
#include <fib_heap.h>
|
|
alpar@222
|
12 |
|
|
alpar@222
|
13 |
using namespace hugo;
|
|
alpar@222
|
14 |
|
|
alpar@222
|
15 |
int main(int, char **) {
|
|
alpar@222
|
16 |
typedef SmartGraph::Node Node;
|
|
alpar@222
|
17 |
typedef SmartGraph::NodeIt NodeIt;
|
|
alpar@222
|
18 |
typedef SmartGraph::InEdgeIt InEdgeIt;
|
|
alpar@222
|
19 |
|
|
alpar@222
|
20 |
SmartGraph G;
|
|
alpar@222
|
21 |
Node s, t;
|
|
alpar@222
|
22 |
SmartGraph::EdgeMap<int> cap(G);
|
|
alpar@222
|
23 |
Timer tim;
|
|
alpar@222
|
24 |
std::cout << "DIMACS load ..." << std::endl;
|
|
alpar@222
|
25 |
readDimacsMaxFlow(std::cin, G, s, t, cap);
|
|
alpar@222
|
26 |
std::cout << " " << tim <<std::endl;
|
|
alpar@222
|
27 |
|
|
alpar@222
|
28 |
std::cout << "dijkstra demo ..." << std::endl;
|
|
alpar@222
|
29 |
|
|
alpar@222
|
30 |
//double pre_time=currTime();
|
|
alpar@222
|
31 |
tim.reset();
|
|
alpar@222
|
32 |
Dijkstra <SmartGraph,
|
|
alpar@222
|
33 |
SmartGraph::EdgeMap<int>,
|
|
alpar@222
|
34 |
FibHeap<SmartGraph::Node, int, SmartGraph::NodeMap<int> >
|
|
alpar@222
|
35 |
> dijkstra_test(G, cap);
|
|
alpar@222
|
36 |
|
|
alpar@222
|
37 |
dijkstra_test.run(s);
|
|
alpar@222
|
38 |
//double post_time=currTime();
|
|
alpar@222
|
39 |
|
|
alpar@222
|
40 |
std::cout << "running time with fib_heap: "
|
|
alpar@222
|
41 |
// << post_time-pre_time << " sec"
|
|
alpar@222
|
42 |
<< tim
|
|
alpar@222
|
43 |
<< std::endl;
|
|
alpar@222
|
44 |
|
|
alpar@222
|
45 |
//pre_time=currTime();
|
|
alpar@222
|
46 |
tim.reset();
|
|
alpar@222
|
47 |
Dijkstra < SmartGraph,
|
|
alpar@222
|
48 |
SmartGraph::EdgeMap<int>,
|
|
alpar@222
|
49 |
BinHeap<SmartGraph::Node, int, SmartGraph::NodeMap<int> > >
|
|
alpar@222
|
50 |
dijkstra_test2(G, cap);
|
|
alpar@222
|
51 |
|
|
alpar@222
|
52 |
dijkstra_test2.run(s);
|
|
alpar@222
|
53 |
//post_time=currTime();
|
|
alpar@222
|
54 |
|
|
alpar@222
|
55 |
std::cout << "running time with bin_heap: "
|
|
alpar@222
|
56 |
// << post_time-pre_time << " sec"
|
|
alpar@222
|
57 |
<< tim
|
|
alpar@222
|
58 |
<< std::endl;
|
|
alpar@222
|
59 |
|
|
alpar@222
|
60 |
|
|
alpar@222
|
61 |
int hiba_fib=0;
|
|
alpar@222
|
62 |
int hiba_bin=0;
|
|
alpar@222
|
63 |
NodeIt u;
|
|
alpar@222
|
64 |
for ( G.first(u) ; G.valid(u); G.next(u) ) {
|
|
alpar@222
|
65 |
InEdgeIt e;
|
|
alpar@222
|
66 |
for ( G.first(e,u); G.valid(e); G.next(e) ) {
|
|
alpar@222
|
67 |
Node v=G.tail(e);
|
|
alpar@222
|
68 |
if ( dijkstra_test.dist(u) - dijkstra_test.dist(v) > cap[e] )
|
|
alpar@222
|
69 |
{
|
|
alpar@222
|
70 |
std::cout<<"Hibas el a fibonaccis Dijkstraban: "
|
|
alpar@222
|
71 |
<< dijkstra_test.dist(u) - dijkstra_test.dist(v) -
|
|
alpar@222
|
72 |
cap[e]<<std::endl;
|
|
alpar@222
|
73 |
++hiba_fib;
|
|
alpar@222
|
74 |
}
|
|
alpar@222
|
75 |
if ( dijkstra_test2.dist(u) - dijkstra_test2.dist(v) > cap[e] )
|
|
alpar@222
|
76 |
{
|
|
alpar@222
|
77 |
std::cout<<"Hibas el a binarisos Dijkstraban: "
|
|
alpar@222
|
78 |
<< dijkstra_test2.dist(u) - dijkstra_test2.dist(v) -
|
|
alpar@222
|
79 |
cap[e]<<std::endl;
|
|
alpar@222
|
80 |
++hiba_bin;
|
|
alpar@222
|
81 |
}
|
|
alpar@222
|
82 |
if ( e==dijkstra_test.pred(u) &&
|
|
alpar@222
|
83 |
dijkstra_test.dist(u) - dijkstra_test.dist(v) != cap[e] )
|
|
alpar@222
|
84 |
{
|
|
alpar@222
|
85 |
std::cout<<"Hibas fael a fibonaccis Dijkstraban: "<<
|
|
alpar@222
|
86 |
dijkstra_test.dist(u) - dijkstra_test.dist(v)- cap[e]<<std::endl;
|
|
alpar@222
|
87 |
++hiba_fib;
|
|
alpar@222
|
88 |
}
|
|
alpar@222
|
89 |
if ( e==dijkstra_test2.pred(u) &&
|
|
alpar@222
|
90 |
dijkstra_test2.dist(u) - dijkstra_test2.dist(v) != cap[e] )
|
|
alpar@222
|
91 |
{
|
|
alpar@222
|
92 |
std::cout<<"Hibas fael a binarisos Dijkstraban: "<<
|
|
alpar@222
|
93 |
dijkstra_test2.dist(u) - dijkstra_test2.dist(v)- cap[e]<<std::endl;
|
|
alpar@222
|
94 |
++hiba_bin;
|
|
alpar@222
|
95 |
}
|
|
alpar@222
|
96 |
}
|
|
alpar@222
|
97 |
|
|
alpar@222
|
98 |
if ( dijkstra_test.dist(u) != dijkstra_test2.dist(u) )
|
|
alpar@222
|
99 |
std::cout << "Nem egyezik meg a tavolsag!"<<std::endl;
|
|
alpar@222
|
100 |
|
|
alpar@222
|
101 |
|
|
alpar@222
|
102 |
}
|
|
alpar@222
|
103 |
|
|
alpar@222
|
104 |
std::cout << "Hibas elek szama a fibonaccis Dijkstraban: "
|
|
alpar@222
|
105 |
<< hiba_fib << " a " << G.edgeNum() <<"-bol."<< std::endl;
|
|
alpar@222
|
106 |
|
|
alpar@222
|
107 |
std::cout << "Hibas elek szama a binarisos Dijkstraban: "
|
|
alpar@222
|
108 |
<< hiba_bin << " a " << G.edgeNum() <<"-bol."<< std::endl;
|
|
alpar@222
|
109 |
|
|
alpar@222
|
110 |
|
|
alpar@222
|
111 |
|
|
alpar@222
|
112 |
|
|
alpar@222
|
113 |
return 0;
|
|
alpar@222
|
114 |
}
|