COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/max_flow_demo.cc @ 652:4dfa1f79bf3e

Last change on this file since 652:4dfa1f79bf3e was 652:4dfa1f79bf3e, checked in by marci, 17 years ago

misc

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