COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

source: lemon-0.x/src/work/marci/lg_vs_sg_vs_sg.cc @ 777:a82713ed19f3

Last change on this file since 777:a82713ed19f3 was 777:a82713ed19f3, checked in by marci, 21 years ago

graph_wrapper.h is ready for hugo 0.2
File size: 9.0 KB
Line 
1// -*- c++ -*-
2#include <iostream>
3#include <fstream>
4#include <string>
5
6#include <sage_graph.h>
7#include <hugo/list_graph.h>
8#include <hugo/smart_graph.h>
9#include <hugo/dimacs.h>
10#include <hugo/max_flow.h>
11#include <augmenting_flow.h>
12#include <hugo/time_measure.h>
13#include <for_each_macros.h>
14
15using namespace hugo;
16
17// Use a DIMACS max flow file as stdin.
18// read_dimacs_demo dimacs_max_flow_file
19
20int main(int, char** argv) {
21
22  std::string in=argv[1];
23  typedef SageGraph MutableGraph;
24
25  {
26    typedef SageGraph Graph;
27    typedef Graph::Node Node;
28    typedef Graph::EdgeIt EdgeIt;
29
30    Graph g;
31    Node s, t;
32    Graph::EdgeMap<int> cap(g);
33    std::ifstream ins(in.c_str());
34    //readDimacsMaxFlow(ins, g, s, t, cap);
35    readDimacs(ins, g, cap, s, t);
36
37    Timer ts;
38    Graph::EdgeMap<int> flow(g); //0 flow
39    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
40      max_flow_test(g, s, t, cap, flow/*, true*/);
41    AugmentingFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
42      augmenting_flow_test(g, s, t, cap, flow/*, true*/);
43
44    std::cout << "SageGraph ..." << std::endl;
45
46    {
47      std::cout << "preflow ..." << std::endl;
48      ts.reset();
49      max_flow_test.run();
50      std::cout << "elapsed time: " << ts << std::endl;
51      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
52    }
53
54    {
55      std::cout << "physical blocking flow augmentation ..." << std::endl;
56      for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
57      ts.reset();
58      int i=0;
59      while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
60      std::cout << "elapsed time: " << ts << std::endl;
61      std::cout << "number of augmentation phases: " << i << std::endl;
62      std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
63    }
64
65//     {
66//       std::cout << "faster physical blocking flow augmentation ..." << std::endl;
67//       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
68//       ts.reset();
69//       int i=0;
70//       while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
71//       std::cout << "elapsed time: " << ts << std::endl;
72//       std::cout << "number of augmentation phases: " << i << std::endl;
73//       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
74//     }
75
76    {
77      std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
78      for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
79      ts.reset();
80      int i=0;
81      while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }
82      std::cout << "elapsed time: " << ts << std::endl;
83      std::cout << "number of augmentation phases: " << i << std::endl;
84      std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
85    }
86
87    {
88      std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
89      for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
90      ts.reset();
91      int i=0;
92      while (augmenting_flow_test.augmentOnShortestPath()) { ++i; }
93      std::cout << "elapsed time: " << ts << std::endl;
94      std::cout << "number of augmentation phases: " << i << std::endl;
95      std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
96    }
97  }
98
99  {
100    typedef SmartGraph Graph;
101    typedef Graph::Node Node;
102    typedef Graph::EdgeIt EdgeIt;
103
104    Graph g;
105    Node s, t;
106    Graph::EdgeMap<int> cap(g);
107    std::ifstream ins(in.c_str());
108    //readDimacsMaxFlow(ins, g, s, t, cap);
109    readDimacs(ins, g, cap, s, t);
110
111    Timer ts;
112    Graph::EdgeMap<int> flow(g); //0 flow
113    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
114      max_flow_test(g, s, t, cap, flow/*, true*/);
115    AugmentingFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
116      augmenting_flow_test(g, s, t, cap, flow/*, true*/);
117    //    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
118    //  max_flow_test(g, s, t, cap, flow);
119
120    std::cout << "SmartGraph ..." << std::endl;
121
122    {
123      std::cout << "preflow ..." << std::endl;
124      for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
125      ts.reset();
126      max_flow_test.run();
127      std::cout << "elapsed time: " << ts << std::endl;
128      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
129    }
130
131    {
132      std::cout << "physical blocking flow augmentation ..." << std::endl;
133      for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
134      ts.reset();
135      int i=0;
136      while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
137      std::cout << "elapsed time: " << ts << std::endl;
138      std::cout << "number of augmentation phases: " << i << std::endl;
139      std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
140    }
141
142//     {
143//       std::cout << "faster physical blocking flow augmentation ..." << std::endl;
144//       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
145//       ts.reset();
146//       int i=0;
147//       while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
148//       std::cout << "elapsed time: " << ts << std::endl;
149//       std::cout << "number of augmentation phases: " << i << std::endl;
150//       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
151//     }
152
153    {
154      std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
155      for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
156      ts.reset();
157      int i=0;
158      while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }
159      std::cout << "elapsed time: " << ts << std::endl;
160      std::cout << "number of augmentation phases: " << i << std::endl;
161      std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
162    }
163
164    {
165      std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
166      for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
167      ts.reset();
168      int i=0;
169      while (augmenting_flow_test.augmentOnShortestPath()) { ++i; }
170      std::cout << "elapsed time: " << ts << std::endl;
171      std::cout << "number of augmentation phases: " << i << std::endl;
172      std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
173    }
174  }
175
176  {
177    typedef ListGraph Graph;
178    typedef Graph::Node Node;
179    typedef Graph::EdgeIt EdgeIt;
180
181    Graph g;
182    Node s, t;
183    Graph::EdgeMap<int> cap(g);
184    std::ifstream ins(in.c_str());
185    //readDimacsMaxFlow(ins, g, s, t, cap);
186    readDimacs(ins, g, cap, s, t);
187
188    Timer ts;
189    Graph::EdgeMap<int> flow(g); //0 flow
190    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
191      max_flow_test(g, s, t, cap, flow/*, true*/);
192    AugmentingFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
193      augmenting_flow_test(g, s, t, cap, flow/*, true*/);
194    //    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
195    //  max_flow_test(g, s, t, cap, flow);
196
197    std::cout << "ListGraph ..." << std::endl;
198
199    {
200      std::cout << "preflow ..." << std::endl;
201      for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
202      ts.reset();
203      max_flow_test.run();
204      std::cout << "elapsed time: " << ts << std::endl;
205      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
206    }
207
208    {
209      std::cout << "physical blocking flow augmentation ..." << std::endl;
210      for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
211      ts.reset();
212      int i=0;
213      while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
214      std::cout << "elapsed time: " << ts << std::endl;
215      std::cout << "number of augmentation phases: " << i << std::endl;
216      std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
217    }
218
219//     {
220//       std::cout << "faster physical blocking flow augmentation ..." << std::endl;
221//       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
222//       ts.reset();
223//       int i=0;
224//       while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
225//       std::cout << "elapsed time: " << ts << std::endl;
226//       std::cout << "number of augmentation phases: " << i << std::endl;
227//       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
228//     }
229
230    {
231      std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
232      for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
233      ts.reset();
234      int i=0;
235      while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }
236      std::cout << "elapsed time: " << ts << std::endl;
237      std::cout << "number of augmentation phases: " << i << std::endl;
238      std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
239    }
240
241    {
242      std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
243      for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
244      ts.reset();
245      int i=0;
246      while (augmenting_flow_test.augmentOnShortestPath()) { ++i; }
247      std::cout << "elapsed time: " << ts << std::endl;
248      std::cout << "number of augmentation phases: " << i << std::endl;
249      std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
250    }
251  }
252
253  return 0;
254}
Note: See TracBrowser for help on using the repository browser.