The graph adadptors can be alteration observed.
In most cases it uses the adapted graph alteration notifiers.
Only special case is now the UndirGraphAdaptor, where
we have to proxy the signals from the graph.
The SubBidirGraphAdaptor is removed, because it doest not
gives more feature than the EdgeSubGraphAdaptor<UndirGraphAdaptor<Graph>>.
The ResGraphAdaptor is based on this composition.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
22 #include "test_tools.h"
23 #include <lemon/smart_graph.h>
24 #include <lemon/dimacs.h>
25 #include <lemon/preflow.h>
26 #include <lemon/concept/graph.h>
27 #include <lemon/concept/maps.h>
29 using namespace lemon;
34 typedef concept::StaticGraph Graph;
36 typedef Graph::Node Node;
37 typedef Graph::Edge Edge;
38 typedef concept::ReadMap<Edge,VType> CapMap;
39 typedef concept::ReadWriteMap<Edge,VType> FlowMap;
40 typedef concept::ReadWriteMap<Node,bool> CutMap;
42 typedef Preflow<Graph, int, CapMap, FlowMap> PType;
50 PType preflow_test(g,n,n,cap,flow);
53 preflow_test.flowValue();
54 preflow_test.source(n);
55 preflow_test.flowMap(flow);
57 preflow_test.phase1(PType::NO_FLOW);
58 preflow_test.minCut(cut);
60 preflow_test.phase2();
61 preflow_test.target(n);
62 preflow_test.capacityMap(cap);
63 preflow_test.minMinCut(cut);
64 preflow_test.maxMinCut(cut);
67 int cut_value ( SmartGraph& g, SmartGraph::NodeMap<bool>& cut,
68 SmartGraph::EdgeMap<int>& cap) {
71 for(SmartGraph::EdgeIt e(g); e!=INVALID; ++e) {
72 if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e];
79 typedef SmartGraph Graph;
81 typedef Graph::Node Node;
82 typedef Graph::NodeIt NodeIt;
83 typedef Graph::EdgeIt EdgeIt;
84 typedef Graph::EdgeMap<int> CapMap;
85 typedef Graph::EdgeMap<int> FlowMap;
86 typedef Graph::NodeMap<bool> CutMap;
88 typedef Preflow<Graph, int> PType;
91 if( getenv("srcdir") )
92 f_name = std::string(getenv("srcdir"));
94 f_name += "/preflow_graph.dim";
96 std::ifstream file(f_name.c_str());
98 check(file, "Input file '" << f_name << "' not found.");
103 readDimacs(file, g, cap, s, t);
109 PType preflow_test(g, s, t, cap, flow);
110 preflow_test.run(PType::ZERO_FLOW);
112 CutMap min_cut(g,false);
113 preflow_test.minCut(min_cut);
114 int min_cut_value=cut_value(g,min_cut,cap);
116 CutMap min_min_cut(g,false);
117 preflow_test.minMinCut(min_min_cut);
118 int min_min_cut_value=cut_value(g,min_min_cut,cap);
120 CutMap max_min_cut(g,false);
121 preflow_test.maxMinCut(max_min_cut);
122 int max_min_cut_value=cut_value(g,max_min_cut,cap);
124 check(preflow_test.flowValue() == min_cut_value &&
125 min_cut_value == min_min_cut_value &&
126 min_min_cut_value == max_min_cut_value,
127 "The max flow value is not equal to the three min cut values.");
129 int flow_value=preflow_test.flowValue();
133 for(EdgeIt e(g); e!=INVALID; ++e) cap[e]=2*cap[e];
134 preflow_test.capacityMap(cap);
136 preflow_test.phase1(PType::PRE_FLOW);
138 CutMap min_cut1(g,false);
139 preflow_test.minCut(min_cut1);
140 min_cut_value=cut_value(g,min_cut1,cap);
142 check(preflow_test.flowValue() == min_cut_value &&
143 min_cut_value == 2*flow_value,
144 "The max flow value or the min cut value is wrong.");
146 preflow_test.phase2();
148 CutMap min_cut2(g,false);
149 preflow_test.minCut(min_cut2);
150 min_cut_value=cut_value(g,min_cut2,cap);
152 CutMap min_min_cut2(g,false);
153 preflow_test.minMinCut(min_min_cut2);
154 min_min_cut_value=cut_value(g,min_min_cut2,cap);
156 preflow_test.maxMinCut(max_min_cut);
157 max_min_cut_value=cut_value(g,max_min_cut,cap);
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 min_cut_value == 2*flow_value,
163 "The max flow value or the three min cut values were not doubled");
168 for( int i=1; i==10; ++i ) {
173 preflow_test.flowMap(flow);
177 if ( tmp1 != INVALID ) s=tmp1;
181 if ( tmp2 != INVALID ) t=tmp2;
183 preflow_test.source(s);
184 preflow_test.target(t);
188 CutMap min_cut3(g,false);
189 preflow_test.minCut(min_cut3);
190 min_cut_value=cut_value(g,min_cut3,cap);
192 CutMap min_min_cut3(g,false);
193 preflow_test.minMinCut(min_min_cut3);
194 min_min_cut_value=cut_value(g,min_min_cut3,cap);
196 preflow_test.maxMinCut(max_min_cut);
197 max_min_cut_value=cut_value(g,max_min_cut,cap);
199 check(preflow_test.flowValue() == min_cut_value &&
200 min_cut_value == min_min_cut_value &&
201 min_min_cut_value == max_min_cut_value,
202 "The max flow value or the three min cut values are incorrect.");