COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/jacint/max_flow_test.cc @ 675:38755a4d4b51

Last change on this file since 675:38755a4d4b51 was 588:510cf257e6f2, checked in by jacint, 21 years ago

felkesz tesztprogi

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