COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/lg_vs_sg.cc @ 409:7ab7f083760a

Last change on this file since 409:7ab7f083760a was 379:a5bff2813c4d, checked in by marci, 17 years ago

.

File size: 5.6 KB
Line 
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>
10#include <preflow.h>
11#include <time_measure.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
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
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, true);
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
44    {
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    }
51
52    {
53      std::cout << "physical blocking flow augmentation ..." << std::endl;
54      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
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    {
64      std::cout << "faster physical blocking flow augmentation ..." << std::endl;
65      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
66      ts.reset();
67      int i=0;
68      while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
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    {
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    }
84
85    {
86      std::cout << "on-the-fly shortest path 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.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
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, true);
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
118    {
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    }
126
127    {
128      std::cout << "physical blocking flow augmentation ..." << std::endl;
129      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
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    {
139      std::cout << "faster physical blocking flow augmentation ..." << std::endl;
140      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
141      ts.reset();
142      int i=0;
143      while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
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    {
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    }
159
160    {
161      std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
162      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
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
172
173
174
175  return 0;
176}
Note: See TracBrowser for help on using the repository browser.