COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/edmonds_karp_demo.cc @ 174:44700ed9ffaa

Last change on this file since 174:44700ed9ffaa was 174:44700ed9ffaa, checked in by marci, 18 years ago

towards on ListGraph?, SmartGraph? compatibility

File size: 4.6 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
12using namespace hugo;
13
14// Use a DIMACS max flow file as stdin.
15// read_dimacs_demo < dimacs_max_flow_file
16
17
18//   struct Ize {
19//   };
20 
21//   struct Mize {
22//     Ize bumm;
23//   };
24
25//   template <typename B>
26//     class Huha {
27//     public:
28//       int u;
29//       B brr;
30//     };
31
32
33int main(int, char **) {
34
35  typedef ListGraph MutableGraph;
36
37  typedef SmartGraph Graph;
38  typedef Graph::Node Node;
39  typedef Graph::EdgeIt EdgeIt;
40
41
42//   Mize mize[10];
43//   Mize bize[0];
44//   Mize zize;
45//   typedef Mize Tize[0];
46
47//   std::cout << &zize << " " << sizeof(mize) << sizeof(Tize) << std::endl;
48//   std::cout << sizeof(bize) << std::endl;
49
50
51//   Huha<Tize> k;
52//   std::cout << sizeof(k) << std::endl;
53
54
55//   struct Bumm {
56//     //int a;
57//     bool b;
58//   };
59
60//   std::cout << sizeof(Bumm) << std::endl;
61
62
63  Graph G;
64  Node s, t;
65  Graph::EdgeMap<int> cap(G);
66  readDimacsMaxFlow(std::cin, G, s, t, cap);
67
68//   typedef TrivGraphWrapper<Graph> TGW;
69//   TGW gw(G);
70//   TGW::NodeIt sw;
71//   gw./*getF*/first(sw);
72//   std::cout << "p1:" << gw.nodeNum() << std::endl;
73//   gw.erase(sw);
74//   std::cout << "p2:" << gw.nodeNum() << std::endl;
75
76//   typedef const Graph cLG;
77//   typedef TrivGraphWrapper<const cLG> CTGW;
78//   CTGW cgw(G);
79//   CTGW::NodeIt csw;
80//   cgw./*getF*/first(csw);
81//   std::cout << "p1:" << cgw.nodeNum() << std::endl;
82//   //cgw.erase(csw);
83//   std::cout << "p2:" << cgw.nodeNum() << std::endl;
84
85
86  {
87    std::cout << "SmartGraph..." << std::endl;
88    std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl;
89    Graph::EdgeMap<int> flow(G); //0 flow
90
91    Timer ts;
92    ts.reset();
93
94    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
95    //max_flow_test.augmentWithBlockingFlow<Graph>();
96    int i=0;
97    while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) {
98//     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
99//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
100//     }
101//     std::cout<<std::endl;
102      ++i;
103    }
104
105//   std::cout << "maximum flow: "<< std::endl;
106//   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
107//     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
108//   }
109//   std::cout<<std::endl;
110    std::cout << "elapsed time: " << ts << std::endl;
111    std::cout << "number of augmentation phases: " << i << std::endl;
112    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
113  }
114
115  {
116    std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
117    Graph::EdgeMap<int> flow(G); //0 flow
118
119    Timer ts;
120    ts.reset();
121
122    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
123    //max_flow_test.augmentWithBlockingFlow<Graph>();
124    int i=0;
125    while (max_flow_test.augmentOnBlockingFlow2()) {
126//     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
127//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
128//     }
129//     std::cout<<std::endl;
130      ++i;
131    }
132
133//   std::cout << "maximum flow: "<< std::endl;
134//   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
135//     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
136//   }
137//   std::cout<<std::endl;
138    std::cout << "elapsed time: " << ts << std::endl;
139    std::cout << "number of augmentation phases: " << i << std::endl;
140    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
141  }
142
143  {
144    std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl;
145    Graph::EdgeMap<int> flow(G); //0 flow
146
147    Timer ts;
148    ts.reset();
149
150    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
151    //max_flow_test.augmentWithBlockingFlow<Graph>();
152    int i=0;
153    while (max_flow_test.augmentOnShortestPath()) {
154//     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
155//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
156//     }
157//     std::cout<<std::endl;
158      ++i;
159    }
160
161//   std::cout << "maximum flow: "<< std::endl;
162//   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
163//     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
164//   }
165//   std::cout<<std::endl;
166    std::cout << "elapsed time: " << ts << std::endl;
167    std::cout << "number of augmentation phases: " << i << std::endl;
168    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
169  }
170
171
172  return 0;
173}
Note: See TracBrowser for help on using the repository browser.