COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/edmonds_karp_demo.cc @ 415:679e64913c5e

Last change on this file since 415:679e64913c5e was 415:679e64913c5e, checked in by marci, 16 years ago

for igcc-3.4.0

File size: 3.8 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  PreflowRes<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
76    pre_flow_res(G, s, t, cap, flow, true);
77  MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
78    max_flow_test(G, s, t, cap, flow);
79
80  {
81    std::cout << "preflow ..." << std::endl;
82    ts.reset();
83    pre_flow_test.run();
84    std::cout << "elapsed time: " << ts << std::endl;
85    std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
86  }
87
88  {
89    std::cout << "wrapped preflow ..." << std::endl;
90    FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
91    ts.reset();
92    pre_flow_res.run();
93    std::cout << "elapsed time: " << ts << std::endl;
94    std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
95  }
96
97  {
98    std::cout << "physical blocking flow augmentation ..." << std::endl;
99    FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
100    ts.reset();
101    int i=0;
102    while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
103    std::cout << "elapsed time: " << ts << std::endl;
104    std::cout << "number of augmentation phases: " << i << std::endl;
105    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
106  }
107
108  {
109    std::cout << "faster 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.augmentOnBlockingFlow1<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 << "on-the-fly 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.augmentOnBlockingFlow2()) { ++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 shortest path 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.augmentOnShortestPath()) { ++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  return 0;
143}
Note: See TracBrowser for help on using the repository browser.