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