COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/edmonds_karp_demo.cc @ 465:d72e56f1730d

Last change on this file since 465:d72e56f1730d was 465:d72e56f1730d, checked in by marci, 21 years ago

mods implied by preflow mods

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