10 #include <fib_heap.h> |
11 #include <fib_heap.h> |
11 |
12 |
12 using namespace hugo; |
13 using namespace hugo; |
13 |
14 |
14 int main(int, char **) { |
15 int main(int, char **) { |
15 typedef ListGraph::Node Node; |
16 typedef SmartGraph::Node Node; |
16 |
17 |
17 ListGraph G; |
18 SmartGraph G; |
18 Node s, t; |
19 Node s, t; |
19 ListGraph::EdgeMap<int> cap(G); |
20 SmartGraph::EdgeMap<int> cap(G); |
20 readDimacsMaxFlow(std::cin, G, s, t, cap); |
21 readDimacsMaxFlow(std::cin, G, s, t, cap); |
21 |
22 |
22 std::cout << "prim demo ..." << std::endl; |
23 std::cout << "prim demo ..." << std::endl; |
23 |
24 |
24 double pre_time=currTime(); |
25 double pre_time=currTime(); |
25 Prim<ListGraph, int, FibHeap<ListGraph::Node, int, |
26 Prim<SmartGraph, int, FibHeap<SmartGraph::Node, int, |
26 ListGraph::NodeMap<int> > > prim_test(G, cap); |
27 SmartGraph::NodeMap<int> > > prim_test(G, cap); |
27 prim_test.run(); |
28 prim_test.run(); |
28 double post_time=currTime(); |
29 double post_time=currTime(); |
29 |
30 |
30 std::cout << "running time with fib_heap: " |
31 std::cout << "running time with fib_heap: " |
31 << post_time-pre_time << " sec"<< std::endl; |
32 << post_time-pre_time << " sec"<< std::endl; |
32 |
33 |
33 pre_time=currTime(); |
34 pre_time=currTime(); |
34 Prim<ListGraph, int, BinHeap<ListGraph::Node, int, |
35 Prim<SmartGraph, int, BinHeap<SmartGraph::Node, int, |
35 ListGraph::NodeMap<int> > > prim_test2(G, cap); |
36 SmartGraph::NodeMap<int> > > prim_test2(G, cap); |
36 prim_test2.run(); |
37 prim_test2.run(); |
37 post_time=currTime(); |
38 post_time=currTime(); |
38 |
39 |
39 std::cout << "running time with bin_heap: " |
40 std::cout << "running time with bin_heap: " |
40 << post_time-pre_time << " sec"<< std::endl; |
41 << post_time-pre_time << " sec"<< std::endl; |