COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/edmonds_karp_demo.cc @ 188:ad1417e74042

Last change on this file since 188:ad1417e74042 was 188:ad1417e74042, checked in by marci, 17 years ago

.

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