COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/edmonds_karp_demo.cc @ 333:e0a80761dfd9

Last change on this file since 333:e0a80761dfd9 was 333:e0a80761dfd9, checked in by marci, 20 years ago

makroizeles

File size: 3.4 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 <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  Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
73    pre_flow_test(G, s, t, cap, flow);
74  MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
75    max_flow_test(G, s, t, cap, flow);
76
77  {
78    std::cout << "preflow ..." << std::endl;
79    ts.reset();
80    pre_flow_test.run();
81    std::cout << "elapsed time: " << ts << std::endl;
82    std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
83  }
84
85  {
86    std::cout << "physical blocking flow augmentation ..." << std::endl;
87    FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
88    ts.reset();
89    int i=0;
90    while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
91    std::cout << "elapsed time: " << ts << std::endl;
92    std::cout << "number of augmentation phases: " << i << std::endl;
93    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
94  }
95
96  {
97    std::cout << "faster physical blocking flow augmentation ..." << std::endl;
98    FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
99    ts.reset();
100    int i=0;
101    while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
102    std::cout << "elapsed time: " << ts << std::endl;
103    std::cout << "number of augmentation phases: " << i << std::endl;
104    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
105  }
106
107  {
108    std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
109    FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
110    ts.reset();
111    int i=0;
112    while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
113    std::cout << "elapsed time: " << ts << std::endl;
114    std::cout << "number of augmentation phases: " << i << std::endl;
115    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
116  }
117
118  {
119    std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
120    FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
121    ts.reset();
122    int i=0;
123    while (max_flow_test.augmentOnShortestPath()) { ++i; }
124    std::cout << "elapsed time: " << ts << std::endl;
125    std::cout << "number of augmentation phases: " << i << std::endl;
126    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
127  }
128
129
130  return 0;
131}
Note: See TracBrowser for help on using the repository browser.