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