COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/max_flow_demo.cc @ 548:61898ac9e9dc

Last change on this file since 548:61898ac9e9dc was 480:4fb0d1e166ea, checked in by marci, 21 years ago

corrections

File size: 3.9 KB
Line 
1// -*- c++ -*-
2#include <iostream>
3#include <fstream>
4
5#include <list_graph.h>
6#include <smart_graph.h>
7#include <dimacs.h>
8#include <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  Timer ts;
71  Graph::EdgeMap<int> flow(G); //0 flow
72  MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
73    max_flow_test(G, s, t, cap, flow);
74
75  {
76    std::cout << "preflow ..." << std::endl;
77    ts.reset();
78    max_flow_test.run();
79    std::cout << "elapsed time: " << ts << std::endl;
80    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
81  }
82
83  {
84    std::cout << "preflow ..." << std::endl;
85    FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
86    ts.reset();
87    max_flow_test.preflow(MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
88    std::cout << "elapsed time: " << ts << std::endl;
89    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
90  }
91
92//   {
93//     std::cout << "wrapped preflow ..." << std::endl;
94//     FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
95//     ts.reset();
96//     pre_flow_res.run();
97//     std::cout << "elapsed time: " << ts << std::endl;
98//     std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
99//   }
100
101  {
102    std::cout << "physical blocking flow augmentation ..." << std::endl;
103    FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
104    ts.reset();
105    int i=0;
106    while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
107    std::cout << "elapsed time: " << ts << std::endl;
108    std::cout << "number of augmentation phases: " << i << std::endl;
109    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
110  }
111
112//   {
113//     std::cout << "faster physical blocking flow augmentation ..." << std::endl;
114//     FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
115//     ts.reset();
116//     int i=0;
117//     while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
118//     std::cout << "elapsed time: " << ts << std::endl;
119//     std::cout << "number of augmentation phases: " << i << std::endl;
120//     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
121//   }
122
123  {
124    std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
125    FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
126    ts.reset();
127    int i=0;
128    while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
129    std::cout << "elapsed time: " << ts << std::endl;
130    std::cout << "number of augmentation phases: " << i << std::endl;
131    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
132  }
133
134  {
135    std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
136    FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
137    ts.reset();
138    int i=0;
139    while (max_flow_test.augmentOnShortestPath()) { ++i; }
140    std::cout << "elapsed time: " << ts << std::endl;
141    std::cout << "number of augmentation phases: " << i << std::endl;
142    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
143  }
144
145
146  return 0;
147}
Note: See TracBrowser for help on using the repository browser.