COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/lp/max_flow_by_lp.cc @ 1031:0b7169db694f

Last change on this file since 1031:0b7169db694f was 1031:0b7169db694f, checked in by marci, 19 years ago

:-(

File size: 6.4 KB
Line 
1// -*- c++ -*-
2#include <iostream>
3#include <fstream>
4
5#include <lemon/smart_graph.h>
6#include <lemon/list_graph.h>
7#include <lemon/dimacs.h>
8#include <lemon/time_measure.h>
9//#include <graph_wrapper.h>
10#include <lemon/preflow.h>
11#include <augmenting_flow.h>
12//#include <preflow_res.h>
13//#include <lp_solver_wrapper_2.h>
14#include <min_cost_gen_flow.h>
15
16// Use a DIMACS max flow file as stdin.
17// max_flow_demo < dimacs_max_flow_file
18
19using namespace lemon;
20
21int main(int, char **) {
22
23  typedef ListGraph MutableGraph;
24  typedef ListGraph Graph;
25  typedef Graph::Node Node;
26  typedef Graph::Edge Edge;
27  typedef Graph::EdgeIt EdgeIt;
28
29  Graph g;
30
31  Node s, t;
32  Graph::EdgeMap<int> cap(g);
33  //readDimacsMaxFlow(std::cin, g, s, t, cap);
34  readDimacs(std::cin, g, cap, s, t);
35  Timer ts;
36  Graph::EdgeMap<int> flow(g); //0 flow
37  Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
38    max_flow_test(g, s, t, cap, flow);
39  AugmentingFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
40    augmenting_flow_test(g, s, t, cap, flow);
41 
42  Graph::NodeMap<bool> cut(g);
43
44  {
45    std::cout << "preflow ..." << std::endl;
46    ts.reset();
47    max_flow_test.run();
48    std::cout << "elapsed time: " << ts << std::endl;
49    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
50    max_flow_test.minCut(cut);
51
52    for (EdgeIt e(g); e!=INVALID; ++e) {
53      if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e])
54        std::cout << "Slackness does not hold!" << std::endl;
55      if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0)
56        std::cout << "Slackness does not hold!" << std::endl;
57    }
58  }
59
60//   {
61//     std::cout << "preflow ..." << std::endl;
62//     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
63//     ts.reset();
64//     max_flow_test.preflow(Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
65//     std::cout << "elapsed time: " << ts << std::endl;
66//     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
67
68//     FOR_EACH_LOC(Graph::EdgeIt, e, g) {
69//       if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e])
70//      std::cout << "Slackness does not hold!" << std::endl;
71//       if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0)
72//      std::cout << "Slackness does not hold!" << std::endl;
73//     }
74//   }
75
76//   {
77//     std::cout << "wrapped preflow ..." << std::endl;
78//     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
79//     ts.reset();
80//     pre_flow_res.run();
81//     std::cout << "elapsed time: " << ts << std::endl;
82//     std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
83//   }
84
85  {
86    std::cout << "physical blocking flow augmentation ..." << std::endl;
87    for (EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
88    ts.reset();
89    int i=0;
90    while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
91    std::cout << "elapsed time: " << ts << std::endl;
92    std::cout << "number of augmentation phases: " << i << std::endl;
93    std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
94
95    for (EdgeIt e(g); e!=INVALID; ++e) {
96      if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e])
97        std::cout << "Slackness does not hold!" << std::endl;
98      if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0)
99        std::cout << "Slackness does not hold!" << std::endl;
100    }
101  }
102
103//   {
104//     std::cout << "faster physical blocking flow augmentation ..." << std::endl;
105//     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
106//     ts.reset();
107//     int i=0;
108//     while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
109//     std::cout << "elapsed time: " << ts << std::endl;
110//     std::cout << "number of augmentation phases: " << i << std::endl;
111//     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
112//   }
113
114  {
115    std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
116    for (EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
117    ts.reset();
118    int i=0;
119    while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }
120    std::cout << "elapsed time: " << ts << std::endl;
121    std::cout << "number of augmentation phases: " << i << std::endl;
122    std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
123
124    for (EdgeIt e(g); e!=INVALID; ++e) {
125      if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e])
126        std::cout << "Slackness does not hold!" << std::endl;
127      if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0)
128        std::cout << "Slackness does not hold!" << std::endl;
129    }
130  }
131
132//   {
133//     std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
134//     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
135//     ts.reset();
136//     int i=0;
137//     while (augmenting_flow_test.augmentOnShortestPath()) { ++i; }
138//     std::cout << "elapsed time: " << ts << std::endl;
139//     std::cout << "number of augmentation phases: " << i << std::endl;
140//     std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
141
142//     FOR_EACH_LOC(Graph::EdgeIt, e, g) {
143//       if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e])
144//      std::cout << "Slackness does not hold!" << std::endl;
145//       if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0)
146//      std::cout << "Slackness does not hold!" << std::endl;
147//     }
148//   }
149
150//   {
151//     std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
152//     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
153//     ts.reset();
154//     int i=0;
155//     while (augmenting_flow_test.augmentOnShortestPath2()) { ++i; }
156//     std::cout << "elapsed time: " << ts << std::endl;
157//     std::cout << "number of augmentation phases: " << i << std::endl;
158//     std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
159
160//     FOR_EACH_LOC(Graph::EdgeIt, e, g) {
161//       if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e])
162//      std::cout << "Slackness does not hold!" << std::endl;
163//       if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0)
164//      std::cout << "Slackness does not hold!" << std::endl;
165//     }
166//   }
167
168  ts.reset();
169
170  Edge e=g.addEdge(t, s);
171  Graph::EdgeMap<int> cost(g, 0);
172  cost.set(e, -1);
173  cap.set(e, 10000);
174  typedef ConstMap<Node, int> Excess;
175  Excess excess(0);
176  typedef ConstMap<Edge, int> LCap;
177  LCap lcap(0);
178
179  MinCostGenFlow<Graph, int, Excess, LCap>
180    min_cost(g, excess, lcap, cap, flow, cost);
181  min_cost.feasible();
182  min_cost.runByLP();
183
184  std::cout << "elapsed time: " << ts << std::endl;
185  std::cout << "flow value: "<< flow[e] << std::endl;
186}
Note: See TracBrowser for help on using the repository browser.