COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/lg_vs_sg.cc @ 577:e8703f0a6e2f

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

top-sort, dimacs mods.

File size: 5.7 KB
RevLine 
[174]1// -*- c++ -*-
2#include <iostream>
3#include <fstream>
4#include <string>
5
6#include <list_graph.h>
[555]7#include <hugo/smart_graph.h>
8#include <hugo/dimacs.h>
[480]9#include <max_flow.h>
[555]10#include <hugo/time_measure.h>
[334]11#include <for_each_macros.h>
[174]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
[577]28    Graph g;
[174]29    Node s, t;
[577]30    Graph::EdgeMap<int> cap(g);
[174]31    std::ifstream ins(in.c_str());
[577]32    //readDimacsMaxFlow(ins, g, s, t, cap);
33    readDimacs(ins, g, cap, s, t);
[174]34
[334]35    Timer ts;
[577]36    Graph::EdgeMap<int> flow(g); //0 flow
[334]37    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
[577]38      max_flow_test(g, s, t, cap, flow/*, true*/);
[334]39
40    std::cout << "ListGraph ..." << std::endl;
41
[174]42    {
[334]43      std::cout << "preflow ..." << std::endl;
44      ts.reset();
[476]45      max_flow_test.run();
[334]46      std::cout << "elapsed time: " << ts << std::endl;
[476]47      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
[334]48    }
[174]49
[334]50    {
51      std::cout << "physical blocking flow augmentation ..." << std::endl;
[577]52      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
[174]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
[476]61//     {
62//       std::cout << "faster physical blocking flow augmentation ..." << std::endl;
[577]63//       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
[476]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//     }
[174]71
72    {
[334]73      std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
[577]74      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
[334]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    }
[174]82
[334]83    {
84      std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
[577]85      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
[174]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
[577]101    Graph g;
[174]102    Node s, t;
[577]103    Graph::EdgeMap<int> cap(g);
[174]104    std::ifstream ins(in.c_str());
[577]105    //readDimacsMaxFlow(ins, g, s, t, cap);
106    readDimacs(ins, g, cap, s, t);
[174]107
[334]108    Timer ts;
[577]109    Graph::EdgeMap<int> flow(g); //0 flow
[334]110    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
[577]111      max_flow_test(g, s, t, cap, flow/*, true*/);
[476]112    //    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
[577]113    //  max_flow_test(g, s, t, cap, flow);
[334]114
115    std::cout << "SmatrGraph ..." << std::endl;
116
[174]117    {
[334]118      std::cout << "preflow ..." << std::endl;
[577]119      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
[334]120      ts.reset();
[476]121      max_flow_test.run();
[334]122      std::cout << "elapsed time: " << ts << std::endl;
[476]123      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
[334]124    }
[174]125
[334]126    {
127      std::cout << "physical blocking flow augmentation ..." << std::endl;
[577]128      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
[174]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
[476]137//     {
138//       std::cout << "faster physical blocking flow augmentation ..." << std::endl;
[577]139//       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
[476]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//     }
[174]147
148    {
[334]149      std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
[577]150      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
[334]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    }
[174]158
[334]159    {
160      std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
[577]161      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
[174]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
[334]171
172
173
[174]174  return 0;
175}
Note: See TracBrowser for help on using the repository browser.