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 |
|
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 <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 } |
|