COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/max_flow_demo.cc @ 853:4cb8f31c1ff8

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