COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/edmonds_karp_demo.cc @ 224:5bc1c83257f8

Last change on this file since 224:5bc1c83257f8 was 206:47f62d789fe7, checked in by marci, 20 years ago

.

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