COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/max_flow_demo.cc @ 646:bd7a69231cf8

Last change on this file since 646:bd7a69231cf8 was 646:bd7a69231cf8, checked in by marci, 17 years ago

max_flow.h: status flags for actMinCut
leda_graph_wrapper.h: NodeMapWrapper?, EdgeMapWrapper?

File size: 6.1 KB
Line 
1// -*- c++ -*-
2#include <iostream>
3#include <fstream>
4
5#include <sage_graph.h>
6#include <hugo/smart_graph.h>
7#include <hugo/dimacs.h>
8#include <hugo/time_measure.h>
9//#include <graph_wrapper.h>
10#include <max_flow.h>
11//#include <preflow_res.h>
12#include <hugo/for_each_macros.h>
13
14using namespace hugo;
15
16// Use a DIMACS max flow file as stdin.
17// read_dimacs_demo < dimacs_max_flow_file
18
19
20//   struct Ize {
21//   };
22 
23//   struct Mize {
24//     Ize bumm;
25//   };
26
27//   template <typename B>
28//     class Huha {
29//     public:
30//       int u;
31//       B brr;
32//     };
33
34
35int main(int, char **) {
36
37  typedef SageGraph MutableGraph;
38
39  typedef SmartGraph Graph;
40  //  typedef SageGraph Graph;
41  typedef Graph::Node Node;
42  typedef Graph::EdgeIt EdgeIt;
43
44
45//   Mize mize[10];
46//   Mize bize[0];
47//   Mize zize;
48//   typedef Mize Tize[0];
49
50//   std::cout << &zize << " " << sizeof(mize) << sizeof(Tize) << std::endl;
51//   std::cout << sizeof(bize) << std::endl;
52
53
54//   Huha<Tize> k;
55//   std::cout << sizeof(k) << std::endl;
56
57
58//   struct Bumm {
59//     //int a;
60//     bool b;
61//   };
62
63//   std::cout << sizeof(Bumm) << std::endl;
64
65
66  Graph g;
67  Node s, t;
68  Graph::EdgeMap<int> cap(g);
69  //readDimacsMaxFlow(std::cin, g, s, t, cap);
70  readDimacs(std::cin, g, cap, s, t);
71  Timer ts;
72  Graph::EdgeMap<int> flow(g); //0 flow
73  MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
74    max_flow_test(g, s, t, cap, flow);
75  Graph::NodeMap<bool> cut(g);
76
77  {
78    std::cout << "preflow ..." << std::endl;
79    ts.reset();
80    max_flow_test.run();
81    std::cout << "elapsed time: " << ts << std::endl;
82    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
83    max_flow_test.actMinCut(cut);
84
85    FOR_EACH_LOC(Graph::EdgeIt, e, g) {
86      if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
87        std::cout << "Slackness does not hold!" << std::endl;
88      if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
89        std::cout << "Slackness does not hold!" << std::endl;
90    }
91  }
92
93  {
94    std::cout << "preflow ..." << std::endl;
95    FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
96    ts.reset();
97    max_flow_test.preflow(MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
98    std::cout << "elapsed time: " << ts << std::endl;
99    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
100
101    FOR_EACH_LOC(Graph::EdgeIt, e, g) {
102      if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
103        std::cout << "Slackness does not hold!" << std::endl;
104      if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
105        std::cout << "Slackness does not hold!" << std::endl;
106    }
107  }
108
109//   {
110//     std::cout << "wrapped preflow ..." << std::endl;
111//     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
112//     ts.reset();
113//     pre_flow_res.run();
114//     std::cout << "elapsed time: " << ts << std::endl;
115//     std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
116//   }
117
118  {
119    std::cout << "physical blocking flow augmentation ..." << std::endl;
120    FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
121    ts.reset();
122    int i=0;
123    while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
124    std::cout << "elapsed time: " << ts << std::endl;
125    std::cout << "number of augmentation phases: " << i << std::endl;
126    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
127
128    FOR_EACH_LOC(Graph::EdgeIt, e, g) {
129      if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
130        std::cout << "Slackness does not hold!" << std::endl;
131      if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
132        std::cout << "Slackness does not hold!" << std::endl;
133    }
134  }
135
136//   {
137//     std::cout << "faster physical blocking flow augmentation ..." << std::endl;
138//     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
139//     ts.reset();
140//     int i=0;
141//     while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
142//     std::cout << "elapsed time: " << ts << std::endl;
143//     std::cout << "number of augmentation phases: " << i << std::endl;
144//     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
145//   }
146
147  {
148    std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
149    FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
150    ts.reset();
151    int i=0;
152    while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
153    std::cout << "elapsed time: " << ts << std::endl;
154    std::cout << "number of augmentation phases: " << i << std::endl;
155    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
156
157    FOR_EACH_LOC(Graph::EdgeIt, e, g) {
158      if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
159        std::cout << "Slackness does not hold!" << std::endl;
160      if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
161        std::cout << "Slackness does not hold!" << std::endl;
162    }
163  }
164
165  {
166    std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
167    FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
168    ts.reset();
169    int i=0;
170    while (max_flow_test.augmentOnShortestPath()) { ++i; }
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    FOR_EACH_LOC(Graph::EdgeIt, e, g) {
176      if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
177        std::cout << "Slackness does not hold!" << std::endl;
178      if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
179        std::cout << "Slackness does not hold!" << std::endl;
180    }
181  }
182
183  {
184    std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
185    FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
186    ts.reset();
187    int i=0;
188    while (max_flow_test.augmentOnShortestPath2()) { ++i; }
189    std::cout << "elapsed time: " << ts << std::endl;
190    std::cout << "number of augmentation phases: " << i << std::endl;
191    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
192
193    FOR_EACH_LOC(Graph::EdgeIt, e, g) {
194      if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
195        std::cout << "Slackness does not hold!" << std::endl;
196      if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
197        std::cout << "Slackness does not hold!" << std::endl;
198    }
199  }
200
201  return 0;
202}
Note: See TracBrowser for help on using the repository browser.