1 #include <iostream> |
|
2 #include <vector> |
|
3 #include <string> |
|
4 |
|
5 #include <list_graph.h> |
|
6 #include <bfs_iterator.h> |
|
7 #include <edmonds_karp.h> |
|
8 |
|
9 using namespace lemon; |
|
10 |
|
11 int main (int, char*[]) |
|
12 { |
|
13 typedef ListGraph::Node Node; |
|
14 typedef ListGraph::Edge Edge; |
|
15 typedef ListGraph::NodeIt NodeIt; |
|
16 typedef ListGraph::EdgeIt EdgeIt; |
|
17 typedef ListGraph::OutEdgeIt OutEdgeIt; |
|
18 typedef ListGraph::InEdgeIt InEdgeIt; |
|
19 typedef ListGraph::SymEdgeIt SymEdgeIt; |
|
20 ListGraph G; |
|
21 std::vector<Node> vector_of_Nodes; |
|
22 for(int i=0; i!=8; ++i) vector_of_Nodes.push_back(G.addNode()); |
|
23 for(int i=0; i!=8; ++i) |
|
24 for(int j=0; j!=8; ++j) |
|
25 if ((i<j)&&(i+j)%3) G.addEdge(vector_of_Nodes[i], vector_of_Nodes[j]); |
|
26 |
|
27 std::cout << "We construct a directed graph on the node set {0,1,2,...,7}," <<std::endl << "i-->j is arc iff i<j and (i+j)%3." << std::endl; |
|
28 std::cout << "number of nodes: " << count(G.first<NodeIt>()) << std::endl; |
|
29 |
|
30 for(NodeIt i=G.first<NodeIt>(); G.valid(i); G.next(i)) { |
|
31 std::cout << "node " << G.id(i) << std::endl; |
|
32 std::cout << " outdegree (OutEdgeIt): " << count(G.first<OutEdgeIt>(i)) << " "; |
|
33 for(OutEdgeIt j=G.first<OutEdgeIt>(i); G.valid(j); G.next(j)) { |
|
34 std::cout << "(" << G.id(G.source(j)) << "--" << G.id(j) << "->" << G.id(G.target(j)) << ") "; |
|
35 } |
|
36 std::cout << std::endl; |
|
37 |
|
38 std::cout<< " "; |
|
39 for(OutEdgeIt j=G.first<OutEdgeIt>(i); G.valid(j); G.next(j)) { |
|
40 std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; } |
|
41 std::cout<<std::endl; |
|
42 |
|
43 std::cout << " indegree: (InEdgeIt) " << count(G.first<InEdgeIt>(i)) << " "; |
|
44 for(InEdgeIt j=G.first<InEdgeIt>(i); G.valid(j); G.next(j)) { |
|
45 std::cout << j << " "; } |
|
46 std::cout << std::endl; |
|
47 |
|
48 std::cout<< " "; |
|
49 for(InEdgeIt j=G.first<InEdgeIt>(i); G.valid(j); G.next(j)) { |
|
50 std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; } |
|
51 std::cout<<std::endl; |
|
52 |
|
53 std::cout << " degree: (SymEdgeIt) " << count(G.first<SymEdgeIt>(i)) << " "; |
|
54 for(SymEdgeIt j=G.first<SymEdgeIt>(i); G.valid(j); G.next(j)) { |
|
55 std::cout << j << " "; } |
|
56 std::cout<<std::endl; |
|
57 |
|
58 std::cout<< " "; |
|
59 for(SymEdgeIt j=G.first<SymEdgeIt>(i); G.valid(j); G.next(j)) { |
|
60 std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; } |
|
61 std::cout<<std::endl; |
|
62 } |
|
63 |
|
64 std::cout << "all edges: "; |
|
65 for(EdgeIt i=G.first<EdgeIt>(); G.valid(i); G.next(i)) { |
|
66 std::cout << i << " "; |
|
67 } |
|
68 std::cout << std::endl; |
|
69 |
|
70 std::cout << "node property array test" << std::endl; |
|
71 ListGraph::NodeMap<int> my_property_vector(G); |
|
72 NodeIt v; |
|
73 G.first(v); |
|
74 my_property_vector.set(v, 42); |
|
75 my_property_vector.set(G.next(G.first<NodeIt>()), 314); |
|
76 my_property_vector.set(G.next(G.next(G.first<NodeIt>())), 1956); |
|
77 my_property_vector.set(vector_of_Nodes[3], 1989); |
|
78 my_property_vector.set(vector_of_Nodes[4], 2003); |
|
79 my_property_vector.set(vector_of_Nodes[7], 1978); |
|
80 std::cout << "some node property values..." << std::endl; |
|
81 for(NodeIt i=G.first<NodeIt>(); G.valid(i); G.next(i)) { |
|
82 std::cout << my_property_vector.get(i) << std::endl; |
|
83 } |
|
84 int _i=1; |
|
85 int _ii=1; |
|
86 ListGraph::EdgeMap<int> my_edge_property(G); |
|
87 for(EdgeIt i=G.first<EdgeIt>(); G.valid(i); G.next(i)) { |
|
88 my_edge_property.set(i, _i); |
|
89 _i*=_ii; ++_ii; |
|
90 } |
|
91 |
|
92 std::cout << "node and edge property values on the sources and targets of edges..." << std::endl; |
|
93 for(EdgeIt j=G.first<EdgeIt>(); G.valid(j); G.next(j)) { |
|
94 std::cout << my_property_vector.get(G.source(j)) << "--" << my_edge_property.get(j) << "-->" << my_property_vector.get(G.target(j)) << " "; |
|
95 } |
|
96 std::cout << std::endl; |
|
97 /* |
|
98 std::cout << "bfs from the first node" << std::endl; |
|
99 bfs<ListGraph> bfs_test(G, G.first<NodeIt>()); |
|
100 bfs_test.run(); |
|
101 std::cout << "reached: "; |
|
102 for(NodeIt i=G.first<NodeIt>(); G.valid(i); G.next(i)) { |
|
103 std::cout << bfs_test.reached.get(i) << " "; |
|
104 } |
|
105 std::cout<<std::endl; |
|
106 std::cout << "dist: "; |
|
107 for(NodeIt i=G.first<NodeIt>(); G.valid(i); G.next(i)) { |
|
108 std::cout << bfs_test.dist.get(i) << " "; |
|
109 } |
|
110 std::cout<<std::endl; |
|
111 */ |
|
112 |
|
113 std::cout << "augmenting path flow algorithm test..." << std::endl; |
|
114 ListGraph flowG; |
|
115 |
|
116 Node s=flowG.addNode(); |
|
117 Node v1=flowG.addNode(); |
|
118 Node v2=flowG.addNode(); |
|
119 Node v3=flowG.addNode(); |
|
120 Node v4=flowG.addNode(); |
|
121 Node t=flowG.addNode(); |
|
122 |
|
123 ListGraph::NodeMap<std::string> node_name(flowG); |
|
124 node_name.set(s, "s"); |
|
125 node_name.set(v1, "v1"); |
|
126 node_name.set(v2, "v2"); |
|
127 node_name.set(v3, "v3"); |
|
128 node_name.set(v4, "v4"); |
|
129 node_name.set(t, "t"); |
|
130 |
|
131 Edge s_v1=flowG.addEdge(s, v1); |
|
132 Edge s_v2=flowG.addEdge(s, v2); |
|
133 Edge v1_v2=flowG.addEdge(v1, v2); |
|
134 Edge v2_v1=flowG.addEdge(v2, v1); |
|
135 Edge v1_v3=flowG.addEdge(v1, v3); |
|
136 Edge v3_v2=flowG.addEdge(v3, v2); |
|
137 Edge v2_v4=flowG.addEdge(v2, v4); |
|
138 Edge v4_v3=flowG.addEdge(v4, v3); |
|
139 Edge v3_t=flowG.addEdge(v3, t); |
|
140 Edge v4_t=flowG.addEdge(v4, t); |
|
141 |
|
142 ListGraph::EdgeMap<int> cap(flowG); |
|
143 |
|
144 cap.set(s_v1, 16); |
|
145 cap.set(s_v2, 13); |
|
146 cap.set(v1_v2, 10); |
|
147 cap.set(v2_v1, 4); |
|
148 cap.set(v1_v3, 12); |
|
149 cap.set(v3_v2, 9); |
|
150 cap.set(v2_v4, 14); |
|
151 cap.set(v4_v3, 7); |
|
152 cap.set(v3_t, 20); |
|
153 cap.set(v4_t, 4); |
|
154 |
|
155 std::cout << "on directed graph graph" << std::endl; //<< flowG; |
|
156 std::cout << "names and capacity values" << std::endl; |
|
157 for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) { |
|
158 std::cout << node_name.get(i) << ": "; |
|
159 std::cout << "out edges: "; |
|
160 for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j)) |
|
161 std::cout << node_name.get(flowG.source(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.target(j)) << " "; |
|
162 std::cout << "in edges: "; |
|
163 for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j)) |
|
164 std::cout << node_name.get(flowG.source(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.target(j)) << " "; |
|
165 std::cout << std::endl; |
|
166 } |
|
167 |
|
168 //flowG.deleteEdge(s_v1); |
|
169 //flowG.deleteEdge(s_v2); |
|
170 //flowG.deleteEdge(v1_v2); |
|
171 //flowG.deleteEdge(v1_v3); |
|
172 |
|
173 |
|
174 //flowG.setSource(v3_t, v2); |
|
175 //flowG.setTarget(v3_t, s); |
|
176 /* |
|
177 for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) { |
|
178 std::cout << node_name.get(i) << ": "; |
|
179 std::cout << "out edges: "; |
|
180 for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j)) |
|
181 std::cout << node_name.get(flowG.source(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.target(j)) << " "; |
|
182 std::cout << "in edges: "; |
|
183 for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j)) |
|
184 std::cout << node_name.get(flowG.source(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.target(j)) << " "; |
|
185 std::cout << std::endl; |
|
186 } |
|
187 |
|
188 for(EdgeIt e=flowG.first<EdgeIt>(); flowG.valid(e); flowG.next(e)) { |
|
189 std::cout << node_name.get(flowG.source(e)) << "-"<< cap.get(e) << "->" << node_name.get(flowG.target(e)) << " "; |
|
190 } |
|
191 */ |
|
192 /* |
|
193 while (flowG.valid(flowG.first<EdgeIt>())) { |
|
194 flowG.deleteEdge(flowG.first<EdgeIt>()); |
|
195 for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) { |
|
196 std::cout << node_name.get(i) << ": "; |
|
197 std::cout << "out edges: "; |
|
198 for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j)) |
|
199 std::cout << node_name.get(flowG.source(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.target(j)) << " "; |
|
200 std::cout << "in edges: "; |
|
201 for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j)) |
|
202 std::cout << node_name.get(flowG.source(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.target(j)) << " "; |
|
203 std::cout << std::endl; |
|
204 } |
|
205 } |
|
206 |
|
207 while (flowG.valid(flowG.first<NodeIt>())) { |
|
208 flowG.deleteNode(flowG.first<NodeIt>()); |
|
209 for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) { |
|
210 std::cout << node_name.get(i) << ": "; |
|
211 std::cout << "out edges: "; |
|
212 for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j)) |
|
213 std::cout << node_name.get(flowG.source(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.target(j)) << " "; |
|
214 std::cout << "in edges: "; |
|
215 for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j)) |
|
216 std::cout << node_name.get(flowG.source(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.target(j)) << " "; |
|
217 std::cout << std::endl; |
|
218 } |
|
219 } |
|
220 */ |
|
221 |
|
222 //std::cout << std::endl; |
|
223 |
|
224 |
|
225 { |
|
226 ListGraph::EdgeMap<int> flow(flowG, 0); |
|
227 MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(flowG, s, t, flow, cap); |
|
228 /* |
|
229 max_flow_test.augmentOnBlockingFlow<ListGraph>(); |
|
230 for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) { |
|
231 std::cout<<"("<<flowG.source(e)<< "-"<<flow.get(e)<<"->"<<flowG.target(e)<<") "; |
|
232 } |
|
233 std::cout<<std::endl; |
|
234 max_flow_test.augmentOnBlockingFlow<ListGraph>(); |
|
235 for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) { |
|
236 std::cout<<"("<<flowG.source(e)<< "-"<<flow.get(e)<<"->"<<flowG.target(e)<<") "; |
|
237 } |
|
238 std::cout<<std::endl;*/ |
|
239 //max_flow_test.run(); |
|
240 |
|
241 //std::cout << "maximum flow: "<< std::endl; |
|
242 while (max_flow_test.augmentOnShortestPath()) { |
|
243 for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) { |
|
244 std::cout<<"("<<flowG.source(e)<< "-"<<flow.get(e)<<"->"<<flowG.target(e)<<") "; |
|
245 } |
|
246 std::cout<<std::endl; |
|
247 } |
|
248 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
|
249 } |
|
250 /* |
|
251 { |
|
252 std::list<Node> S; |
|
253 S.push_back(s); S.push_back(v3); |
|
254 std::list<Node> T; |
|
255 T.push_back(t); |
|
256 |
|
257 ListGraph::EdgeMap<int> flow(flowG, 0); |
|
258 MaxFlow2<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(flowG, S, T, flow, cap); |
|
259 max_flow_test.run(); |
|
260 |
|
261 std::cout << "maximum flow: "<< std::endl; |
|
262 for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) { |
|
263 std::cout<<"("<<flowG.source(e)<< "-"<<flow.get(e)<<"->"<<flowG.target(e)<<") "; |
|
264 } |
|
265 std::cout<<std::endl; |
|
266 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
|
267 } |
|
268 */ |
|
269 return 0; |
|
270 } |
|