COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/lg_vs_sg.cc @ 358:caf183989ec4

Last change on this file since 358:caf183989ec4 was 334:63703ea7d02f, checked in by marci, 20 years ago

brrr

File size: 5.6 KB
RevLine 
[174]1// -*- c++ -*-
2#include <iostream>
3#include <fstream>
4#include <string>
5
6#include <list_graph.h>
7#include <smart_graph.h>
8#include <dimacs.h>
9#include <edmonds_karp.h>
[334]10#include <preflow.h>
[174]11#include <time_measure.h>
[334]12#include <for_each_macros.h>
[174]13
14using namespace hugo;
15
16// Use a DIMACS max flow file as stdin.
17// read_dimacs_demo dimacs_max_flow_file
18
19int main(int, char** argv) {
20
21  std::string in=argv[1];
22  typedef ListGraph MutableGraph;
23
24  {
25    typedef ListGraph Graph;
26    typedef Graph::Node Node;
27    typedef Graph::EdgeIt EdgeIt;
28
29    Graph G;
30    Node s, t;
31    Graph::EdgeMap<int> cap(G);
32    std::ifstream ins(in.c_str());
33    readDimacsMaxFlow(ins, G, s, t, cap);
34
[334]35    Timer ts;
36    Graph::EdgeMap<int> flow(G); //0 flow
37    Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
38      pre_flow_test(G, s, t, cap, flow);
39    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
40      max_flow_test(G, s, t, cap, flow);
41
42    std::cout << "ListGraph ..." << std::endl;
43
[174]44    {
[334]45      std::cout << "preflow ..." << std::endl;
46      ts.reset();
47      pre_flow_test.run();
48      std::cout << "elapsed time: " << ts << std::endl;
49      std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
50    }
[174]51
[334]52    {
53      std::cout << "physical blocking flow augmentation ..." << std::endl;
54      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
[174]55      ts.reset();
56      int i=0;
57      while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
58      std::cout << "elapsed time: " << ts << std::endl;
59      std::cout << "number of augmentation phases: " << i << std::endl;
60      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
61    }
62
63    {
[334]64      std::cout << "faster physical blocking flow augmentation ..." << std::endl;
65      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
[174]66      ts.reset();
67      int i=0;
[334]68      while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
[174]69      std::cout << "elapsed time: " << ts << std::endl;
70      std::cout << "number of augmentation phases: " << i << std::endl;
71      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
72    }
73
74    {
[334]75      std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
76      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
77      ts.reset();
78      int i=0;
79      while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
80      std::cout << "elapsed time: " << ts << std::endl;
81      std::cout << "number of augmentation phases: " << i << std::endl;
82      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
83    }
[174]84
[334]85    {
86      std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
87      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
[174]88      ts.reset();
89      int i=0;
90      while (max_flow_test.augmentOnShortestPath()) { ++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
98  {
99    typedef SmartGraph Graph;
100    typedef Graph::Node Node;
101    typedef Graph::EdgeIt EdgeIt;
102
103    Graph G;
104    Node s, t;
105    Graph::EdgeMap<int> cap(G);
106    std::ifstream ins(in.c_str());
107    readDimacsMaxFlow(ins, G, s, t, cap);
108
[334]109    Timer ts;
110    Graph::EdgeMap<int> flow(G); //0 flow
111    Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
112      pre_flow_test(G, s, t, cap, flow);
113    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
114      max_flow_test(G, s, t, cap, flow);
115
116    std::cout << "SmatrGraph ..." << std::endl;
117
[174]118    {
[334]119      std::cout << "preflow ..." << std::endl;
120      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
121      ts.reset();
122      pre_flow_test.run();
123      std::cout << "elapsed time: " << ts << std::endl;
124      std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
125    }
[174]126
[334]127    {
128      std::cout << "physical blocking flow augmentation ..." << std::endl;
129      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
[174]130      ts.reset();
131      int i=0;
132      while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
133      std::cout << "elapsed time: " << ts << std::endl;
134      std::cout << "number of augmentation phases: " << i << std::endl;
135      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
136    }
137
138    {
[334]139      std::cout << "faster physical blocking flow augmentation ..." << std::endl;
140      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
[174]141      ts.reset();
142      int i=0;
[334]143      while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
[174]144      std::cout << "elapsed time: " << ts << std::endl;
145      std::cout << "number of augmentation phases: " << i << std::endl;
146      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
147    }
148
149    {
[334]150      std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
151      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
152      ts.reset();
153      int i=0;
154      while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
155      std::cout << "elapsed time: " << ts << std::endl;
156      std::cout << "number of augmentation phases: " << i << std::endl;
157      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
158    }
[174]159
[334]160    {
161      std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
162      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
[174]163      ts.reset();
164      int i=0;
165      while (max_flow_test.augmentOnShortestPath()) { ++i; }
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
[334]172
173
174
[174]175  return 0;
176}
Note: See TracBrowser for help on using the repository browser.