COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/max_flow_demo.cc @ 854:baf0b6e40211

Last change on this file since 854:baf0b6e40211 was 854:baf0b6e40211, checked in by marci, 17 years ago

correction of SubGraphWrapper? bug.

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