COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/jacint/max_flow_test.cc @ 985:741f3108a90f

Last change on this file since 985:741f3108a90f was 921:818510fa3d99, checked in by Alpar Juttner, 20 years ago

hugo -> lemon

File size: 5.2 KB
Line 
1#include <iostream>
2
3#include <lemon/list_graph.h>
4#include <lemon/dimacs.h>
5#include <max_flow.h>
6#include <max_flow_no_stack.h>
7#include <lemon/time_measure.h>
8
9using namespace lemon;
10
11int main(int, char **) {
12 
13  typedef ListGraph Graph;
14 
15  typedef Graph::Node Node;
16  typedef Graph::EdgeIt EdgeIt;
17
18  Graph G;
19  Node s, t;
20  Graph::EdgeMap<int> cap(G);
21  readDimacs(std::cin, G, cap, s, t);
22  Timer ts;
23 
24  std::cout <<
25    "\n  Running max_flow.h on a graph with " <<
26    G.nodeNum() << " nodes and " << G.edgeNum() << " edges..."
27           << std::endl<<std::endl;
28
29  Graph::EdgeMap<int> flowstack(G,0);
30  MaxFlow<Graph, int> max_flow_test(G, s, t, cap, flowstack);
31  ts.reset();
32  max_flow_test.run();
33  std::cout << "Elapsed time of run() with stl stack: " << std::endl
34            <<ts << std::endl;
35
36  Graph::EdgeMap<int> flow(G,0);
37  MaxFlowNoStack<Graph, int> max_flow_test_no_stack(G, s, t, cap, flow);
38  ts.reset();
39  max_flow_test_no_stack.run();
40  std::cout << "Elapsed time of run() without stack: " << std::endl
41            <<ts << std::endl;
42 
43  Graph::NodeMap<bool> mincut(G);
44  max_flow_test_no_stack.minMinCut(mincut);
45  int min_min_cut_value=0;
46  EdgeIt e;
47  for(G.first(e); G.valid(e); G.next(e)) {
48    if (mincut[G.tail(e)] && !mincut[G.head(e)]) min_min_cut_value+=cap[e];
49  }
50
51  Graph::NodeMap<bool> cut(G);
52  max_flow_test_no_stack.minCut(cut);
53  int min_cut_value=0;
54  for(G.first(e); G.valid(e); G.next(e)) {
55    if (cut[G.tail(e)] && !cut[G.head(e)])
56      min_cut_value+=cap[e];
57  }
58
59  Graph::NodeMap<bool> maxcut(G);
60  max_flow_test_no_stack.maxMinCut(maxcut);
61  int max_min_cut_value=0;
62  for(G.first(e); G.valid(e); G.next(e)) {
63    if (maxcut[G.tail(e)] && !maxcut[G.head(e)])
64      max_min_cut_value+=cap[e];
65      }
66
67  std::cout << "\n Checking the result without stack: " <<std::endl; 
68  std::cout << "Flow value: "<< max_flow_test_no_stack.flowValue() << std::endl;
69  std::cout << "Min cut value: "<< min_cut_value << std::endl;
70  std::cout << "Min min cut value: "<< min_min_cut_value << std::endl;
71  std::cout << "Max min cut value: "<< max_min_cut_value <<
72    std::endl;
73
74  if ( max_flow_test_no_stack.flowValue() == min_cut_value &&
75       min_cut_value == min_min_cut_value &&
76       min_min_cut_value == max_min_cut_value )
77    std::cout << "They are equal! " <<std::endl<< std::endl<<"\n"; 
78
79  /*
80
81  Graph::EdgeMap<int> flow2(G,0);
82  std::cout << "Calling resetFlow() " << std::endl
83            << ts << std::endl;
84  max_flow_test.setFlow(flow2); 
85  ts.reset();
86  max_flow_test.preflow(max_flow_test.PRE_FLOW);
87  std::cout << "Elapsed time of preflow(PRE_FLOW) starting from the zero flow: " << std::endl
88            << ts << std::endl;
89 
90  Graph::NodeMap<bool> mincut2(G);
91  max_flow_test.minMinCut(mincut2);
92  int min_min_cut_value2=0;
93    for(G.first(e); G.valid(e); G.next(e)) {
94    if (mincut2[G.tail(e)] && !mincut2[G.head(e)]) min_min_cut_value2+=cap[e];
95  }
96
97  Graph::NodeMap<bool> cut2(G);
98  max_flow_test.minCut(cut2);
99  int min_cut_value2=0;
100  for(G.first(e); G.valid(e); G.next(e)) {
101    if (cut2[G.tail(e)] && !cut2[G.head(e)])
102      min_cut_value2+=cap[e];
103  }
104
105  Graph::NodeMap<bool> maxcut2(G);
106  max_flow_test.maxMinCut(maxcut2);
107  int max_min_cut_value2=0;
108  for(G.first(e); G.valid(e); G.next(e)) {
109    if (maxcut2[G.tail(e)] && !maxcut2[G.head(e)])
110      max_min_cut_value2+=cap[e];
111      }
112 
113  std::cout << "\n Checking the result: " <<std::endl; 
114  std::cout << "Flow value: "<< max_flow_test.flowValue() << std::endl;
115  std::cout << "Min cut value: "<< min_cut_value2 << std::endl;
116  std::cout << "Min min cut value: "<< min_min_cut_value2 << std::endl;
117  std::cout << "Max min cut value: "<< max_min_cut_value2 <<
118    std::endl; 
119  if ( max_flow_test.flowValue() == min_cut_value &&
120       min_cut_value == min_min_cut_value &&
121       min_min_cut_value == max_min_cut_value )
122    std::cout << "They are equal! " <<std::endl; 
123
124
125  MaxFlow<Graph, int> max_flow_test3(G, s, t, cap, flow2);
126  max_flow_test3.run(max_flow_test3.GEN_FLOW);
127  std::cout << "Calling run(GEN_FLOW) from the max flow found before. " <<std::endl; 
128 
129  Graph::NodeMap<bool> mincut3(G);
130  max_flow_test3.minMinCut(mincut3);
131  int min_min_cut_value3=0;
132  for(G.first(e); G.valid(e); G.next(e)) {
133    if (mincut3[G.tail(e)] && !mincut3[G.head(e)]) min_min_cut_value3+=cap[e];
134  }
135
136  Graph::NodeMap<bool> cut3(G);
137  max_flow_test3.minCut(cut3);
138  int min_cut_value3=0;
139  for(G.first(e); G.valid(e); G.next(e)) {
140    if (cut3[G.tail(e)] && !cut3[G.head(e)])
141      min_cut_value3+=cap[e];
142  }
143
144  Graph::NodeMap<bool> maxcut3(G);
145  max_flow_test3.maxMinCut(maxcut3);
146  int max_min_cut_value3=0;
147  for(G.first(e); G.valid(e); G.next(e)) {
148    if (maxcut3[G.tail(e)] && !maxcut3[G.head(e)])
149      max_min_cut_value3+=cap[e];
150  }
151
152  std::cout << "\n Checking the result: " <<std::endl; 
153  std::cout << "Flow value: "<< max_flow_test3.flowValue() << std::endl;
154  std::cout << "Min cut value: "<< min_cut_value3 << std::endl;
155  std::cout << "Min min cut value: "<< min_min_cut_value3 << std::endl;
156  std::cout << "Max min cut value: "<< max_min_cut_value3 <<
157    std::endl;
158
159  if ( max_flow_test3.flowValue() == min_cut_value3 &&
160       min_cut_value3 == min_min_cut_value3 &&
161       min_min_cut_value3 == max_min_cut_value3 )
162    std::cout << "They are equal! " <<std::endl<< std::endl<<"\n"; 
163  */
164 
165  return 0;
166}
Note: See TracBrowser for help on using the repository browser.