COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/jacint/flow_test.cc @ 105:a3c73e9b9b2e

Last change on this file since 105:a3c73e9b9b2e was 105:a3c73e9b9b2e, checked in by Alpar Juttner, 21 years ago

marci -> hugo replacements
resize -> update replacements

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