COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/edmonds_karp_demo.cc @ 332:5dc61ba30730

Last change on this file since 332:5dc61ba30730 was 330:7ac0d4e8a31c, checked in by marci, 20 years ago

In the resgraphwrapper interface, and in the constructor,
the order of FlowMap? and CapacityMap? is changed.

File size: 5.8 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  {
71    std::cout << "preflow ..." << std::endl;
72    Graph::EdgeMap<int> flow(G); //0 flow
73
74    Timer ts;
75    ts.reset();
76
77    Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
78      max_flow_test(G, s, t, cap, flow);
79    max_flow_test.run();
80//    int i=0;
81//    while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) {
82//     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
83//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
84//     }
85//     std::cout<<std::endl;
86//      ++i;
87//    }
88
89//   std::cout << "maximum flow: "<< std::endl;
90//   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
91//     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
92//   }
93//   std::cout<<std::endl;
94    std::cout << "elapsed time: " << ts << std::endl;
95//    std::cout << "number of augmentation phases: " << i << std::endl;
96    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
97  }
98
99  {
100    std::cout << "physical blocking flow augmentation ..." << std::endl;
101    Graph::EdgeMap<int> flow(G); //0 flow
102
103    Timer ts;
104    ts.reset();
105
106    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
107      max_flow_test(G, s, t, cap, flow);
108    int i=0;
109    while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) {
110//     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
111//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
112//     }
113//     std::cout<<std::endl;
114      ++i;
115    }
116
117//   std::cout << "maximum flow: "<< std::endl;
118//   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
119//     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
120//   }
121//   std::cout<<std::endl;
122    std::cout << "elapsed time: " << ts << std::endl;
123    std::cout << "number of augmentation phases: " << i << std::endl;
124    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
125  }
126
127  {
128    std::cout << "faster physical blocking flow augmentation ..." << std::endl;
129    Graph::EdgeMap<int> flow(G); //0 flow
130
131    Timer ts;
132    ts.reset();
133
134    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
135      max_flow_test(G, s, t, cap, flow);
136    int i=0;
137    while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
138//     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
139//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
140//     }
141//     std::cout<<std::endl;
142      ++i;
143    }
144
145//   std::cout << "maximum flow: "<< std::endl;
146//   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
147//     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
148//   }
149//   std::cout<<std::endl;
150    std::cout << "elapsed time: " << ts << std::endl;
151    std::cout << "number of augmentation phases: " << i << std::endl;
152    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
153  }
154
155  {
156    std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
157    Graph::EdgeMap<int> flow(G); //0 flow
158
159    Timer ts;
160    ts.reset();
161
162    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
163      max_flow_test(G, s, t, cap, flow);
164    int i=0;
165    while (max_flow_test.augmentOnBlockingFlow2()) {
166//     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
167//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
168//     }
169//     std::cout<<std::endl;
170      ++i;
171    }
172
173//   std::cout << "maximum flow: "<< std::endl;
174//   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
175//     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
176//   }
177//   std::cout<<std::endl;
178    std::cout << "elapsed time: " << ts << std::endl;
179    std::cout << "number of augmentation phases: " << i << std::endl;
180    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
181  }
182
183  {
184    std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
185    Graph::EdgeMap<int> flow(G); //0 flow
186
187    Timer ts;
188    ts.reset();
189
190    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
191      max_flow_test(G, s, t, cap, flow);
192    int i=0;
193    while (max_flow_test.augmentOnShortestPath()) {
194//     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
195//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
196//     }
197//     std::cout<<std::endl;
198      ++i;
199    }
200
201//   std::cout << "maximum flow: "<< std::endl;
202//   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
203//     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
204//   }
205//   std::cout<<std::endl;
206    std::cout << "elapsed time: " << ts << std::endl;
207    std::cout << "number of augmentation phases: " << i << std::endl;
208    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
209  }
210
211
212  return 0;
213}
Note: See TracBrowser for help on using the repository browser.