COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/max_flow_demo.cc @ 775:e46a1f0623a0

Last change on this file since 775:e46a1f0623a0 was 775:e46a1f0623a0, checked in by marci, 20 years ago

ResGraphWrapper?<Graph> is done, so does dimacs.h.

File size: 5.4 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 <hugo/max_flow.h>
11#include <augmenting_flow.h>
12//#include <preflow_res.h>
13#include <for_each_macros.h>
14#include <graph_concept.h>
15
16using namespace hugo;
17
18// Use a DIMACS max flow file as stdin.
19// max_flow_demo < dimacs_max_flow_file
20
21int main(int, char **) {
22
23  typedef SageGraph MutableGraph;
24
25  //typedef FullFeatureGraphConcept Graph;
26  //typedef SmartGraph Graph;
27  typedef SageGraph Graph;
28  typedef Graph::Node Node;
29  typedef Graph::EdgeIt EdgeIt;
30
31  Graph g;
32
33  Node s, t;
34  Graph::EdgeMap<int> cap(g);
35  //readDimacsMaxFlow(std::cin, g, s, t, cap);
36  readDimacs(std::cin, g, cap, s, t);
37  Timer ts;
38  Graph::EdgeMap<int> flow(g); //0 flow
39  MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
40    max_flow_test(g, s, t, cap, flow);
41  AugmentingFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
42    augmenting_flow_test(g, s, t, cap, flow);
43 
44  Graph::NodeMap<bool> cut(g);
45
46  {
47    std::cout << "preflow ..." << std::endl;
48    ts.reset();
49    max_flow_test.run();
50    std::cout << "elapsed time: " << ts << std::endl;
51    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
52    max_flow_test.actMinCut(cut);
53
54    FOR_EACH_LOC(Graph::EdgeIt, e, g) {
55      if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
56        std::cout << "Slackness does not hold!" << std::endl;
57      if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
58        std::cout << "Slackness does not hold!" << std::endl;
59    }
60  }
61
62  {
63    std::cout << "preflow ..." << std::endl;
64    FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
65    ts.reset();
66    max_flow_test.preflow(MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
67    std::cout << "elapsed time: " << ts << std::endl;
68    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
69
70    FOR_EACH_LOC(Graph::EdgeIt, e, g) {
71      if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
72        std::cout << "Slackness does not hold!" << std::endl;
73      if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
74        std::cout << "Slackness does not hold!" << std::endl;
75    }
76  }
77
78//   {
79//     std::cout << "wrapped preflow ..." << std::endl;
80//     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
81//     ts.reset();
82//     pre_flow_res.run();
83//     std::cout << "elapsed time: " << ts << std::endl;
84//     std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
85//   }
86
87  {
88    std::cout << "physical blocking flow augmentation ..." << std::endl;
89    FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
90    ts.reset();
91    int i=0;
92    while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
93    std::cout << "elapsed time: " << ts << std::endl;
94    std::cout << "number of augmentation phases: " << i << std::endl;
95    std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
96
97    FOR_EACH_LOC(Graph::EdgeIt, e, g) {
98      if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
99        std::cout << "Slackness does not hold!" << std::endl;
100      if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
101        std::cout << "Slackness does not hold!" << std::endl;
102    }
103  }
104
105//   {
106//     std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
107//     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
108//     ts.reset();
109//     int i=0;
110//     while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }
111//     std::cout << "elapsed time: " << ts << std::endl;
112//     std::cout << "number of augmentation phases: " << i << std::endl;
113//     std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
114
115//     FOR_EACH_LOC(Graph::EdgeIt, e, g) {
116//       if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
117//      std::cout << "Slackness does not hold!" << std::endl;
118//       if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
119//      std::cout << "Slackness does not hold!" << std::endl;
120//     }
121//   }
122
123  {
124    std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
125    FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
126    ts.reset();
127    int i=0;
128    while (augmenting_flow_test.augmentOnShortestPath()) { ++i; }
129    std::cout << "elapsed time: " << ts << std::endl;
130    std::cout << "number of augmentation phases: " << i << std::endl;
131    std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
132
133    FOR_EACH_LOC(Graph::EdgeIt, e, g) {
134      if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
135        std::cout << "Slackness does not hold!" << std::endl;
136      if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
137        std::cout << "Slackness does not hold!" << std::endl;
138    }
139  }
140
141  {
142    std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
143    FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
144    ts.reset();
145    int i=0;
146    while (augmenting_flow_test.augmentOnShortestPath2()) { ++i; }
147    std::cout << "elapsed time: " << ts << std::endl;
148    std::cout << "number of augmentation phases: " << i << std::endl;
149    std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
150
151    FOR_EACH_LOC(Graph::EdgeIt, e, g) {
152      if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
153        std::cout << "Slackness does not hold!" << std::endl;
154      if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
155        std::cout << "Slackness does not hold!" << std::endl;
156    }
157  }
158
159  return 0;
160}
Note: See TracBrowser for help on using the repository browser.