1 // -*- c++ -*- |
|
2 |
|
3 // Use a DIMACS max flow file as follows: |
|
4 // graph_wrapper_time dimacs_max_flow_file |
|
5 |
|
6 #include <iostream> |
|
7 #include <fstream> |
|
8 #include <string> |
|
9 #include <vector> |
|
10 #include <lemon/invalid.h> |
|
11 #include <lemon/time_measure.h> |
|
12 #include <lemon/graph_wrapper.h> |
|
13 #include <lemon/preflow.h> |
|
14 #include <lemon/dimacs.h> |
|
15 #include <lemon/list_graph.h> |
|
16 |
|
17 using namespace lemon; |
|
18 |
|
19 using std::cout; |
|
20 using std::endl; |
|
21 |
|
22 template<typename Graph> |
|
23 void timeTest(std::string str, Graph& g) { |
|
24 g.clear(); |
|
25 typename Graph::Node s; |
|
26 typename Graph::Node t; |
|
27 typedef typename Graph::template EdgeMap<int> FlowMap; |
|
28 FlowMap cap(g); |
|
29 FlowMap flow(g); |
|
30 std::ifstream is(str.c_str()); |
|
31 readDimacs(is, g, cap, s, t); |
|
32 Timer ts; |
|
33 ts.reset(); |
|
34 |
|
35 typedef Preflow<Graph, int, FlowMap, FlowMap> MyPreflow; |
|
36 MyPreflow max_flow(g, s, t, cap, flow); |
|
37 max_flow.run(MyPreflow::NO_FLOW); |
|
38 cout << "flow value: " << max_flow.flowValue() << endl; |
|
39 cout << ts << endl; |
|
40 } |
|
41 |
|
42 int main(int, char** argv) { |
|
43 std::string in=argv[1]; |
|
44 |
|
45 typedef ListGraph Graph; |
|
46 Graph g; |
|
47 timeTest<Graph>(in, g); |
|
48 typedef GraphWrapper<Graph> Graph1; |
|
49 Graph1 g1(g); |
|
50 timeTest<Graph1>(in, g1); |
|
51 typedef GraphWrapper<Graph1> Graph2; |
|
52 Graph2 g2(g1); |
|
53 timeTest<Graph2>(in, g2); |
|
54 typedef GraphWrapper<Graph2> Graph3; |
|
55 Graph3 g3(g2); |
|
56 timeTest<Graph3>(in, g3); |
|
57 typedef GraphWrapper<Graph3> Graph4; |
|
58 Graph4 g4(g3); |
|
59 timeTest<Graph4>(in, g4); |
|
60 typedef GraphWrapper<Graph4> Graph5; |
|
61 Graph5 g5(g4); |
|
62 timeTest<Graph5>(in, g5); |
|
63 typedef GraphWrapper<Graph5> Graph6; |
|
64 Graph6 g6(g5); |
|
65 timeTest<Graph6>(in, g6); |
|
66 typedef GraphWrapper<Graph6> Graph7; |
|
67 Graph7 g7(g6); |
|
68 timeTest<Graph7>(in, g7); |
|
69 |
|
70 return 0; |
|
71 } |
|