COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/preflow_bug.cc @ 1153:4b0468de3a31

Last change on this file since 1153:4b0468de3a31 was 986:e997802b855c, checked in by Alpar Juttner, 16 years ago

Naming changes:

  • head -> target
  • tail -> source
File size: 7.8 KB
Line 
1// -*- c++ -*-
2#include <iostream>
3#include <fstream>
4
5#include <sage_graph.h>
6#include <lemon/smart_graph.h>
7#include <lemon/dimacs.h>
8//#include <lemon/time_measure.h>
9//#include <graph_wrapper.h>
10#include <lemon/max_flow.h>
11//#include <preflow_res.h>
12#include <for_each_macros.h>
13#include <graph_concept.h>
14
15using std::cout;
16using std::endl;
17
18using namespace lemon;
19
20// Use a DIMACS min cost flow file as stdin.
21// read_dimacs_demo < dimacs_max_flow_file
22
23int main(int, char **) {
24
25  //typedef SageGraph MutableGraph;
26  //typedef FullFeatureGraphConcept Graph;
27  //typedef SmartGraph Graph;
28  typedef SageGraph Graph;
29  typedef Graph::Node Node;
30  typedef Graph::EdgeIt EdgeIt;
31
32  Graph g;
33
34  Node s, t;
35  Graph::EdgeMap<int> cap(g);
36  Graph::EdgeMap<int> flow(g); //0 flow
37  //readDimacs(std::cin, g, cap, s, t);
38  readDimacs(std::cin, g, cap, s, t, flow);
39//  Timer ts;
40  MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
41    max_flow_test(g, s, t, cap, flow);
42 
43  Graph::NodeMap<bool> cut(g);
44
45  {
46    Graph::EdgeIt e;
47    for (g.first(e); g.valid(e); g.next(e))
48      cout << 1+g.id(g.source(e)) << "->" << 1+g.id(g.target(e)) << " cap: " << cap[e] << " preflow: " << flow[e] << endl;
49  }
50  {
51    Graph::NodeIt n;
52    for (g.first(n); g.valid(n); g.next(n)) {
53      int a=0;
54      {
55        Graph::InEdgeIt e;
56        for (g.first(e, n); g.valid(e); g.next(e)) a+=flow[e];
57      }
58      {
59        Graph::OutEdgeIt e;
60        for (g.first(e, n); g.valid(e); g.next(e)) a-=flow[e];
61      }
62      cout << 1+g.id(n) << " excess: " << a << endl;
63    }
64  }
65
66
67  {
68//    std::cout << "preflow ..." << std::endl;
69//    ts.reset();
70    max_flow_test.preflowPhase1(MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::PRE_FLOW);
71//    std::cout << "elapsed time: " << ts << std::endl;
72    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
73    std::cout << "flow value 2: "<< max_flow_test.flowValue2() << std::endl;
74    max_flow_test.actMinCut(cut);
75   
76    Graph::EdgeIt e;
77    for (g.first(e); g.valid(e); g.next(e)) {
78      if (cut[g.source(e)] && !cut[g.target(e)]) {
79        cout << 1+g.id(g.source(e)) << "->" << 1+g.id(g.target(e))
80             << "(forward edge) flow: " << flow[e]
81             << " cap: " << cap[e]<< endl;
82        if (flow[e]!=cap[e])
83        std::cout << "Slackness does not hold!" << std::endl;
84      }
85      if (!cut[g.source(e)] && cut[g.target(e)]) {
86        cout << 1+g.id(g.source(e)) << "->" << 1+g.id(g.target(e))
87             << "(backward edge) flow: " << flow[e] << endl;
88        if (flow[e]!=0)
89        std::cout << "Slackness does not hold!" << std::endl;
90      }
91    }
92    Graph::NodeIt n;
93    for (g.first(n); g.valid(n); g.next(n)) {
94      if (cut[n])
95        cout << "in cut: " << 1+g.id(n) << endl;
96    }
97  }
98
99//   {
100//     std::cout << "preflow ..." << std::endl;
101//     ts.reset();
102//     max_flow_test.run();
103//     std::cout << "elapsed time: " << ts << std::endl;
104//     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
105//     max_flow_test.actMinCut(cut);
106
107//     FOR_EACH_LOC(Graph::EdgeIt, e, g) {
108//       if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e])
109//      std::cout << "Slackness does not hold!" << std::endl;
110//       if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0)
111//      std::cout << "Slackness does not hold!" << std::endl;
112//     }
113//   }
114
115//   {
116//     std::cout << "preflow ..." << std::endl;
117//     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
118//     ts.reset();
119//     max_flow_test.preflow(MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
120//     std::cout << "elapsed time: " << ts << std::endl;
121//     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
122
123//     FOR_EACH_LOC(Graph::EdgeIt, e, g) {
124//       if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e])
125//      std::cout << "Slackness does not hold!" << std::endl;
126//       if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0)
127//      std::cout << "Slackness does not hold!" << std::endl;
128//     }
129//   }
130
131// //   {
132// //     std::cout << "wrapped preflow ..." << std::endl;
133// //     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
134// //     ts.reset();
135// //     pre_flow_res.run();
136// //     std::cout << "elapsed time: " << ts << std::endl;
137// //     std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
138// //   }
139
140//   {
141//     std::cout << "physical blocking flow augmentation ..." << std::endl;
142//     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
143//     ts.reset();
144//     int i=0;
145//     while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
146//     std::cout << "elapsed time: " << ts << std::endl;
147//     std::cout << "number of augmentation phases: " << i << std::endl;
148//     std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
149
150//     FOR_EACH_LOC(Graph::EdgeIt, e, g) {
151//       if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e])
152//      std::cout << "Slackness does not hold!" << std::endl;
153//       if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0)
154//      std::cout << "Slackness does not hold!" << std::endl;
155//     }
156//   }
157
158// //   {
159// //     std::cout << "faster physical blocking flow augmentation ..." << std::endl;
160// //     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
161// //     ts.reset();
162// //     int i=0;
163// //     while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
164// //     std::cout << "elapsed time: " << ts << std::endl;
165// //     std::cout << "number of augmentation phases: " << i << std::endl;
166// //     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
167// //   }
168
169//   {
170//     std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
171//     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
172//     ts.reset();
173//     int i=0;
174//     while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }
175//     std::cout << "elapsed time: " << ts << std::endl;
176//     std::cout << "number of augmentation phases: " << i << std::endl;
177//     std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
178
179//     FOR_EACH_LOC(Graph::EdgeIt, e, g) {
180//       if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e])
181//      std::cout << "Slackness does not hold!" << std::endl;
182//       if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0)
183//      std::cout << "Slackness does not hold!" << std::endl;
184//     }
185//   }
186
187//   {
188//     std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
189//     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
190//     ts.reset();
191//     int i=0;
192//     while (augmenting_flow_test.augmentOnShortestPath()) { ++i; }
193//     std::cout << "elapsed time: " << ts << std::endl;
194//     std::cout << "number of augmentation phases: " << i << std::endl;
195//     std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
196
197//     FOR_EACH_LOC(Graph::EdgeIt, e, g) {
198//       if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e])
199//      std::cout << "Slackness does not hold!" << std::endl;
200//       if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0)
201//      std::cout << "Slackness does not hold!" << std::endl;
202//     }
203//   }
204
205//   {
206//     std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
207//     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
208//     ts.reset();
209//     int i=0;
210//     while (augmenting_flow_test.augmentOnShortestPath2()) { ++i; }
211//     std::cout << "elapsed time: " << ts << std::endl;
212//     std::cout << "number of augmentation phases: " << i << std::endl;
213//     std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
214
215//     FOR_EACH_LOC(Graph::EdgeIt, e, g) {
216//       if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e])
217//      std::cout << "Slackness does not hold!" << std::endl;
218//       if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0)
219//      std::cout << "Slackness does not hold!" << std::endl;
220//     }
221//   }
222
223  return 0;
224}
Note: See TracBrowser for help on using the repository browser.