COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/lg_vs_sg.cc @ 618:e944d741f472

Last change on this file since 618:e944d741f472 was 577:e8703f0a6e2f, checked in by marci, 20 years ago

top-sort, dimacs mods.

File size: 5.7 KB
Line 
1// -*- c++ -*-
2#include <iostream>
3#include <fstream>
4#include <string>
5
6#include <list_graph.h>
7#include <hugo/smart_graph.h>
8#include <hugo/dimacs.h>
9#include <max_flow.h>
10#include <hugo/time_measure.h>
11#include <for_each_macros.h>
12
13using namespace hugo;
14
15// Use a DIMACS max flow file as stdin.
16// read_dimacs_demo dimacs_max_flow_file
17
18int main(int, char** argv) {
19
20  std::string in=argv[1];
21  typedef ListGraph MutableGraph;
22
23  {
24    typedef ListGraph Graph;
25    typedef Graph::Node Node;
26    typedef Graph::EdgeIt EdgeIt;
27
28    Graph g;
29    Node s, t;
30    Graph::EdgeMap<int> cap(g);
31    std::ifstream ins(in.c_str());
32    //readDimacsMaxFlow(ins, g, s, t, cap);
33    readDimacs(ins, g, cap, s, t);
34
35    Timer ts;
36    Graph::EdgeMap<int> flow(g); //0 flow
37    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
38      max_flow_test(g, s, t, cap, flow/*, true*/);
39
40    std::cout << "ListGraph ..." << std::endl;
41
42    {
43      std::cout << "preflow ..." << std::endl;
44      ts.reset();
45      max_flow_test.run();
46      std::cout << "elapsed time: " << ts << std::endl;
47      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
48    }
49
50    {
51      std::cout << "physical blocking flow augmentation ..." << std::endl;
52      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
53      ts.reset();
54      int i=0;
55      while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
56      std::cout << "elapsed time: " << ts << std::endl;
57      std::cout << "number of augmentation phases: " << i << std::endl;
58      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
59    }
60
61//     {
62//       std::cout << "faster physical blocking flow augmentation ..." << std::endl;
63//       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
64//       ts.reset();
65//       int i=0;
66//       while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
67//       std::cout << "elapsed time: " << ts << std::endl;
68//       std::cout << "number of augmentation phases: " << i << std::endl;
69//       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
70//     }
71
72    {
73      std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
74      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
75      ts.reset();
76      int i=0;
77      while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
78      std::cout << "elapsed time: " << ts << std::endl;
79      std::cout << "number of augmentation phases: " << i << std::endl;
80      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
81    }
82
83    {
84      std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
85      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
86      ts.reset();
87      int i=0;
88      while (max_flow_test.augmentOnShortestPath()) { ++i; }
89      std::cout << "elapsed time: " << ts << std::endl;
90      std::cout << "number of augmentation phases: " << i << std::endl;
91      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
92    }
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 << "SmatrGraph ..." << 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
173
174  return 0;
175}
Note: See TracBrowser for help on using the repository browser.