COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci_graph_demo.cc @ 151:c0e556186c55

Last change on this file since 151:c0e556186c55 was 133:0631992fe7a1, checked in by marci, 21 years ago

Dinits blocking flow added to edmonds_karp_demo.hh.

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