COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/jacint/preflow_excess_test.cc @ 986:e997802b855c

Last change on this file since 986:e997802b855c was 986:e997802b855c, checked in by Alpar Juttner, 15 years ago

Naming changes:

  • head -> target
  • tail -> source
File size: 5.2 KB
Line 
1/*
2The only difference between preflow.h and preflow_res.h is that the latter
3uses the ResGraphWrapper, while the first does not. (Bfs is implemented by
4hand in both.) This test program runs Preflow and PreflowRes on the same
5graph, tests the result of these implementations and writes the running time
6of them.  */
7#include <iostream>
8
9#include <smart_graph.h>
10#include <dimacs.h>
11#include <preflow_excess.h>
12#include <time_measure.h>
13
14using namespace lemon;
15
16int main(int, char **) {
17 
18  typedef SmartGraph Graph;
19 
20  typedef Graph::Node Node;
21  typedef Graph::EdgeIt EdgeIt;
22
23  Graph G;
24  Node s, t;
25  Graph::EdgeMap<int> cap(G);
26  readDimacsMaxFlow(std::cin, G, s, t, cap);
27  Timer ts;
28 
29  std::cout <<
30    "\n  Are we slower?"
31            <<std::endl;
32  std::cout <<
33    "\n  Running preflow.h on a graph with " <<
34    G.nodeNum() << " nodes and " << G.edgeNum() << " edges..."
35           << std::endl<<std::endl;
36
37
38
39
40
41
42 
43  Graph::EdgeMap<int> flow(G,0);
44  Preflow<Graph, int> max_flow_test(G, s, t, cap, flow, 0 , 0);
45  ts.reset();
46  max_flow_test.run();
47  std::cout << "Elapsed time from a preflow: " << std::endl
48            <<ts << std::endl;
49 
50  Graph::NodeMap<bool> mincut(G);
51  max_flow_test.minMinCut(mincut);
52  int min_min_cut_value=0;
53  EdgeIt e;
54  for(G.first(e); G.valid(e); G.next(e)) {
55    if (mincut[G.source(e)] && !mincut[G.target(e)]) min_min_cut_value+=cap[e];
56  }
57
58  Graph::NodeMap<bool> cut(G);
59  max_flow_test.minCut(cut);
60  int min_cut_value=0;
61  for(G.first(e); G.valid(e); G.next(e)) {
62    if (cut[G.source(e)] && !cut[G.target(e)])
63      min_cut_value+=cap[e];
64  }
65
66  Graph::NodeMap<bool> maxcut(G);
67  max_flow_test.maxMinCut(maxcut);
68  int max_min_cut_value=0;
69  for(G.first(e); G.valid(e); G.next(e)) {
70    if (maxcut[G.source(e)] && !maxcut[G.target(e)])
71      max_min_cut_value+=cap[e];
72      }
73
74  std::cout << "\n Checking the result: " <<std::endl; 
75  std::cout << "Flow value: "<< max_flow_test.flowValue() << std::endl;
76  std::cout << "Min cut value: "<< min_cut_value << std::endl;
77  std::cout << "Min min cut value: "<< min_min_cut_value << std::endl;
78  std::cout << "Max min cut value: "<< max_min_cut_value <<
79    std::endl;
80
81  if ( max_flow_test.flowValue() == min_cut_value &&
82       min_cut_value == min_min_cut_value &&
83       min_min_cut_value == max_min_cut_value )
84    std::cout << "They are equal! " <<std::endl<< std::endl<<"\n"; 
85
86
87
88
89
90 
91  Graph::EdgeMap<int> flow2(G,0);
92  Preflow<Graph, int> max_flow_test2(G, s, t, cap, flow2, 0 , 1);
93  ts.reset();
94  max_flow_test2.run();
95  std::cout << "Elapsed time from a flow: " << std::endl
96            << ts << std::endl;
97 
98  Graph::NodeMap<bool> mincut2(G);
99  max_flow_test2.minMinCut(mincut2);
100  int min_min_cut_value2=0;
101    for(G.first(e); G.valid(e); G.next(e)) {
102    if (mincut2[G.source(e)] && !mincut2[G.target(e)]) min_min_cut_value2+=cap[e];
103  }
104
105  Graph::NodeMap<bool> cut2(G);
106  max_flow_test2.minCut(cut2);
107  int min_cut_value2=0;
108  for(G.first(e); G.valid(e); G.next(e)) {
109    if (cut2[G.source(e)] && !cut2[G.target(e)])
110      min_cut_value2+=cap[e];
111  }
112
113  Graph::NodeMap<bool> maxcut2(G);
114  max_flow_test2.maxMinCut(maxcut2);
115  int max_min_cut_value2=0;
116  for(G.first(e); G.valid(e); G.next(e)) {
117    if (maxcut2[G.source(e)] && !maxcut2[G.target(e)])
118      max_min_cut_value2+=cap[e];
119      }
120 
121  std::cout << "\n Checking the result: " <<std::endl; 
122  std::cout << "Flow value: "<< max_flow_test2.flowValue() << std::endl;
123  std::cout << "Min cut value: "<< min_cut_value2 << std::endl;
124  std::cout << "Min min cut value: "<< min_min_cut_value2 << std::endl;
125  std::cout << "Max min cut value: "<< max_min_cut_value2 <<
126    std::endl; 
127  if ( max_flow_test.flowValue() == min_cut_value &&
128       min_cut_value == min_min_cut_value &&
129       min_min_cut_value == max_min_cut_value )
130    std::cout << "They are equal! " <<std::endl; 
131
132
133
134
135
136  Graph::EdgeMap<int> flow3(G,0);
137  Preflow<Graph, int> max_flow_test3(G, s, t, cap, flow3, 1 , 1);
138  ts.reset();
139  max_flow_test3.run();
140  std::cout << "Elapsed time from a const zero flow: " << std::endl
141            <<ts << std::endl;
142 
143  Graph::NodeMap<bool> mincut3(G);
144  max_flow_test3.minMinCut(mincut3);
145  int min_min_cut_value3=0;
146  for(G.first(e); G.valid(e); G.next(e)) {
147    if (mincut3[G.source(e)] && !mincut3[G.target(e)]) min_min_cut_value3+=cap[e];
148  }
149
150  Graph::NodeMap<bool> cut3(G);
151  max_flow_test3.minCut(cut3);
152  int min_cut_value3=0;
153  for(G.first(e); G.valid(e); G.next(e)) {
154    if (cut3[G.source(e)] && !cut3[G.target(e)])
155      min_cut_value3+=cap[e];
156  }
157
158  Graph::NodeMap<bool> maxcut3(G);
159  max_flow_test3.maxMinCut(maxcut3);
160  int max_min_cut_value3=0;
161  for(G.first(e); G.valid(e); G.next(e)) {
162    if (maxcut3[G.source(e)] && !maxcut3[G.target(e)])
163      max_min_cut_value3+=cap[e];
164      }
165
166  std::cout << "\n Checking the result: " <<std::endl; 
167  std::cout << "Flow value: "<< max_flow_test3.flowValue() << std::endl;
168  std::cout << "Min cut value: "<< min_cut_value3 << std::endl;
169  std::cout << "Min min cut value: "<< min_min_cut_value3 << std::endl;
170  std::cout << "Max min cut value: "<< max_min_cut_value3 <<
171    std::endl;
172
173  if ( max_flow_test3.flowValue() == min_cut_value3 &&
174       min_cut_value3 == min_min_cut_value3 &&
175       min_min_cut_value3 == max_min_cut_value3 )
176    std::cout << "They are equal! " <<std::endl<< std::endl<<"\n"; 
177 
178  return 0;
179}
Note: See TracBrowser for help on using the repository browser.