COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/jacint/max_flow_bug.cc @ 965:1e16b8dac159

Last change on this file since 965:1e16b8dac159 was 921:818510fa3d99, checked in by Alpar Juttner, 20 years ago

hugo -> lemon

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