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 @ 643:f8053cb51047

Last change on this file since 643:f8053cb51047 was 643:f8053cb51047, checked in by marci, 22 years ago

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