COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/lg_vs_sg_vs_sg.cc @ 1153:4b0468de3a31

Last change on this file since 1153:4b0468de3a31 was 921:818510fa3d99, checked in by Alpar Juttner, 20 years ago

hugo -> lemon

File size: 9.0 KB
RevLine 
[174]1// -*- c++ -*-
2#include <iostream>
3#include <fstream>
4#include <string>
5
[642]6#include <sage_graph.h>
[921]7#include <lemon/list_graph.h>
8#include <lemon/smart_graph.h>
9#include <lemon/dimacs.h>
10#include <lemon/max_flow.h>
[762]11#include <augmenting_flow.h>
[921]12#include <lemon/time_measure.h>
[762]13#include <for_each_macros.h>
[174]14
[921]15using namespace lemon;
[174]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];
[642]23  typedef SageGraph MutableGraph;
[174]24
25  {
[642]26    typedef SageGraph Graph;
[174]27    typedef Graph::Node Node;
28    typedef Graph::EdgeIt EdgeIt;
29
[577]30    Graph g;
[174]31    Node s, t;
[577]32    Graph::EdgeMap<int> cap(g);
[174]33    std::ifstream ins(in.c_str());
[577]34    //readDimacsMaxFlow(ins, g, s, t, cap);
35    readDimacs(ins, g, cap, s, t);
[174]36
[334]37    Timer ts;
[577]38    Graph::EdgeMap<int> flow(g); //0 flow
[334]39    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
[577]40      max_flow_test(g, s, t, cap, flow/*, true*/);
[762]41    AugmentingFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
42      augmenting_flow_test(g, s, t, cap, flow/*, true*/);
[334]43
[642]44    std::cout << "SageGraph ..." << std::endl;
[334]45
[174]46    {
[334]47      std::cout << "preflow ..." << std::endl;
48      ts.reset();
[476]49      max_flow_test.run();
[334]50      std::cout << "elapsed time: " << ts << std::endl;
[476]51      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
[334]52    }
[174]53
[334]54    {
55      std::cout << "physical blocking flow augmentation ..." << std::endl;
[777]56      for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
[174]57      ts.reset();
58      int i=0;
[762]59      while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
[174]60      std::cout << "elapsed time: " << ts << std::endl;
61      std::cout << "number of augmentation phases: " << i << std::endl;
[762]62      std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
[174]63    }
64
[476]65//     {
66//       std::cout << "faster physical blocking flow augmentation ..." << std::endl;
[577]67//       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
[476]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//     }
[174]75
76    {
[334]77      std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
[777]78      for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
[334]79      ts.reset();
80      int i=0;
[762]81      while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }
[334]82      std::cout << "elapsed time: " << ts << std::endl;
83      std::cout << "number of augmentation phases: " << i << std::endl;
[762]84      std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
[334]85    }
[174]86
[334]87    {
88      std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
[777]89      for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
[174]90      ts.reset();
91      int i=0;
[762]92      while (augmenting_flow_test.augmentOnShortestPath()) { ++i; }
[174]93      std::cout << "elapsed time: " << ts << std::endl;
94      std::cout << "number of augmentation phases: " << i << std::endl;
[762]95      std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
[174]96    }
97  }
98
99  {
100    typedef SmartGraph Graph;
101    typedef Graph::Node Node;
102    typedef Graph::EdgeIt EdgeIt;
103
[577]104    Graph g;
[174]105    Node s, t;
[577]106    Graph::EdgeMap<int> cap(g);
[174]107    std::ifstream ins(in.c_str());
[577]108    //readDimacsMaxFlow(ins, g, s, t, cap);
109    readDimacs(ins, g, cap, s, t);
[174]110
[334]111    Timer ts;
[577]112    Graph::EdgeMap<int> flow(g); //0 flow
[334]113    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
[577]114      max_flow_test(g, s, t, cap, flow/*, true*/);
[762]115    AugmentingFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
116      augmenting_flow_test(g, s, t, cap, flow/*, true*/);
[476]117    //    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
[577]118    //  max_flow_test(g, s, t, cap, flow);
[334]119
[642]120    std::cout << "SmartGraph ..." << std::endl;
[334]121
[174]122    {
[334]123      std::cout << "preflow ..." << std::endl;
[777]124      for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
[334]125      ts.reset();
[476]126      max_flow_test.run();
[334]127      std::cout << "elapsed time: " << ts << std::endl;
[476]128      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
[334]129    }
[174]130
[334]131    {
132      std::cout << "physical blocking flow augmentation ..." << std::endl;
[777]133      for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
[174]134      ts.reset();
135      int i=0;
[762]136      while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
[174]137      std::cout << "elapsed time: " << ts << std::endl;
138      std::cout << "number of augmentation phases: " << i << std::endl;
[762]139      std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
[174]140    }
141
[476]142//     {
143//       std::cout << "faster physical blocking flow augmentation ..." << std::endl;
[577]144//       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
[476]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//     }
[174]152
153    {
[334]154      std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
[777]155      for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
[334]156      ts.reset();
157      int i=0;
[762]158      while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }
[334]159      std::cout << "elapsed time: " << ts << std::endl;
160      std::cout << "number of augmentation phases: " << i << std::endl;
[762]161      std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
[334]162    }
[174]163
[334]164    {
165      std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
[777]166      for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
[174]167      ts.reset();
168      int i=0;
[762]169      while (augmenting_flow_test.augmentOnShortestPath()) { ++i; }
[174]170      std::cout << "elapsed time: " << ts << std::endl;
171      std::cout << "number of augmentation phases: " << i << std::endl;
[762]172      std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
[174]173    }
174  }
175
[642]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*/);
[762]192    AugmentingFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
193      augmenting_flow_test(g, s, t, cap, flow/*, true*/);
[642]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;
[777]201      for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
[642]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;
[777]210      for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
[642]211      ts.reset();
212      int i=0;
[762]213      while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
[642]214      std::cout << "elapsed time: " << ts << std::endl;
215      std::cout << "number of augmentation phases: " << i << std::endl;
[762]216      std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
[642]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;
[777]232      for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
[642]233      ts.reset();
234      int i=0;
[762]235      while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }
[642]236      std::cout << "elapsed time: " << ts << std::endl;
237      std::cout << "number of augmentation phases: " << i << std::endl;
[762]238      std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
[642]239    }
240
241    {
242      std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
[777]243      for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
[642]244      ts.reset();
245      int i=0;
[762]246      while (augmenting_flow_test.augmentOnShortestPath()) { ++i; }
[642]247      std::cout << "elapsed time: " << ts << std::endl;
248      std::cout << "number of augmentation phases: " << i << std::endl;
[762]249      std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
[642]250    }
251  }
252
[174]253  return 0;
254}
Note: See TracBrowser for help on using the repository browser.