COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/edmonds_karp_demo.cc @ 305:6720705c9095

Last change on this file since 305:6720705c9095 was 305:6720705c9095, checked in by marci, 20 years ago

.

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