Images are compiled in now.
2 * test/preflow_test.cc - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
20 #include "test_tools.h"
21 #include <lemon/smart_graph.h>
22 #include <lemon/dimacs.h>
23 #include <lemon/preflow.h>
24 #include <lemon/concept/graph.h>
25 #include <lemon/concept/maps.h>
27 using namespace lemon;
32 typedef concept::StaticGraph Graph;
34 typedef Graph::Node Node;
35 typedef Graph::Edge Edge;
36 typedef concept::ReadMap<Edge,VType> CapMap;
37 typedef concept::ReadWriteMap<Edge,VType> FlowMap;
38 typedef concept::ReadWriteMap<Node,bool> CutMap;
40 typedef Preflow<Graph, int, CapMap, FlowMap> PType;
48 PType preflow_test(g,n,n,cap,flow);
51 preflow_test.flowValue();
52 preflow_test.source(n);
53 preflow_test.flowMap(flow);
55 preflow_test.phase1(PType::NO_FLOW);
56 preflow_test.minCut(cut);
58 preflow_test.phase2();
59 preflow_test.target(n);
60 preflow_test.capacityMap(cap);
61 preflow_test.minMinCut(cut);
62 preflow_test.maxMinCut(cut);
65 int cut_value ( SmartGraph& g, SmartGraph::NodeMap<bool>& cut,
66 SmartGraph::EdgeMap<int>& cap) {
69 for(SmartGraph::EdgeIt e(g); e!=INVALID; ++e) {
70 if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e];
77 typedef SmartGraph Graph;
79 typedef Graph::Node Node;
80 typedef Graph::NodeIt NodeIt;
81 typedef Graph::EdgeIt EdgeIt;
82 typedef Graph::EdgeMap<int> CapMap;
83 typedef Graph::EdgeMap<int> FlowMap;
84 typedef Graph::NodeMap<bool> CutMap;
86 typedef Preflow<Graph, int> PType;
89 if( getenv("srcdir") )
90 f_name = std::string(getenv("srcdir"));
92 f_name += "/preflow_graph.dim";
94 std::ifstream file(f_name.c_str());
96 check(file, "Input file '" << f_name << "' not found.");
101 readDimacs(file, g, cap, s, t);
107 PType preflow_test(g, s, t, cap, flow);
108 preflow_test.run(PType::ZERO_FLOW);
110 CutMap min_cut(g,false);
111 preflow_test.minCut(min_cut);
112 int min_cut_value=cut_value(g,min_cut,cap);
114 CutMap min_min_cut(g,false);
115 preflow_test.minMinCut(min_min_cut);
116 int min_min_cut_value=cut_value(g,min_min_cut,cap);
118 CutMap max_min_cut(g,false);
119 preflow_test.maxMinCut(max_min_cut);
120 int max_min_cut_value=cut_value(g,max_min_cut,cap);
122 check(preflow_test.flowValue() == min_cut_value &&
123 min_cut_value == min_min_cut_value &&
124 min_min_cut_value == max_min_cut_value,
125 "The max flow value is not equal to the three min cut values.");
127 int flow_value=preflow_test.flowValue();
131 for(EdgeIt e(g); e!=INVALID; ++e) cap[e]=2*cap[e];
132 preflow_test.capacityMap(cap);
134 preflow_test.phase1(PType::PRE_FLOW);
136 CutMap min_cut1(g,false);
137 preflow_test.minCut(min_cut1);
138 min_cut_value=cut_value(g,min_cut1,cap);
140 check(preflow_test.flowValue() == min_cut_value &&
141 min_cut_value == 2*flow_value,
142 "The max flow value or the min cut value is wrong.");
144 preflow_test.phase2();
146 CutMap min_cut2(g,false);
147 preflow_test.minCut(min_cut2);
148 min_cut_value=cut_value(g,min_cut2,cap);
150 CutMap min_min_cut2(g,false);
151 preflow_test.minMinCut(min_min_cut2);
152 min_min_cut_value=cut_value(g,min_min_cut2,cap);
154 preflow_test.maxMinCut(max_min_cut);
155 max_min_cut_value=cut_value(g,max_min_cut,cap);
157 check(preflow_test.flowValue() == min_cut_value &&
158 min_cut_value == min_min_cut_value &&
159 min_min_cut_value == max_min_cut_value &&
160 min_cut_value == 2*flow_value,
161 "The max flow value or the three min cut values were not doubled");
166 for( int i=1; i==10; ++i ) {
171 preflow_test.flowMap(flow);
175 if ( tmp1 != INVALID ) s=tmp1;
179 if ( tmp2 != INVALID ) t=tmp2;
181 preflow_test.source(s);
182 preflow_test.target(t);
186 CutMap min_cut3(g,false);
187 preflow_test.minCut(min_cut3);
188 min_cut_value=cut_value(g,min_cut3,cap);
190 CutMap min_min_cut3(g,false);
191 preflow_test.minMinCut(min_min_cut3);
192 min_min_cut_value=cut_value(g,min_min_cut3,cap);
194 preflow_test.maxMinCut(max_min_cut);
195 max_min_cut_value=cut_value(g,max_min_cut,cap);
197 check(preflow_test.flowValue() == min_cut_value &&
198 min_cut_value == min_min_cut_value &&
199 min_min_cut_value == max_min_cut_value,
200 "The max flow value or the three min cut values are incorrect.");