1 // -*- c++ -*- |
1 // -*- c++ -*- |
2 |
2 |
3 // Use a DIMACS max flow file as stdin. |
3 // Use a DIMACS max flow file as stdin. |
4 // max_flow_demo < dimacs_max_flow_file |
4 // max_flow_demo < dimacs_max_flow_file |
5 |
5 |
6 |
|
7 #include <iostream> |
6 #include <iostream> |
8 #include <fstream> |
7 #include <fstream> |
9 |
8 |
10 #include <sage_graph.h> |
|
11 #include <hugo/smart_graph.h> |
9 #include <hugo/smart_graph.h> |
|
10 #include <hugo/list_graph.h> |
12 #include <hugo/dimacs.h> |
11 #include <hugo/dimacs.h> |
13 #include <hugo/time_measure.h> |
12 #include <hugo/time_measure.h> |
14 //#include <graph_wrapper.h> |
|
15 #include <hugo/preflow.h> |
13 #include <hugo/preflow.h> |
16 #include <augmenting_flow.h> |
14 #include <augmenting_flow.h> |
17 //#include <preflow_res.h> |
|
18 #include <for_each_macros.h> |
|
19 #include <graph_concept.h> |
15 #include <graph_concept.h> |
20 |
16 |
21 using namespace hugo; |
17 using namespace hugo; |
22 |
18 |
23 int main(int, char **) { |
19 int main(int, char **) { |
24 |
20 |
25 typedef SageGraph MutableGraph; |
21 typedef ListGraph MutableGraph; |
26 |
22 typedef SmartGraph Graph; |
27 //typedef FullFeatureGraphConcept Graph; |
|
28 //typedef SmartGraph Graph; |
|
29 typedef SageGraph Graph; |
|
30 typedef Graph::Node Node; |
23 typedef Graph::Node Node; |
31 typedef Graph::EdgeIt EdgeIt; |
24 typedef Graph::EdgeIt EdgeIt; |
32 |
25 |
33 Graph g; |
26 Graph g; |
34 |
27 |
51 max_flow_test.run(); |
44 max_flow_test.run(); |
52 std::cout << "elapsed time: " << ts << std::endl; |
45 std::cout << "elapsed time: " << ts << std::endl; |
53 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
46 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
54 max_flow_test.minCut(cut); |
47 max_flow_test.minCut(cut); |
55 |
48 |
56 FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
49 for(Graph::EdgeIt e(g); e!=INVALID; ++e) { |
57 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) |
50 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) |
58 std::cout << "Slackness does not hold!" << std::endl; |
51 std::cout << "Slackness does not hold!" << std::endl; |
59 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) |
52 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) |
60 std::cout << "Slackness does not hold!" << std::endl; |
53 std::cout << "Slackness does not hold!" << std::endl; |
61 } |
54 } |
62 } |
55 } |
63 |
56 |
64 { |
57 { |
65 std::cout << "preflow ..." << std::endl; |
58 std::cout << "preflow ..." << std::endl; |
66 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
59 for(Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0); |
67 ts.reset(); |
60 ts.reset(); |
68 max_flow_test.preflow(Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW); |
61 max_flow_test.run(Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW); |
69 std::cout << "elapsed time: " << ts << std::endl; |
62 std::cout << "elapsed time: " << ts << std::endl; |
70 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
63 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
71 |
64 |
72 FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
65 for(Graph::EdgeIt e(g); e!=INVALID; ++e) { |
73 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) |
66 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) |
74 std::cout << "Slackness does not hold!" << std::endl; |
67 std::cout << "Slackness does not hold!" << std::endl; |
75 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) |
68 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) |
76 std::cout << "Slackness does not hold!" << std::endl; |
69 std::cout << "Slackness does not hold!" << std::endl; |
77 } |
70 } |
86 // std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl; |
79 // std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl; |
87 // } |
80 // } |
88 |
81 |
89 { |
82 { |
90 std::cout << "physical blocking flow augmentation ..." << std::endl; |
83 std::cout << "physical blocking flow augmentation ..." << std::endl; |
91 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
84 for(Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0); |
92 ts.reset(); |
85 ts.reset(); |
93 int i=0; |
86 int i=0; |
94 while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; } |
87 while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; } |
95 std::cout << "elapsed time: " << ts << std::endl; |
88 std::cout << "elapsed time: " << ts << std::endl; |
96 std::cout << "number of augmentation phases: " << i << std::endl; |
89 std::cout << "number of augmentation phases: " << i << std::endl; |
97 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; |
90 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; |
98 |
91 |
99 FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
92 for(Graph::EdgeIt e(g); e!=INVALID; ++e) { |
100 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) |
93 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) |
101 std::cout << "Slackness does not hold!" << std::endl; |
94 std::cout << "Slackness does not hold!" << std::endl; |
102 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) |
95 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) |
103 std::cout << "Slackness does not hold!" << std::endl; |
96 std::cout << "Slackness does not hold!" << std::endl; |
104 } |
97 } |
105 } |
98 } |
106 |
99 |
107 { |
100 { |
108 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl; |
101 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl; |
109 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
102 for(Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0); |
110 ts.reset(); |
103 ts.reset(); |
111 int i=0; |
104 int i=0; |
112 while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; } |
105 while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; } |
113 std::cout << "elapsed time: " << ts << std::endl; |
106 std::cout << "elapsed time: " << ts << std::endl; |
114 std::cout << "number of augmentation phases: " << i << std::endl; |
107 std::cout << "number of augmentation phases: " << i << std::endl; |
115 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; |
108 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; |
116 |
109 |
117 FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
110 for(Graph::EdgeIt e(g); e!=INVALID; ++e) { |
118 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) |
111 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) |
119 std::cout << "Slackness does not hold!" << std::endl; |
112 std::cout << "Slackness does not hold!" << std::endl; |
120 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) |
113 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) |
121 std::cout << "Slackness does not hold!" << std::endl; |
114 std::cout << "Slackness does not hold!" << std::endl; |
122 } |
115 } |
123 } |
116 } |
124 |
117 |
125 { |
118 { |
126 std::cout << "on-the-fly shortest path augmentation ..." << std::endl; |
119 std::cout << "on-the-fly shortest path augmentation ..." << std::endl; |
127 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
120 for(Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0); |
128 ts.reset(); |
121 ts.reset(); |
129 int i=0; |
122 int i=0; |
130 while (augmenting_flow_test.augmentOnShortestPath()) { ++i; } |
123 while (augmenting_flow_test.augmentOnShortestPath()) { ++i; } |
131 std::cout << "elapsed time: " << ts << std::endl; |
124 std::cout << "elapsed time: " << ts << std::endl; |
132 std::cout << "number of augmentation phases: " << i << std::endl; |
125 std::cout << "number of augmentation phases: " << i << std::endl; |
133 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; |
126 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; |
134 |
127 |
135 FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
128 for(Graph::EdgeIt e(g); e!=INVALID; ++e) { |
136 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) |
129 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) |
137 std::cout << "Slackness does not hold!" << std::endl; |
130 std::cout << "Slackness does not hold!" << std::endl; |
138 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) |
131 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) |
139 std::cout << "Slackness does not hold!" << std::endl; |
132 std::cout << "Slackness does not hold!" << std::endl; |
140 } |
133 } |
141 } |
134 } |
142 |
135 |
143 { |
136 { |
144 std::cout << "on-the-fly shortest path augmentation ..." << std::endl; |
137 std::cout << "on-the-fly shortest path augmentation ..." << std::endl; |
145 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
138 for(Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0); |
146 ts.reset(); |
139 ts.reset(); |
147 int i=0; |
140 int i=0; |
148 while (augmenting_flow_test.augmentOnShortestPath2()) { ++i; } |
141 while (augmenting_flow_test.augmentOnShortestPath2()) { ++i; } |
149 std::cout << "elapsed time: " << ts << std::endl; |
142 std::cout << "elapsed time: " << ts << std::endl; |
150 std::cout << "number of augmentation phases: " << i << std::endl; |
143 std::cout << "number of augmentation phases: " << i << std::endl; |
151 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; |
144 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; |
152 |
145 |
153 FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
146 for(Graph::EdgeIt e(g); e!=INVALID; ++e) { |
154 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) |
147 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) |
155 std::cout << "Slackness does not hold!" << std::endl; |
148 std::cout << "Slackness does not hold!" << std::endl; |
156 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) |
149 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) |
157 std::cout << "Slackness does not hold!" << std::endl; |
150 std::cout << "Slackness does not hold!" << std::endl; |
158 } |
151 } |