|
1 #include <iostream> |
|
2 #include <vector> |
|
3 #include <string> |
|
4 |
|
5 #include <marci_list_graph.hh> |
|
6 #include <marci_graph_traits.hh> |
|
7 #include <marci_property_vector.hh> |
|
8 #include <preflow_push_hl.hh> |
|
9 #include <preflow_push_max_flow.hh> |
|
10 #include <reverse_bfs.hh> |
|
11 #include <dijkstra.hh> |
|
12 |
|
13 using namespace marci; |
|
14 |
|
15 |
|
16 int main (int, char*[]) |
|
17 { |
|
18 typedef graph_traits<list_graph>::node_iterator node_iterator; |
|
19 typedef graph_traits<list_graph>::edge_iterator edge_iterator; |
|
20 typedef graph_traits<list_graph>::each_node_iterator each_node_iterator; |
|
21 typedef graph_traits<list_graph>::each_edge_iterator each_edge_iterator; |
|
22 typedef graph_traits<list_graph>::out_edge_iterator out_edge_iterator; |
|
23 typedef graph_traits<list_graph>::in_edge_iterator in_edge_iterator; |
|
24 typedef graph_traits<list_graph>::sym_edge_iterator sym_edge_iterator; |
|
25 |
|
26 list_graph flow_test; |
|
27 |
|
28 //Ahuja könyv példája, maxflowvalue=13 |
|
29 node_iterator s=flow_test.add_node(); |
|
30 node_iterator v1=flow_test.add_node(); |
|
31 node_iterator v2=flow_test.add_node(); |
|
32 node_iterator v3=flow_test.add_node(); |
|
33 node_iterator v4=flow_test.add_node(); |
|
34 node_iterator v5=flow_test.add_node(); |
|
35 node_iterator t=flow_test.add_node(); |
|
36 |
|
37 node_property_vector<list_graph, std::string> node_name(flow_test); |
|
38 node_name.put(s, "s"); |
|
39 node_name.put(v1, "v1"); |
|
40 node_name.put(v2, "v2"); |
|
41 node_name.put(v3, "v3"); |
|
42 node_name.put(v4, "v4"); |
|
43 node_name.put(v5, "v5"); |
|
44 node_name.put(t, "t"); |
|
45 |
|
46 edge_iterator s_v1=flow_test.add_edge(s, v1); |
|
47 edge_iterator s_v2=flow_test.add_edge(s, v2); |
|
48 edge_iterator s_v3=flow_test.add_edge(s, v3); |
|
49 edge_iterator v2_v4=flow_test.add_edge(v2, v4); |
|
50 edge_iterator v2_v5=flow_test.add_edge(v2, v5); |
|
51 edge_iterator v3_v5=flow_test.add_edge(v3, v5); |
|
52 edge_iterator v4_t=flow_test.add_edge(v4, t); |
|
53 edge_iterator v5_t=flow_test.add_edge(v5, t); |
|
54 edge_iterator v2_s=flow_test.add_edge(v2, s); |
|
55 |
|
56 edge_property_vector<list_graph, int> cap(flow_test); |
|
57 cap.put(s_v1, 0); |
|
58 cap.put(s_v2, 10); |
|
59 cap.put(s_v3, 10); |
|
60 cap.put(v2_v4, 5); |
|
61 cap.put(v2_v5, 8); |
|
62 cap.put(v3_v5, 5); |
|
63 cap.put(v4_t, 8); |
|
64 cap.put(v5_t, 8); |
|
65 cap.put(v2_s, 0); |
|
66 |
|
67 |
|
68 |
|
69 //Marci példája, maxflowvalue=23 |
|
70 /* node_iterator s=flow_test.add_node(); |
|
71 node_iterator v1=flow_test.add_node(); |
|
72 node_iterator v2=flow_test.add_node(); |
|
73 node_iterator v3=flow_test.add_node(); |
|
74 node_iterator v4=flow_test.add_node(); |
|
75 node_iterator t=flow_test.add_node(); |
|
76 node_iterator w=flow_test.add_node(); |
|
77 |
|
78 |
|
79 node_property_vector<list_graph, std::string> node_name(flow_test); |
|
80 node_name.put(s, "s"); |
|
81 node_name.put(v1, "v1"); |
|
82 node_name.put(v2, "v2"); |
|
83 node_name.put(v3, "v3"); |
|
84 node_name.put(v4, "v4"); |
|
85 node_name.put(t, "t"); |
|
86 node_name.put(w, "w"); |
|
87 |
|
88 edge_iterator s_v1=flow_test.add_edge(s, v1); |
|
89 edge_iterator s_v2=flow_test.add_edge(s, v2); |
|
90 edge_iterator v1_v2=flow_test.add_edge(v1, v2); |
|
91 edge_iterator v2_v1=flow_test.add_edge(v2, v1); |
|
92 edge_iterator v1_v3=flow_test.add_edge(v1, v3); |
|
93 edge_iterator v3_v2=flow_test.add_edge(v3, v2); |
|
94 edge_iterator v2_v4=flow_test.add_edge(v2, v4); |
|
95 edge_iterator v4_v3=flow_test.add_edge(v4, v3); |
|
96 edge_iterator v3_t=flow_test.add_edge(v3, t); |
|
97 edge_iterator v4_t=flow_test.add_edge(v4, t); |
|
98 edge_iterator v3_v3=flow_test.add_edge(v3, v3); |
|
99 edge_iterator s_w=flow_test.add_edge(s, w); |
|
100 // edge_iterator v2_s=flow_test.add_edge(v2, s); |
|
101 |
|
102 |
|
103 |
|
104 edge_property_vector<list_graph, int> cap(flow_test); //serves as length in dijkstra |
|
105 cap.put(s_v1, 16); |
|
106 cap.put(s_v2, 13); |
|
107 cap.put(v1_v2, 10); |
|
108 cap.put(v2_v1, 4); |
|
109 cap.put(v1_v3, 12); |
|
110 cap.put(v3_v2, 9); |
|
111 cap.put(v2_v4, 14); |
|
112 cap.put(v4_v3, 7); |
|
113 cap.put(v3_t, 20); |
|
114 cap.put(v4_t, 4); |
|
115 cap.put(v3_v3, 4); |
|
116 cap.put(s_w, 4); |
|
117 // cap.put(v2_s, 0); |
|
118 |
|
119 */ |
|
120 |
|
121 //pelda 3, maxflowvalue=4 |
|
122 /* node_iterator s=flow_test.add_node(); |
|
123 node_iterator v1=flow_test.add_node(); |
|
124 node_iterator v2=flow_test.add_node(); |
|
125 node_iterator t=flow_test.add_node(); |
|
126 node_iterator w=flow_test.add_node(); |
|
127 |
|
128 node_property_vector<list_graph, std::string> node_name(flow_test); |
|
129 node_name.put(s, "s"); |
|
130 node_name.put(v1, "v1"); |
|
131 node_name.put(v2, "v2"); |
|
132 node_name.put(t, "t"); |
|
133 node_name.put(w, "w"); |
|
134 |
|
135 edge_iterator s_v1=flow_test.add_edge(s, v1); |
|
136 edge_iterator v1_v2=flow_test.add_edge(v1, v2); |
|
137 edge_iterator v2_t=flow_test.add_edge(v2, t); |
|
138 edge_iterator v1_v1=flow_test.add_edge(v1, v1); |
|
139 edge_iterator s_w=flow_test.add_edge(s, w); |
|
140 |
|
141 |
|
142 edge_property_vector<list_graph, int> cap(flow_test); |
|
143 |
|
144 cap.put(s_v1, 16); |
|
145 cap.put(v1_v2, 10); |
|
146 cap.put(v2_t, 4); |
|
147 cap.put(v1_v1, 3); |
|
148 cap.put(s_w, 5); |
|
149 */ |
|
150 |
|
151 |
|
152 |
|
153 |
|
154 std::cout << "Testing reverse_bfs..." << std::endl; |
|
155 |
|
156 reverse_bfs<list_graph> bfs_test(flow_test, t); |
|
157 |
|
158 bfs_test.run(); |
|
159 |
|
160 for (each_node_iterator w=flow_test.first_node(); w.valid(); ++w) { |
|
161 std::cout <<"The distance of " << w << " is " << bfs_test.dist(w) <<std::endl; |
|
162 } |
|
163 |
|
164 |
|
165 |
|
166 |
|
167 |
|
168 std::cout << "Testing preflow_push_hl..." << std::endl; |
|
169 |
|
170 preflow_push_hl<list_graph, int> preflow_push_test(flow_test, s, t, cap); |
|
171 |
|
172 preflow_push_test.run(); |
|
173 |
|
174 std::cout << "Maximum flow value is: " << preflow_push_test.maxflow() << "."<<std::endl; |
|
175 |
|
176 std::cout<< "The flow on edge s-v1 is "<< preflow_push_test.flowonedge(s_v1) << "."<<std::endl; |
|
177 |
|
178 edge_property_vector<list_graph, int> flow=preflow_push_test.allflow(); |
|
179 for (each_edge_iterator e=flow_test.first_edge(); e.valid(); ++e) { |
|
180 std::cout <<"Flow on edge " << flow_test.tail(e) <<"-" << flow_test.head(e)<< " is " <<flow.get(e) <<std::endl; |
|
181 } |
|
182 |
|
183 std::cout << "A minimum cut: " <<std::endl; |
|
184 node_property_vector<list_graph, bool> mincut=preflow_push_test.mincut(); |
|
185 |
|
186 for (each_node_iterator v=flow_test.first_node(); v.valid(); ++v) { |
|
187 if (mincut.get(v)) std::cout <<node_name.get(v)<< " "; |
|
188 } |
|
189 |
|
190 std::cout<<"\n\n"<<std::endl; |
|
191 |
|
192 |
|
193 |
|
194 |
|
195 std::cout << "Testing preflow_push_max_flow..." << std::endl; |
|
196 |
|
197 preflow_push_max_flow<list_graph, int> max_flow_test(flow_test, s, t, cap); |
|
198 |
|
199 max_flow_test.run(); |
|
200 |
|
201 std::cout << "Maximum flow value is: " << max_flow_test.maxflow() << "."<< std::endl; |
|
202 |
|
203 std::cout << "A minimum cut: " <<std::endl; |
|
204 node_property_vector<list_graph, bool> mincut2=max_flow_test.mincut(); |
|
205 |
|
206 for (each_node_iterator v=flow_test.first_node(); v.valid(); ++v) { |
|
207 if (mincut2.get(v)) std::cout <<node_name.get(v)<< " "; |
|
208 } |
|
209 |
|
210 std::cout << std::endl <<std::endl; |
|
211 |
|
212 |
|
213 |
|
214 std::cout << "Testing dijkstra..." << std::endl; |
|
215 |
|
216 node_iterator root=v2; |
|
217 |
|
218 dijkstra<list_graph, int> dijkstra_test(flow_test, root, cap); |
|
219 |
|
220 dijkstra_test.run(); |
|
221 |
|
222 for (each_node_iterator w=flow_test.first_node(); w.valid(); ++w) { |
|
223 if (dijkstra_test.reach(w)) { |
|
224 std::cout <<"The distance of " << w << " is " << dijkstra_test.dist(w); |
|
225 if (dijkstra_test.pred(w).valid()) { |
|
226 std::cout <<", a shortest path from the root ends with edge " << dijkstra_test.pred(w) <<std::endl; |
|
227 } else { |
|
228 std::cout <<", this is the root."<<std::endl; } |
|
229 |
|
230 } else { |
|
231 cout << w << " is not reachable from " << root <<std::endl; |
|
232 } |
|
233 } |
|
234 |
|
235 |
|
236 |
|
237 return 0; |
|
238 } |
|
239 |
|
240 |
|
241 |
|
242 |
|
243 |
|
244 |
|
245 |
|
246 |
|
247 |