23 readDimacsMaxFlow(std::cin, G, s, t, cap); |
23 readDimacsMaxFlow(std::cin, G, s, t, cap); |
24 |
24 |
25 std::cout << "dijkstra demo ..." << std::endl; |
25 std::cout << "dijkstra demo ..." << std::endl; |
26 |
26 |
27 double pre_time=currTime(); |
27 double pre_time=currTime(); |
28 Dijkstra<SmartGraph, int, FibHeap<SmartGraph::Node, int, |
28 Dijkstra<SmartGraph, int, FibHeap<SmartGraph::Node, int, |
29 SmartGraph::NodeMap<int> > > dijkstra_test(G, cap); |
29 SmartGraph::NodeMap<int> > > dijkstra_test(G, cap); |
30 dijkstra_test.run(s); |
30 dijkstra_test.run(s); |
31 double post_time=currTime(); |
31 double post_time=currTime(); |
32 |
32 |
33 std::cout << "running time with fib_heap: " |
33 std::cout << "running time with fib_heap: " |
34 << post_time-pre_time << " sec"<< std::endl; |
34 << post_time-pre_time << " sec"<< std::endl; |
35 |
35 |
36 pre_time=currTime(); |
36 pre_time=currTime(); |
37 Dijkstra<SmartGraph, int, BinHeap<SmartGraph::Node, int, |
37 Dijkstra<SmartGraph, int, BinHeap<SmartGraph::Node, int, |
38 SmartGraph::NodeMap<int> > > dijkstra_test2(G, cap); |
38 SmartGraph::NodeMap<int> > > dijkstra_test2(G, cap); |
48 NodeIt u; |
48 NodeIt u; |
49 for ( G.first(u) ; G.valid(u); G.next(u) ) { |
49 for ( G.first(u) ; G.valid(u); G.next(u) ) { |
50 InEdgeIt e; |
50 InEdgeIt e; |
51 for ( G.first(e,u); G.valid(e); G.next(e) ) { |
51 for ( G.first(e,u); G.valid(e); G.next(e) ) { |
52 Node v=G.tail(e); |
52 Node v=G.tail(e); |
53 if ( dijkstra_test.dist(u) - dijkstra_test.dist(v) > cap.get(e) ) |
53 if ( dijkstra_test.dist(u) - dijkstra_test.dist(v) > cap[e] ) |
54 { |
54 { |
55 std::cout<<"Hibas el a fibonaccis Dijkstraban: " |
55 std::cout<<"Hibas el a fibonaccis Dijkstraban: " |
56 << dijkstra_test.dist(u) - dijkstra_test.dist(v) - |
56 << dijkstra_test.dist(u) - dijkstra_test.dist(v) - |
57 cap.get(e)<<std::endl; |
57 cap[e]<<std::endl; |
58 ++hiba_fib; |
58 ++hiba_fib; |
59 } |
59 } |
60 if ( dijkstra_test2.dist(u) - dijkstra_test2.dist(v) > cap.get(e) ) |
60 if ( dijkstra_test2.dist(u) - dijkstra_test2.dist(v) > cap[e] ) |
61 { |
61 { |
62 std::cout<<"Hibas el a binarisos Dijkstraban: " |
62 std::cout<<"Hibas el a binarisos Dijkstraban: " |
63 << dijkstra_test2.dist(u) - dijkstra_test2.dist(v) - |
63 << dijkstra_test2.dist(u) - dijkstra_test2.dist(v) - |
64 cap.get(e)<<std::endl; |
64 cap[e]<<std::endl; |
65 ++hiba_bin; |
65 ++hiba_bin; |
66 } |
66 } |
67 if ( e==dijkstra_test.pred(u) && |
67 if ( e==dijkstra_test.pred(u) && |
68 dijkstra_test.dist(u) - dijkstra_test.dist(v) != cap.get(e) ) |
68 dijkstra_test.dist(u) - dijkstra_test.dist(v) != cap[e] ) |
69 { |
69 { |
70 std::cout<<"Hibas fael a fibonaccis Dijkstraban: "<< |
70 std::cout<<"Hibas fael a fibonaccis Dijkstraban: "<< |
71 dijkstra_test.dist(u) - dijkstra_test.dist(v)- cap.get(e)<<std::endl; |
71 dijkstra_test.dist(u) - dijkstra_test.dist(v)- cap[e]<<std::endl; |
72 ++hiba_fib; |
72 ++hiba_fib; |
73 } |
73 } |
74 if ( e==dijkstra_test2.pred(u) && |
74 if ( e==dijkstra_test2.pred(u) && |
75 dijkstra_test2.dist(u) - dijkstra_test2.dist(v) != cap.get(e) ) |
75 dijkstra_test2.dist(u) - dijkstra_test2.dist(v) != cap[e] ) |
76 { |
76 { |
77 std::cout<<"Hibas fael a binarisos Dijkstraban: "<< |
77 std::cout<<"Hibas fael a binarisos Dijkstraban: "<< |
78 dijkstra_test2.dist(u) - dijkstra_test2.dist(v)- cap.get(e)<<std::endl; |
78 dijkstra_test2.dist(u) - dijkstra_test2.dist(v)- cap[e]<<std::endl; |
79 ++hiba_bin; |
79 ++hiba_bin; |
80 } |
80 } |
81 } |
81 } |
82 |
82 |
83 if ( dijkstra_test.dist(u) != dijkstra_test2.dist(u) ) |
83 if ( dijkstra_test.dist(u) != dijkstra_test2.dist(u) ) |