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, 20 years ago

.

File size: 4.7 KB
RevLine 
[174]1// -*- c++ -*-
[73]2#include <iostream>
3#include <fstream>
4
[174]5#include <list_graph.h>
6#include <smart_graph.h>
7#include <dimacs.h>
8#include <edmonds_karp.h>
[73]9#include <time_measure.h>
[155]10#include <graph_wrapper.h>
[73]11
[105]12using namespace hugo;
[73]13
14// Use a DIMACS max flow file as stdin.
15// read_dimacs_demo < dimacs_max_flow_file
[139]16
[174]17
18//   struct Ize {
19//   };
[139]20 
[174]21//   struct Mize {
22//     Ize bumm;
23//   };
[139]24
[174]25//   template <typename B>
26//     class Huha {
27//     public:
28//       int u;
29//       B brr;
30//     };
31
[139]32
[73]33int main(int, char **) {
34
[174]35  typedef ListGraph MutableGraph;
[139]36
[188]37//  typedef SmartGraph Graph;
38  typedef ListGraph Graph;
[174]39  typedef Graph::Node Node;
40  typedef Graph::EdgeIt EdgeIt;
[139]41
42
[174]43//   Mize mize[10];
44//   Mize bize[0];
45//   Mize zize;
46//   typedef Mize Tize[0];
[146]47
[174]48//   std::cout << &zize << " " << sizeof(mize) << sizeof(Tize) << std::endl;
49//   std::cout << sizeof(bize) << std::endl;
[146]50
51
[174]52//   Huha<Tize> k;
53//   std::cout << sizeof(k) << std::endl;
[139]54
[174]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);
[73]67  readDimacsMaxFlow(std::cin, G, s, t, cap);
[155]68
[174]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
[73]86
[133]87  {
[174]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
[73]91
[174]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) {
[168]100//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
101//     }
102//     std::cout<<std::endl;
[174]103      ++i;
104    }
[168]105
[174]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;
[168]114  }
115
116  {
[174]117    std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
118    Graph::EdgeMap<int> flow(G); //0 flow
[168]119
[174]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) {
[168]128//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
129//     }
130//     std::cout<<std::endl;
[174]131      ++i;
132    }
[133]133
[174]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;
[133]142  }
143
144  {
[174]145    std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl;
146    Graph::EdgeMap<int> flow(G); //0 flow
[133]147
[174]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) {
[168]156//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
157//     }
158//     std::cout<<std::endl;
[174]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;
[168]170  }
[133]171
[73]172
173  return 0;
174}
Note: See TracBrowser for help on using the repository browser.