COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/lg_vs_sg.cc @ 476:cfe550761745

Last change on this file since 476:cfe550761745 was 476:cfe550761745, checked in by marci, 16 years ago

preflow, maxflow

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 <preflow.h>
10#include <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
34    Timer ts;
35    Graph::EdgeMap<int> flow(G); //0 flow
36    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
37      max_flow_test(G, s, t, cap, flow/*, true*/);
38
39    std::cout << "ListGraph ..." << std::endl;
40
41    {
42      std::cout << "preflow ..." << std::endl;
43      ts.reset();
44      max_flow_test.run();
45      std::cout << "elapsed time: " << ts << std::endl;
46      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
47    }
48
49    {
50      std::cout << "physical blocking flow augmentation ..." << std::endl;
51      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
52      ts.reset();
53      int i=0;
54      while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
55      std::cout << "elapsed time: " << ts << std::endl;
56      std::cout << "number of augmentation phases: " << i << std::endl;
57      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
58    }
59
60//     {
61//       std::cout << "faster physical blocking flow augmentation ..." << std::endl;
62//       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
63//       ts.reset();
64//       int i=0;
65//       while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
66//       std::cout << "elapsed time: " << ts << std::endl;
67//       std::cout << "number of augmentation phases: " << i << std::endl;
68//       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
69//     }
70
71    {
72      std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
73      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
74      ts.reset();
75      int i=0;
76      while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
77      std::cout << "elapsed time: " << ts << std::endl;
78      std::cout << "number of augmentation phases: " << i << std::endl;
79      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
80    }
81
82    {
83      std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
84      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
85      ts.reset();
86      int i=0;
87      while (max_flow_test.augmentOnShortestPath()) { ++i; }
88      std::cout << "elapsed time: " << ts << std::endl;
89      std::cout << "number of augmentation phases: " << i << std::endl;
90      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
91    }
92  }
93
94
95  {
96    typedef SmartGraph Graph;
97    typedef Graph::Node Node;
98    typedef Graph::EdgeIt EdgeIt;
99
100    Graph G;
101    Node s, t;
102    Graph::EdgeMap<int> cap(G);
103    std::ifstream ins(in.c_str());
104    readDimacsMaxFlow(ins, G, s, t, cap);
105
106    Timer ts;
107    Graph::EdgeMap<int> flow(G); //0 flow
108    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
109      max_flow_test(G, s, t, cap, flow/*, true*/);
110    //    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
111    //  max_flow_test(G, s, t, cap, flow);
112
113    std::cout << "SmatrGraph ..." << std::endl;
114
115    {
116      std::cout << "preflow ..." << std::endl;
117      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
118      ts.reset();
119      max_flow_test.run();
120      std::cout << "elapsed time: " << ts << std::endl;
121      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
122    }
123
124    {
125      std::cout << "physical blocking flow augmentation ..." << std::endl;
126      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
127      ts.reset();
128      int i=0;
129      while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
130      std::cout << "elapsed time: " << ts << std::endl;
131      std::cout << "number of augmentation phases: " << i << std::endl;
132      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
133    }
134
135//     {
136//       std::cout << "faster physical blocking flow augmentation ..." << std::endl;
137//       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
138//       ts.reset();
139//       int i=0;
140//       while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
141//       std::cout << "elapsed time: " << ts << std::endl;
142//       std::cout << "number of augmentation phases: " << i << std::endl;
143//       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
144//     }
145
146    {
147      std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
148      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
149      ts.reset();
150      int i=0;
151      while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
152      std::cout << "elapsed time: " << ts << std::endl;
153      std::cout << "number of augmentation phases: " << i << std::endl;
154      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
155    }
156
157    {
158      std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
159      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
160      ts.reset();
161      int i=0;
162      while (max_flow_test.augmentOnShortestPath()) { ++i; }
163      std::cout << "elapsed time: " << ts << std::endl;
164      std::cout << "number of augmentation phases: " << i << std::endl;
165      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
166    }
167  }
168
169
170
171
172  return 0;
173}
Note: See TracBrowser for help on using the repository browser.