COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/max_flow_demo.cc @ 1074:4a24a46407db

Last change on this file since 1074:4a24a46407db was 986:e997802b855c, checked in by Alpar Juttner, 19 years ago

Naming changes:

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