COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/test/preflow_test.cc @ 854:baf0b6e40211

Last change on this file since 854:baf0b6e40211 was 845:e4692f92a79b, checked in by Akos Ladanyi, 20 years ago

'make distcheck' works again\!

  • Property exe set to *
File size: 4.1 KB
Line 
1#include <fstream>
2#include "test_tools.h"
3#include <hugo/smart_graph.h>
4#include <hugo/dimacs.h>
5#include <hugo/preflow.h>
6#include <hugo/skeletons/graph.h>
7#include <hugo/skeletons/maps.h>
8using namespace hugo;
9
10void check_Preflow()
11{
12  typedef int VType;
13  typedef skeleton::StaticGraphSkeleton Graph;
14
15  typedef Graph::Node Node;
16  typedef Graph::Edge Edge;
17  typedef skeleton::ReadMap<Edge,VType> CapMap;
18  typedef skeleton::ReadWriteMap<Edge,VType> FlowMap;
19  typedef skeleton::ReadWriteMap<Node,bool> CutMap;
20 
21  typedef Preflow<Graph, int, CapMap, FlowMap> PType;
22
23  Graph G;
24  Node n;
25  CapMap cap;
26  FlowMap flow;
27  CutMap cut;
28
29  PType preflow_test(G,n,n,cap,flow);
30
31  preflow_test.run();
32  preflow_test.flowValue();
33  preflow_test.setSource(n);
34  preflow_test.setFlow(flow);
35
36  preflow_test.phase1(PType::NO_FLOW);
37  preflow_test.minCut(cut);
38
39  preflow_test.phase2();
40  preflow_test.setTarget(n);
41  preflow_test.setCap(cap);
42  preflow_test.minMinCut(cut);
43  preflow_test.maxMinCut(cut);
44}
45
46int cut_value ( SmartGraph& G, SmartGraph::NodeMap<bool>& cut,
47                SmartGraph::EdgeMap<int>& cap) {
48 
49  int c=0;
50  for(SmartGraph::EdgeIt e(G); e!=INVALID; ++e) {
51    if (cut[G.tail(e)] && !cut[G.head(e)]) c+=cap[e];
52  }
53  return c;
54}
55
56int main() {
57
58  typedef SmartGraph Graph;
59 
60  typedef Graph::Node Node;
61  typedef Graph::NodeIt NodeIt;
62  typedef Graph::EdgeIt EdgeIt;
63  typedef Graph::EdgeMap<int> CapMap;
64  typedef Graph::EdgeMap<int> FlowMap;
65  typedef Graph::NodeMap<bool> CutMap;
66
67  typedef Preflow<Graph, int> PType;
68
69  std::ifstream file("preflow_graph.out");
70 
71  Graph G;
72  Node s, t;
73  CapMap cap(G);
74  readDimacs(file, G, cap, s, t);
75
76  FlowMap flow(G,0);
77 
78  PType preflow_test(G, s, t, cap, flow);
79  preflow_test.run(PType::ZERO_FLOW);
80 
81   
82  CutMap mincut(G,false);
83  preflow_test.minCut(mincut);
84  int min_cut_value=cut_value(G,mincut,cap);
85   
86  CutMap minmincut(G,false);
87  preflow_test.minMinCut(minmincut);
88  int min_min_cut_value=cut_value(G,minmincut,cap);
89   
90  CutMap maxmincut(G,false);
91  preflow_test.maxMinCut(maxmincut);
92  int max_min_cut_value=cut_value(G,maxmincut,cap);
93
94  check(preflow_test.flowValue() == min_cut_value &&
95        min_cut_value == min_min_cut_value &&
96        min_min_cut_value == max_min_cut_value,
97        "The max flow value is not equal to the three min cut values.");
98
99  int flow_value=preflow_test.flowValue();
100
101
102  for(EdgeIt e(G); e!=INVALID; ++e) cap[e]=2*cap[e];
103  preflow_test.setCap(cap); 
104
105  NodeIt tmp_node(G,t);
106  ++tmp_node;
107  t=tmp_node;
108 
109  preflow_test.setTarget(t); //the max flow value remains 2*flow_value
110  //warning: ++t must be a valid node. In preflow_graph, it is.
111
112  preflow_test.phase1(PType::PRE_FLOW);
113
114  CutMap mincut1(G,false);
115  preflow_test.minCut(mincut1);
116  min_cut_value=cut_value(G,mincut1,cap);
117   
118  check(preflow_test.flowValue() == min_cut_value &&
119        min_cut_value == 2*flow_value,
120        "The max flow value or the min cut value is wrong.");
121
122  preflow_test.phase2();
123
124  CutMap mincut2(G,false);
125  preflow_test.minCut(mincut2);
126  min_cut_value=cut_value(G,mincut2,cap);
127   
128  CutMap minmincut2(G,false);
129  preflow_test.minMinCut(minmincut2);
130  min_min_cut_value=cut_value(G,minmincut2,cap);
131
132 
133  preflow_test.maxMinCut(maxmincut);
134 
135  max_min_cut_value=cut_value(G,maxmincut,cap);
136
137  check(preflow_test.flowValue() == min_cut_value &&
138        min_cut_value == min_min_cut_value &&
139        min_min_cut_value == max_min_cut_value &&
140        min_cut_value == 2*flow_value,
141        "The max flow value or the three min cut values were not doubled");
142
143  EdgeIt e(G);
144  for( int i=1; i==1000; ++i ) {
145    flow[e]=0;
146    ++e;
147  }
148
149  preflow_test.setFlow(flow);
150  preflow_test.setSource(s);
151
152  preflow_test.run();
153
154  CutMap mincut3(G,false);
155  preflow_test.minCut(mincut3);
156  min_cut_value=cut_value(G,mincut3,cap);
157   
158  CutMap minmincut3(G,false);
159  preflow_test.minMinCut(minmincut3);
160  min_min_cut_value=cut_value(G,minmincut3,cap);
161   
162  preflow_test.maxMinCut(maxmincut);
163  max_min_cut_value=cut_value(G,maxmincut,cap);
164
165  check(preflow_test.flowValue() == min_cut_value &&
166        min_cut_value == min_min_cut_value &&
167        min_min_cut_value == max_min_cut_value,
168        "The max flow value or the three min cut values are incorrect.");
169}
170
171
172
Note: See TracBrowser for help on using the repository browser.