|
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 |
|
13 using namespace hugo; |
|
14 |
|
15 int 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 } |