COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/edmonds_karp_demo.cc @ 311:6635b11938fe

Last change on this file since 311:6635b11938fe was 311:6635b11938fe, checked in by marci, 17 years ago

gw

File size: 6.3 KB
Line 
1// -*- c++ -*-
2#include <iostream>
3#include <fstream>
4
5#include <list_graph.h>
6#include <smart_graph.h>
7#include <dimacs.h>
8#include <edmonds_karp.h>
9#include <time_measure.h>
10//#include <graph_wrapper.h>
11#include <preflow.h>
12
13using namespace hugo;
14
15// Use a DIMACS max flow file as stdin.
16// read_dimacs_demo < dimacs_max_flow_file
17
18
19//   struct Ize {
20//   };
21 
22//   struct Mize {
23//     Ize bumm;
24//   };
25
26//   template <typename B>
27//     class Huha {
28//     public:
29//       int u;
30//       B brr;
31//     };
32
33
34int main(int, char **) {
35
36  typedef ListGraph MutableGraph;
37
38  typedef SmartGraph Graph;
39  //typedef ListGraph Graph;
40  typedef Graph::Node Node;
41  typedef Graph::EdgeIt EdgeIt;
42
43
44//   Mize mize[10];
45//   Mize bize[0];
46//   Mize zize;
47//   typedef Mize Tize[0];
48
49//   std::cout << &zize << " " << sizeof(mize) << sizeof(Tize) << std::endl;
50//   std::cout << sizeof(bize) << std::endl;
51
52
53//   Huha<Tize> k;
54//   std::cout << sizeof(k) << std::endl;
55
56
57//   struct Bumm {
58//     //int a;
59//     bool b;
60//   };
61
62//   std::cout << sizeof(Bumm) << std::endl;
63
64
65  Graph G;
66  Node s, t;
67  Graph::EdgeMap<int> cap(G);
68  readDimacsMaxFlow(std::cin, G, s, t, cap);
69
70//   typedef TrivGraphWrapper<Graph> TGW;
71//   TGW gw(G);
72//   TGW::NodeIt sw;
73//   gw./*getF*/first(sw);
74//   std::cout << "p1:" << gw.nodeNum() << std::endl;
75//   gw.erase(sw);
76//   std::cout << "p2:" << gw.nodeNum() << std::endl;
77
78//   typedef const Graph cLG;
79//   typedef TrivGraphWrapper<const cLG> CTGW;
80//   CTGW cgw(G);
81//   CTGW::NodeIt csw;
82//   cgw./*getF*/first(csw);
83//   std::cout << "p1:" << cgw.nodeNum() << std::endl;
84//   //cgw.erase(csw);
85//   std::cout << "p2:" << cgw.nodeNum() << std::endl;
86
87  {
88    std::cout << "preflow ..." << std::endl;
89    Graph::EdgeMap<int> flow(G); //0 flow
90
91    Timer ts;
92    ts.reset();
93
94    Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
95      max_flow_test(G, s, t, cap, flow);
96    max_flow_test.run();
97//    int i=0;
98//    while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) {
99//     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
100//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
101//     }
102//     std::cout<<std::endl;
103//      ++i;
104//    }
105
106//   std::cout << "maximum flow: "<< std::endl;
107//   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
108//     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
109//   }
110//   std::cout<<std::endl;
111    std::cout << "elapsed time: " << ts << std::endl;
112//    std::cout << "number of augmentation phases: " << i << std::endl;
113    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
114  }
115
116  {
117    std::cout << "physical blocking flow augmentation ..." << std::endl;
118    Graph::EdgeMap<int> flow(G); //0 flow
119
120    Timer ts;
121    ts.reset();
122
123    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
124      max_flow_test(G, s, t, flow, cap);
125    int i=0;
126    while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) {
127//     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
128//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
129//     }
130//     std::cout<<std::endl;
131      ++i;
132    }
133
134//   std::cout << "maximum flow: "<< std::endl;
135//   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
136//     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
137//   }
138//   std::cout<<std::endl;
139    std::cout << "elapsed time: " << ts << std::endl;
140    std::cout << "number of augmentation phases: " << i << std::endl;
141    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
142  }
143
144  {
145    std::cout << "faster physical blocking flow augmentation ..." << std::endl;
146    Graph::EdgeMap<int> flow(G); //0 flow
147
148    Timer ts;
149    ts.reset();
150
151    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
152      max_flow_test(G, s, t, flow, cap);
153    int i=0;
154    while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
155//     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
156//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
157//     }
158//     std::cout<<std::endl;
159      ++i;
160    }
161
162//   std::cout << "maximum flow: "<< std::endl;
163//   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
164//     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
165//   }
166//   std::cout<<std::endl;
167    std::cout << "elapsed time: " << ts << std::endl;
168    std::cout << "number of augmentation phases: " << i << std::endl;
169    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
170  }
171
172  {
173    std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
174    Graph::EdgeMap<int> flow(G); //0 flow
175
176    Timer ts;
177    ts.reset();
178
179    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
180      max_flow_test(G, s, t, flow, cap);
181    int i=0;
182    while (max_flow_test.augmentOnBlockingFlow2()) {
183//     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
184//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
185//     }
186//     std::cout<<std::endl;
187      ++i;
188    }
189
190//   std::cout << "maximum flow: "<< std::endl;
191//   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
192//     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
193//   }
194//   std::cout<<std::endl;
195    std::cout << "elapsed time: " << ts << std::endl;
196    std::cout << "number of augmentation phases: " << i << std::endl;
197    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
198  }
199
200  {
201    std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
202    Graph::EdgeMap<int> flow(G); //0 flow
203
204    Timer ts;
205    ts.reset();
206
207    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
208      max_flow_test(G, s, t, flow, cap);
209    int i=0;
210    while (max_flow_test.augmentOnShortestPath()) {
211//     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
212//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
213//     }
214//     std::cout<<std::endl;
215      ++i;
216    }
217
218//   std::cout << "maximum flow: "<< std::endl;
219//   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
220//     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
221//   }
222//   std::cout<<std::endl;
223    std::cout << "elapsed time: " << ts << std::endl;
224    std::cout << "number of augmentation phases: " << i << std::endl;
225    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
226  }
227
228
229  return 0;
230}
Note: See TracBrowser for help on using the repository browser.