COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/jacint/edmonds.cc @ 497:500456d50d21

Last change on this file since 497:500456d50d21 was 494:e42f56e7ad93, checked in by jacint, 20 years ago

Felkesz kod!

File size: 5.3 KB
Line 
1#include <iostream>
2#include <vector>
3#include <string>
4
5#include <list_graph.h>
6#include <edmonds.h>
7
8using namespace hugo;
9
10int main (int, char*[])
11{
12  typedef ListGraph::NodeIt NodeIt;
13  typedef ListGraph::EdgeIt EdgeIt;
14  typedef ListGraph::Node Node;
15  typedef ListGraph::Edge Edge;
16  typedef ListGraph::OutEdgeIt OutEdgeIt;
17  typedef ListGraph::InEdgeIt InEdgeIt;
18 
19  ListGraph flow_test;
20 
21  /*    //Ahuja könyv példája, maxflowvalue=13*/
22  Node s=flow_test.addNode();
23  Node v1=flow_test.addNode();
24  Node v2=flow_test.addNode();
25  Node v3=flow_test.addNode();
26  Node v4=flow_test.addNode();
27  Node v5=flow_test.addNode();
28  Node t=flow_test.addNode();
29 
30  ListGraph::NodeMap<std::string> Node_name(flow_test);
31  Node_name.set(s, "s");
32  Node_name.set(v1, "v1");
33  Node_name.set(v2, "v2");
34  Node_name.set(v3, "v3");
35  Node_name.set(v4, "v4");
36  Node_name.set(v5, "v5");
37  Node_name.set(t, "t");
38
39  Edge s_v1=flow_test.addEdge(s, v1);
40  Edge s_v2=flow_test.addEdge(s, v2);
41  Edge s_v3=flow_test.addEdge(s, v3);
42  Edge v2_v4=flow_test.addEdge(v2, v4);
43  Edge v2_v5=flow_test.addEdge(v2, v5);
44  Edge v3_v5=flow_test.addEdge(v3, v5);
45  Edge v4_t=flow_test.addEdge(v4, t);
46  Edge v5_t=flow_test.addEdge(v5, t);
47  Edge v2_s=flow_test.addEdge(v2, s);
48 
49   ListGraph::EdgeMap<int> cap(flow_test); 
50  cap.set(s_v1, 0);
51  cap.set(s_v2, 10);
52  cap.set(s_v3, 10);
53 cap.set(v2_v4, 5);
54  cap.set(v2_v5, 8);
55  cap.set(v3_v5, 5);
56  cap.set(v4_t, 8);
57  cap.set(v5_t, 8);
58  cap.set(v2_s, 0);
59 
60
61  Edmonds<ListGraph> edmonds(flow_test);
62  std::vector<Edge> matching(0);
63  std::cout<<  edmonds.run(matching);
64
65 
66  /*  //Marci példája, maxflowvalue=23
67    Node s=flow_test.addNode();
68  Node v1=flow_test.addNode();
69  Node v2=flow_test.addNode();
70  Node v3=flow_test.addNode();
71  Node v4=flow_test.addNode();
72  Node t=flow_test.addNode();
73  Node z=flow_test.addNode();
74
75 
76   ListGraph::NodeMap<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(z, "z");
84
85  Edge s_v1=flow_test.addEdge(s, v1);
86  Edge s_v2=flow_test.addEdge(s, v2);
87  Edge v1_v2=flow_test.addEdge(v1, v2);
88  Edge v2_v1=flow_test.addEdge(v2, v1);
89  Edge v1_v3=flow_test.addEdge(v1, v3);
90  Edge v3_v2=flow_test.addEdge(v3, v2);
91  Edge v2_v4=flow_test.addEdge(v2, v4);
92  Edge v4_v3=flow_test.addEdge(v4, v3);
93  Edge v3_t=flow_test.addEdge(v3, t);
94  Edge v4_t=flow_test.addEdge(v4, t);
95  Edge v3_v3=flow_test.addEdge(v3, v3);
96  Edge s_z=flow_test.addEdge(s, z);
97  //  Edge v2_s=flow_test.addEdge(v2, s);
98 
99
100
101   ListGraph::EdgeMap<int> cap(flow_test); 
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_z, 4);
114  //  cap.set(v2_s, 0);
115
116  */
117
118  //pelda 3, maxflowvalue=4
119  /*      Node s=flow_test.addNode();
120  Node v1=flow_test.addNode();
121  Node v2=flow_test.addNode();
122  Node t=flow_test.addNode();
123  Node 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  Edge s_v1=flow_test.addEdge(s, v1);
133  Edge v1_v2=flow_test.addEdge(v1, v2);
134  Edge v2_t=flow_test.addEdge(v2, t);
135  Edge v1_v1=flow_test.addEdge(v1, v1);
136  Edge 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  return 0;
211}
212
213
214
215
216
217
218
219
220
Note: See TracBrowser for help on using the repository browser.