COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/test/preflow_test.cc @ 841:f4c32484dc5b

Last change on this file since 841:f4c32484dc5b was 833:512e5fd7d38b, checked in by jacint, 20 years ago

preflow test

  • Property exe set to *
File size: 4.0 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::NodeIt NodeIt;
61  typedef Graph::EdgeIt EdgeIt;
62  typedef Graph::EdgeMap<int> CapMap;
63  typedef Graph::EdgeMap<int> FlowMap;
64  typedef Graph::NodeMap<bool> CutMap;
65
66  typedef Preflow<Graph, int> PType;
67
68  std::ifstream file("preflow_graph");
69 
70  Graph G;
71  NodeIt s, t;
72  CapMap cap(G);
73  readDimacs(file, G, cap, s, t);
74
75  FlowMap flow(G,0);
76 
77  PType preflow_test(G, s, t, cap, flow);
78  preflow_test.run(PType::ZERO_FLOW);
79 
80   
81  CutMap mincut(G,false);
82  preflow_test.minCut(mincut);
83  int min_cut_value=cut_value(G,mincut,cap);
84   
85  CutMap minmincut(G,false);
86  preflow_test.minMinCut(minmincut);
87  int min_min_cut_value=cut_value(G,minmincut,cap);
88   
89  CutMap maxmincut(G,false);
90  preflow_test.maxMinCut(maxmincut);
91  int max_min_cut_value=cut_value(G,maxmincut,cap);
92
93  check(preflow_test.flowValue() == min_cut_value &&
94        min_cut_value == min_min_cut_value &&
95        min_min_cut_value == max_min_cut_value,
96        "The max flow value is not equal to the three min cut values.");
97
98  int flow_value=preflow_test.flowValue();
99
100
101  for(EdgeIt e(G); e!=INVALID; ++e) cap[e]=2*cap[e];
102  preflow_test.setCap(cap); 
103  preflow_test.setTarget(++t); //the max flow value remains 2*flow_value
104  //warning: ++t must be a valid node. In preflow_graph, it is.
105
106  preflow_test.phase1(PType::PRE_FLOW);
107
108  CutMap mincut1(G,false);
109  preflow_test.minCut(mincut1);
110  min_cut_value=cut_value(G,mincut1,cap);
111   
112  check(preflow_test.flowValue() == min_cut_value &&
113        min_cut_value == 2*flow_value,
114        "The max flow value or the min cut value is wrong.");
115
116  preflow_test.phase2();
117
118  CutMap mincut2(G,false);
119  preflow_test.minCut(mincut2);
120  min_cut_value=cut_value(G,mincut2,cap);
121   
122  CutMap minmincut2(G,false);
123  preflow_test.minMinCut(minmincut2);
124  min_min_cut_value=cut_value(G,minmincut2,cap);
125
126 
127  preflow_test.maxMinCut(maxmincut);
128 
129  max_min_cut_value=cut_value(G,maxmincut,cap);
130
131  check(preflow_test.flowValue() == min_cut_value &&
132        min_cut_value == min_min_cut_value &&
133        min_min_cut_value == max_min_cut_value &&
134        min_cut_value == 2*flow_value,
135        "The max flow value or the three min cut values were not doubled");
136
137  EdgeIt e(G);
138  for( int i=1; i==1000; ++i ) {
139    flow[e]=0;
140    ++e;
141  }
142
143  preflow_test.setFlow(flow);
144  preflow_test.setSource(s);
145
146  preflow_test.run();
147
148  CutMap mincut3(G,false);
149  preflow_test.minCut(mincut3);
150  min_cut_value=cut_value(G,mincut3,cap);
151   
152  CutMap minmincut3(G,false);
153  preflow_test.minMinCut(minmincut3);
154  min_min_cut_value=cut_value(G,minmincut3,cap);
155   
156  preflow_test.maxMinCut(maxmincut);
157  max_min_cut_value=cut_value(G,maxmincut,cap);
158
159  check(preflow_test.flowValue() == min_cut_value &&
160        min_cut_value == min_min_cut_value &&
161        min_min_cut_value == max_min_cut_value,
162        "The max flow value or the three min cut values are incorrect.");
163}
164
165
166
Note: See TracBrowser for help on using the repository browser.