COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/max_flow_demo.cc @ 615:b6b31b75b522

Last change on this file since 615:b6b31b75b522 was 577:e8703f0a6e2f, checked in by marci, 20 years ago

top-sort, dimacs mods.

File size: 4.0 KB
Line 
1// -*- c++ -*-
2#include <iostream>
3#include <fstream>
4
5#include <list_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 <max_flow.h>
11//#include <preflow_res.h>
12#include <for_each_macros.h>
13
14using namespace hugo;
15
16// Use a DIMACS max flow file as stdin.
17// read_dimacs_demo < dimacs_max_flow_file
18
19
20//   struct Ize {
21//   };
22 
23//   struct Mize {
24//     Ize bumm;
25//   };
26
27//   template <typename B>
28//     class Huha {
29//     public:
30//       int u;
31//       B brr;
32//     };
33
34
35int main(int, char **) {
36
37  typedef ListGraph MutableGraph;
38
39  typedef SmartGraph Graph;
40  //  typedef ListGraph Graph;
41  typedef Graph::Node Node;
42  typedef Graph::EdgeIt EdgeIt;
43
44
45//   Mize mize[10];
46//   Mize bize[0];
47//   Mize zize;
48//   typedef Mize Tize[0];
49
50//   std::cout << &zize << " " << sizeof(mize) << sizeof(Tize) << std::endl;
51//   std::cout << sizeof(bize) << std::endl;
52
53
54//   Huha<Tize> k;
55//   std::cout << sizeof(k) << std::endl;
56
57
58//   struct Bumm {
59//     //int a;
60//     bool b;
61//   };
62
63//   std::cout << sizeof(Bumm) << std::endl;
64
65
66  Graph g;
67  Node s, t;
68  Graph::EdgeMap<int> cap(g);
69  //readDimacsMaxFlow(std::cin, g, s, t, cap);
70  readDimacs(std::cin, g, cap, s, t);
71  Timer ts;
72  Graph::EdgeMap<int> flow(g); //0 flow
73  MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
74    max_flow_test(g, s, t, cap, flow);
75
76  {
77    std::cout << "preflow ..." << std::endl;
78    ts.reset();
79    max_flow_test.run();
80    std::cout << "elapsed time: " << ts << std::endl;
81    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
82  }
83
84  {
85    std::cout << "preflow ..." << std::endl;
86    FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
87    ts.reset();
88    max_flow_test.preflow(MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
89    std::cout << "elapsed time: " << ts << std::endl;
90    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
91  }
92
93//   {
94//     std::cout << "wrapped preflow ..." << std::endl;
95//     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
96//     ts.reset();
97//     pre_flow_res.run();
98//     std::cout << "elapsed time: " << ts << std::endl;
99//     std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
100//   }
101
102  {
103    std::cout << "physical blocking flow augmentation ..." << std::endl;
104    FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
105    ts.reset();
106    int i=0;
107    while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
108    std::cout << "elapsed time: " << ts << std::endl;
109    std::cout << "number of augmentation phases: " << i << std::endl;
110    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
111  }
112
113//   {
114//     std::cout << "faster physical blocking flow augmentation ..." << std::endl;
115//     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
116//     ts.reset();
117//     int i=0;
118//     while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
119//     std::cout << "elapsed time: " << ts << std::endl;
120//     std::cout << "number of augmentation phases: " << i << std::endl;
121//     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
122//   }
123
124  {
125    std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
126    FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
127    ts.reset();
128    int i=0;
129    while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
130    std::cout << "elapsed time: " << ts << std::endl;
131    std::cout << "number of augmentation phases: " << i << std::endl;
132    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
133  }
134
135  {
136    std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
137    FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
138    ts.reset();
139    int i=0;
140    while (max_flow_test.augmentOnShortestPath()) { ++i; }
141    std::cout << "elapsed time: " << ts << std::endl;
142    std::cout << "number of augmentation phases: " << i << std::endl;
143    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
144  }
145
146
147  return 0;
148}
Note: See TracBrowser for help on using the repository browser.