1.1 --- a/lemon/edmonds_karp.h Thu Feb 28 18:13:48 2013 +0100
1.2 +++ b/lemon/edmonds_karp.h Thu Feb 28 23:44:35 2013 +0100
1.3 @@ -167,6 +167,8 @@
1.4
1.5 public:
1.6
1.7 + typedef EdmondsKarp Create;
1.8 +
1.9 ///\name Named template parameters
1.10
1.11 ///@{
2.1 --- a/test/CMakeLists.txt Thu Feb 28 18:13:48 2013 +0100
2.2 +++ b/test/CMakeLists.txt Thu Feb 28 23:44:35 2013 +0100
2.3 @@ -25,7 +25,6 @@
2.4 dijkstra_test
2.5 dim_test
2.6 edge_set_test
2.7 - edmonds_karp_test
2.8 error_test
2.9 euler_test
2.10 fractional_matching_test
2.11 @@ -42,13 +41,13 @@
2.12 matching_test
2.13 max_cardinality_search_test
2.14 max_clique_test
2.15 + max_flow_test
2.16 min_cost_arborescence_test
2.17 min_cost_flow_test
2.18 min_mean_cycle_test
2.19 nagamochi_ibaraki_test
2.20 path_test
2.21 planarity_test
2.22 - preflow_test
2.23 radix_sort_test
2.24 random_test
2.25 suurballe_test
3.1 --- a/test/edmonds_karp_test.cc Thu Feb 28 18:13:48 2013 +0100
3.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
3.3 @@ -1,236 +0,0 @@
3.4 -/* -*- mode: C++; indent-tabs-mode: nil; -*-
3.5 - *
3.6 - * This file is a part of LEMON, a generic C++ optimization library.
3.7 - *
3.8 - * Copyright (C) 2003-2010
3.9 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
3.10 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
3.11 - *
3.12 - * Permission to use, modify and distribute this software is granted
3.13 - * provided that this copyright notice appears in all copies. For
3.14 - * precise terms see the accompanying LICENSE file.
3.15 - *
3.16 - * This software is provided "AS IS" with no warranty of any kind,
3.17 - * express or implied, and with no claim as to its suitability for any
3.18 - * purpose.
3.19 - *
3.20 - */
3.21 -
3.22 -#include<iostream>
3.23 -
3.24 -#include "test_tools.h"
3.25 -#include<lemon/smart_graph.h>
3.26 -#include<lemon/edmonds_karp.h>
3.27 -#include <lemon/concepts/digraph.h>
3.28 -#include <lemon/concepts/maps.h>
3.29 -#include <lemon/lgf_reader.h>
3.30 -
3.31 -using namespace lemon;
3.32 -
3.33 -char test_lgf[] =
3.34 - "@nodes\n"
3.35 - "label\n"
3.36 - "0\n"
3.37 - "1\n"
3.38 - "2\n"
3.39 - "3\n"
3.40 - "4\n"
3.41 - "5\n"
3.42 - "6\n"
3.43 - "7\n"
3.44 - "8\n"
3.45 - "9\n"
3.46 - "@arcs\n"
3.47 - " label capacity\n"
3.48 - "0 1 0 20\n"
3.49 - "0 2 1 0\n"
3.50 - "1 1 2 3\n"
3.51 - "1 2 3 8\n"
3.52 - "1 3 4 8\n"
3.53 - "2 5 5 5\n"
3.54 - "3 2 6 5\n"
3.55 - "3 5 7 5\n"
3.56 - "3 6 8 5\n"
3.57 - "4 3 9 3\n"
3.58 - "5 7 10 3\n"
3.59 - "5 6 11 10\n"
3.60 - "5 8 12 10\n"
3.61 - "6 8 13 8\n"
3.62 - "8 9 14 20\n"
3.63 - "8 1 15 5\n"
3.64 - "9 5 16 5\n"
3.65 - "@attributes\n"
3.66 - "source 1\n"
3.67 - "target 8\n";
3.68 -
3.69 -void checkEdmondKarpCompile() {
3.70 - typedef int VType;
3.71 - typedef concepts::Digraph Digraph;
3.72 -
3.73 - typedef Digraph::Node Node;
3.74 - typedef Digraph::Arc Arc;
3.75 - typedef concepts::ReadMap<Arc,VType> CapMap;
3.76 - typedef concepts::ReadWriteMap<Arc,VType> FlowMap;
3.77 - typedef concepts::WriteMap<Node,bool> CutMap;
3.78 -
3.79 - Digraph g;
3.80 - Node n;
3.81 - Arc e;
3.82 - CapMap cap;
3.83 - FlowMap flow;
3.84 - CutMap cut;
3.85 - VType v;
3.86 - bool b;
3.87 - ignore_unused_variable_warning(v,b);
3.88 - typedef EdmondsKarp<Digraph, CapMap>
3.89 - ::SetFlowMap<FlowMap>
3.90 - ::Create EKType;
3.91 - EKType ek_test(g, cap, n, n);
3.92 - const EKType& const_ek_test = ek_test;
3.93 -
3.94 - EKType::Tolerance tol = const_ek_test.tolerance();
3.95 - ek_test.tolerance(tol);
3.96 -
3.97 - ek_test
3.98 - .capacityMap(cap)
3.99 - .flowMap(flow)
3.100 - .source(n)
3.101 - .target(n);
3.102 -
3.103 - ek_test.init();
3.104 - ek_test.start();
3.105 -
3.106 - v = const_ek_test.flowValue();
3.107 - v = const_ek_test.flow(e);
3.108 -
3.109 - const FlowMap& fm = const_ek_test.flowMap();
3.110 - b = const_ek_test.minCut(n);
3.111 - const_ek_test.minCutMap(cut);
3.112 -
3.113 - ignore_unused_variable_warning(fm);
3.114 -}
3.115 -
3.116 -int cutValue (const SmartDigraph& g,
3.117 - const SmartDigraph::NodeMap<bool>& cut,
3.118 - const SmartDigraph::ArcMap<int>& cap) {
3.119 -
3.120 - int c=0;
3.121 - for(SmartDigraph::ArcIt e(g); e!=INVALID; ++e) {
3.122 - if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e];
3.123 - }
3.124 - return c;
3.125 -}
3.126 -
3.127 -bool checkFlow(const SmartDigraph& g,
3.128 - const SmartDigraph::ArcMap<int>& flow,
3.129 - const SmartDigraph::ArcMap<int>& cap,
3.130 - SmartDigraph::Node s, SmartDigraph::Node t) {
3.131 -
3.132 - for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) {
3.133 - if (flow[e] < 0 || flow[e] > cap[e]) return false;
3.134 - }
3.135 -
3.136 - for (SmartDigraph::NodeIt n(g); n != INVALID; ++n) {
3.137 - if (n == s || n == t) continue;
3.138 - int sum = 0;
3.139 - for (SmartDigraph::OutArcIt e(g, n); e != INVALID; ++e) {
3.140 - sum += flow[e];
3.141 - }
3.142 - for (SmartDigraph::InArcIt e(g, n); e != INVALID; ++e) {
3.143 - sum -= flow[e];
3.144 - }
3.145 - if (sum != 0) return false;
3.146 - }
3.147 - return true;
3.148 -}
3.149 -
3.150 -int main() {
3.151 -
3.152 - typedef SmartDigraph Digraph;
3.153 -
3.154 - typedef Digraph::Node Node;
3.155 - typedef Digraph::NodeIt NodeIt;
3.156 - typedef Digraph::ArcIt ArcIt;
3.157 - typedef Digraph::ArcMap<int> CapMap;
3.158 - typedef Digraph::ArcMap<int> FlowMap;
3.159 - typedef Digraph::NodeMap<bool> CutMap;
3.160 -
3.161 - typedef EdmondsKarp<Digraph, CapMap> EKType;
3.162 -
3.163 - Digraph g;
3.164 - Node s, t;
3.165 - CapMap cap(g);
3.166 - std::istringstream input(test_lgf);
3.167 - DigraphReader<Digraph>(g,input).
3.168 - arcMap("capacity", cap).
3.169 - node("source",s).
3.170 - node("target",t).
3.171 - run();
3.172 -
3.173 - EKType ek_test(g, cap, s, t);
3.174 - ek_test.run();
3.175 -
3.176 - check(checkFlow(g, ek_test.flowMap(), cap, s, t),
3.177 - "The flow is not feasible.");
3.178 -
3.179 - CutMap min_cut(g);
3.180 - ek_test.minCutMap(min_cut);
3.181 - int min_cut_value=cutValue(g,min_cut,cap);
3.182 -
3.183 - check(ek_test.flowValue() == min_cut_value,
3.184 - "The max flow value is not equal to the three min cut values.");
3.185 -
3.186 - FlowMap flow(g);
3.187 - for(ArcIt e(g); e!=INVALID; ++e) flow[e] = ek_test.flowMap()[e];
3.188 -
3.189 - int flow_value=ek_test.flowValue();
3.190 -
3.191 - for(ArcIt e(g); e!=INVALID; ++e) cap[e]=2*cap[e];
3.192 - ek_test.init(flow);
3.193 - ek_test.start();
3.194 -
3.195 - CutMap min_cut1(g);
3.196 - ek_test.minCutMap(min_cut1);
3.197 - min_cut_value=cutValue(g,min_cut1,cap);
3.198 -
3.199 - check(ek_test.flowValue() == min_cut_value &&
3.200 - min_cut_value == 2*flow_value,
3.201 - "The max flow value or the min cut value is wrong.");
3.202 -
3.203 - check(checkFlow(g, ek_test.flowMap(), cap, s, t),
3.204 - "The flow is not feasible.");
3.205 -
3.206 - CutMap min_cut2(g);
3.207 - ek_test.minCutMap(min_cut2);
3.208 - min_cut_value=cutValue(g,min_cut2,cap);
3.209 -
3.210 - check(ek_test.flowValue() == min_cut_value &&
3.211 - min_cut_value == 2*flow_value,
3.212 - "The max flow value or the three min cut values were not doubled.");
3.213 -
3.214 -
3.215 - ek_test.flowMap(flow);
3.216 -
3.217 - NodeIt tmp1(g,s);
3.218 - ++tmp1;
3.219 - if ( tmp1 != INVALID ) s=tmp1;
3.220 -
3.221 - NodeIt tmp2(g,t);
3.222 - ++tmp2;
3.223 - if ( tmp2 != INVALID ) t=tmp2;
3.224 -
3.225 - ek_test.source(s);
3.226 - ek_test.target(t);
3.227 -
3.228 - ek_test.run();
3.229 -
3.230 - CutMap min_cut3(g);
3.231 - ek_test.minCutMap(min_cut3);
3.232 - min_cut_value=cutValue(g,min_cut3,cap);
3.233 -
3.234 -
3.235 - check(ek_test.flowValue() == min_cut_value,
3.236 - "The max flow value or the three min cut values are incorrect.");
3.237 -
3.238 - return 0;
3.239 -}
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/test/max_flow_test.cc Thu Feb 28 23:44:35 2013 +0100
4.3 @@ -0,0 +1,395 @@
4.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
4.5 + *
4.6 + * This file is a part of LEMON, a generic C++ optimization library.
4.7 + *
4.8 + * Copyright (C) 2003-2010
4.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
4.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
4.11 + *
4.12 + * Permission to use, modify and distribute this software is granted
4.13 + * provided that this copyright notice appears in all copies. For
4.14 + * precise terms see the accompanying LICENSE file.
4.15 + *
4.16 + * This software is provided "AS IS" with no warranty of any kind,
4.17 + * express or implied, and with no claim as to its suitability for any
4.18 + * purpose.
4.19 + *
4.20 + */
4.21 +
4.22 +#include <iostream>
4.23 +
4.24 +#include "test_tools.h"
4.25 +#include <lemon/smart_graph.h>
4.26 +#include <lemon/preflow.h>
4.27 +#include <lemon/edmonds_karp.h>
4.28 +#include <lemon/concepts/digraph.h>
4.29 +#include <lemon/concepts/maps.h>
4.30 +#include <lemon/lgf_reader.h>
4.31 +#include <lemon/elevator.h>
4.32 +
4.33 +using namespace lemon;
4.34 +
4.35 +char test_lgf[] =
4.36 + "@nodes\n"
4.37 + "label\n"
4.38 + "0\n"
4.39 + "1\n"
4.40 + "2\n"
4.41 + "3\n"
4.42 + "4\n"
4.43 + "5\n"
4.44 + "6\n"
4.45 + "7\n"
4.46 + "8\n"
4.47 + "9\n"
4.48 + "@arcs\n"
4.49 + " label capacity\n"
4.50 + "0 1 0 20\n"
4.51 + "0 2 1 0\n"
4.52 + "1 1 2 3\n"
4.53 + "1 2 3 8\n"
4.54 + "1 3 4 8\n"
4.55 + "2 5 5 5\n"
4.56 + "3 2 6 5\n"
4.57 + "3 5 7 5\n"
4.58 + "3 6 8 5\n"
4.59 + "4 3 9 3\n"
4.60 + "5 7 10 3\n"
4.61 + "5 6 11 10\n"
4.62 + "5 8 12 10\n"
4.63 + "6 8 13 8\n"
4.64 + "8 9 14 20\n"
4.65 + "8 1 15 5\n"
4.66 + "9 5 16 5\n"
4.67 + "@attributes\n"
4.68 + "source 1\n"
4.69 + "target 8\n";
4.70 +
4.71 +
4.72 +// Checks the general interface of a max flow algorithm
4.73 +template <typename GR, typename CAP>
4.74 +struct MaxFlowClassConcept
4.75 +{
4.76 +
4.77 + template <typename MF>
4.78 + struct Constraints {
4.79 +
4.80 + typedef typename GR::Node Node;
4.81 + typedef typename GR::Arc Arc;
4.82 + typedef typename CAP::Value Value;
4.83 + typedef concepts::ReadWriteMap<Arc, Value> FlowMap;
4.84 + typedef concepts::WriteMap<Node, bool> CutMap;
4.85 +
4.86 + GR g;
4.87 + Node n;
4.88 + Arc e;
4.89 + CAP cap;
4.90 + FlowMap flow;
4.91 + CutMap cut;
4.92 + Value v;
4.93 + bool b;
4.94 +
4.95 + void constraints() {
4.96 + checkConcept<concepts::Digraph, GR>();
4.97 +
4.98 + const Constraints& me = *this;
4.99 +
4.100 + typedef typename MF
4.101 + ::template SetFlowMap<FlowMap>
4.102 + ::Create MaxFlowType;
4.103 + typedef typename MF::Create MaxFlowType2;
4.104 + MaxFlowType max_flow(me.g, me.cap, me.n, me.n);
4.105 + const MaxFlowType& const_max_flow = max_flow;
4.106 +
4.107 + max_flow
4.108 + .capacityMap(cap)
4.109 + .flowMap(flow)
4.110 + .source(n)
4.111 + .target(n);
4.112 +
4.113 + typename MaxFlowType::Tolerance tol = const_max_flow.tolerance();
4.114 + max_flow.tolerance(tol);
4.115 +
4.116 + max_flow.init();
4.117 + max_flow.init(cap);
4.118 + max_flow.run();
4.119 +
4.120 + v = const_max_flow.flowValue();
4.121 + v = const_max_flow.flow(e);
4.122 + const FlowMap& fm = const_max_flow.flowMap();
4.123 +
4.124 + b = const_max_flow.minCut(n);
4.125 + const_max_flow.minCutMap(cut);
4.126 +
4.127 + ignore_unused_variable_warning(fm);
4.128 + }
4.129 +
4.130 + };
4.131 +
4.132 +};
4.133 +
4.134 +// Checks the specific parts of Preflow's interface
4.135 +void checkPreflowCompile()
4.136 +{
4.137 + typedef int Value;
4.138 + typedef concepts::Digraph Digraph;
4.139 + typedef concepts::ReadMap<Digraph::Arc, Value> CapMap;
4.140 + typedef Elevator<Digraph, Digraph::Node> Elev;
4.141 + typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev;
4.142 +
4.143 + Digraph g;
4.144 + Digraph::Node n;
4.145 + CapMap cap;
4.146 +
4.147 + typedef Preflow<Digraph, CapMap>
4.148 + ::SetElevator<Elev>
4.149 + ::SetStandardElevator<LinkedElev>
4.150 + ::Create PreflowType;
4.151 + PreflowType preflow_test(g, cap, n, n);
4.152 + const PreflowType& const_preflow_test = preflow_test;
4.153 +
4.154 + const PreflowType::Elevator& elev = const_preflow_test.elevator();
4.155 + preflow_test.elevator(const_cast<PreflowType::Elevator&>(elev));
4.156 +
4.157 + bool b = preflow_test.init(cap);
4.158 + preflow_test.startFirstPhase();
4.159 + preflow_test.startSecondPhase();
4.160 + preflow_test.runMinCut();
4.161 +
4.162 + ignore_unused_variable_warning(b);
4.163 +}
4.164 +
4.165 +// Checks the specific parts of EdmondsKarp's interface
4.166 +void checkEdmondsKarpCompile()
4.167 +{
4.168 + typedef int Value;
4.169 + typedef concepts::Digraph Digraph;
4.170 + typedef concepts::ReadMap<Digraph::Arc, Value> CapMap;
4.171 + typedef Elevator<Digraph, Digraph::Node> Elev;
4.172 + typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev;
4.173 +
4.174 + Digraph g;
4.175 + Digraph::Node n;
4.176 + CapMap cap;
4.177 +
4.178 + EdmondsKarp<Digraph, CapMap> ek_test(g, cap, n, n);
4.179 +
4.180 + ek_test.init(cap);
4.181 + bool b = ek_test.checkedInit(cap);
4.182 + b = ek_test.augment();
4.183 + ek_test.start();
4.184 +
4.185 + ignore_unused_variable_warning(b);
4.186 +}
4.187 +
4.188 +
4.189 +template <typename T>
4.190 +T cutValue (const SmartDigraph& g,
4.191 + const SmartDigraph::NodeMap<bool>& cut,
4.192 + const SmartDigraph::ArcMap<T>& cap) {
4.193 +
4.194 + T c=0;
4.195 + for(SmartDigraph::ArcIt e(g); e!=INVALID; ++e) {
4.196 + if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e];
4.197 + }
4.198 + return c;
4.199 +}
4.200 +
4.201 +template <typename T>
4.202 +bool checkFlow(const SmartDigraph& g,
4.203 + const SmartDigraph::ArcMap<T>& flow,
4.204 + const SmartDigraph::ArcMap<T>& cap,
4.205 + SmartDigraph::Node s, SmartDigraph::Node t) {
4.206 +
4.207 + for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) {
4.208 + if (flow[e] < 0 || flow[e] > cap[e]) return false;
4.209 + }
4.210 +
4.211 + for (SmartDigraph::NodeIt n(g); n != INVALID; ++n) {
4.212 + if (n == s || n == t) continue;
4.213 + T sum = 0;
4.214 + for (SmartDigraph::OutArcIt e(g, n); e != INVALID; ++e) {
4.215 + sum += flow[e];
4.216 + }
4.217 + for (SmartDigraph::InArcIt e(g, n); e != INVALID; ++e) {
4.218 + sum -= flow[e];
4.219 + }
4.220 + if (sum != 0) return false;
4.221 + }
4.222 + return true;
4.223 +}
4.224 +
4.225 +void initFlowTest()
4.226 +{
4.227 + DIGRAPH_TYPEDEFS(SmartDigraph);
4.228 +
4.229 + SmartDigraph g;
4.230 + SmartDigraph::ArcMap<int> cap(g),iflow(g);
4.231 + Node s=g.addNode(); Node t=g.addNode();
4.232 + Node n1=g.addNode(); Node n2=g.addNode();
4.233 + Arc a;
4.234 + a=g.addArc(s,n1); cap[a]=20; iflow[a]=20;
4.235 + a=g.addArc(n1,n2); cap[a]=10; iflow[a]=0;
4.236 + a=g.addArc(n2,t); cap[a]=20; iflow[a]=0;
4.237 +
4.238 + Preflow<SmartDigraph> pre(g,cap,s,t);
4.239 + pre.init(iflow);
4.240 + pre.startFirstPhase();
4.241 + check(pre.flowValue() == 10, "The incorrect max flow value.");
4.242 + check(pre.minCut(s), "Wrong min cut (Node s).");
4.243 + check(pre.minCut(n1), "Wrong min cut (Node n1).");
4.244 + check(!pre.minCut(n2), "Wrong min cut (Node n2).");
4.245 + check(!pre.minCut(t), "Wrong min cut (Node t).");
4.246 +}
4.247 +
4.248 +template <typename MF, typename SF>
4.249 +void checkMaxFlowAlg() {
4.250 + typedef SmartDigraph Digraph;
4.251 + DIGRAPH_TYPEDEFS(Digraph);
4.252 +
4.253 + typedef typename MF::Value Value;
4.254 + typedef Digraph::ArcMap<Value> CapMap;
4.255 + typedef CapMap FlowMap;
4.256 + typedef BoolNodeMap CutMap;
4.257 +
4.258 + Digraph g;
4.259 + Node s, t;
4.260 + CapMap cap(g);
4.261 + std::istringstream input(test_lgf);
4.262 + DigraphReader<Digraph>(g,input)
4.263 + .arcMap("capacity", cap)
4.264 + .node("source",s)
4.265 + .node("target",t)
4.266 + .run();
4.267 +
4.268 + MF max_flow(g, cap, s, t);
4.269 + max_flow.run();
4.270 +
4.271 + check(checkFlow(g, max_flow.flowMap(), cap, s, t),
4.272 + "The flow is not feasible.");
4.273 +
4.274 + CutMap min_cut(g);
4.275 + max_flow.minCutMap(min_cut);
4.276 + Value min_cut_value = cutValue(g, min_cut, cap);
4.277 +
4.278 + check(max_flow.flowValue() == min_cut_value,
4.279 + "The max flow value is not equal to the min cut value.");
4.280 +
4.281 + FlowMap flow(g);
4.282 + for (ArcIt e(g); e != INVALID; ++e) flow[e] = max_flow.flowMap()[e];
4.283 +
4.284 + Value flow_value = max_flow.flowValue();
4.285 +
4.286 + for (ArcIt e(g); e != INVALID; ++e) cap[e] = 2 * cap[e];
4.287 + max_flow.init(flow);
4.288 +
4.289 + SF::startFirstPhase(max_flow); // start first phase of the algorithm
4.290 +
4.291 + CutMap min_cut1(g);
4.292 + max_flow.minCutMap(min_cut1);
4.293 + min_cut_value = cutValue(g, min_cut1, cap);
4.294 +
4.295 + check(max_flow.flowValue() == min_cut_value &&
4.296 + min_cut_value == 2 * flow_value,
4.297 + "The max flow value or the min cut value is wrong.");
4.298 +
4.299 + SF::startSecondPhase(max_flow); // start second phase of the algorithm
4.300 +
4.301 + check(checkFlow(g, max_flow.flowMap(), cap, s, t),
4.302 + "The flow is not feasible.");
4.303 +
4.304 + CutMap min_cut2(g);
4.305 + max_flow.minCutMap(min_cut2);
4.306 + min_cut_value = cutValue(g, min_cut2, cap);
4.307 +
4.308 + check(max_flow.flowValue() == min_cut_value &&
4.309 + min_cut_value == 2 * flow_value,
4.310 + "The max flow value or the min cut value was not doubled");
4.311 +
4.312 +
4.313 + max_flow.flowMap(flow);
4.314 +
4.315 + NodeIt tmp1(g, s);
4.316 + ++tmp1;
4.317 + if (tmp1 != INVALID) s = tmp1;
4.318 +
4.319 + NodeIt tmp2(g, t);
4.320 + ++tmp2;
4.321 + if (tmp2 != INVALID) t = tmp2;
4.322 +
4.323 + max_flow.source(s);
4.324 + max_flow.target(t);
4.325 +
4.326 + max_flow.run();
4.327 +
4.328 + CutMap min_cut3(g);
4.329 + max_flow.minCutMap(min_cut3);
4.330 + min_cut_value=cutValue(g, min_cut3, cap);
4.331 +
4.332 + check(max_flow.flowValue() == min_cut_value,
4.333 + "The max flow value or the min cut value is wrong.");
4.334 +}
4.335 +
4.336 +// Struct for calling start functions of a general max flow algorithm
4.337 +template <typename MF>
4.338 +struct GeneralStartFunctions {
4.339 +
4.340 + static void startFirstPhase(MF& mf) {
4.341 + mf.start();
4.342 + }
4.343 +
4.344 + static void startSecondPhase(MF& mf) {
4.345 + ignore_unused_variable_warning(mf);
4.346 + }
4.347 +
4.348 +};
4.349 +
4.350 +// Struct for calling start functions of Preflow
4.351 +template <typename MF>
4.352 +struct PreflowStartFunctions {
4.353 +
4.354 + static void startFirstPhase(MF& mf) {
4.355 + mf.startFirstPhase();
4.356 + }
4.357 +
4.358 + static void startSecondPhase(MF& mf) {
4.359 + mf.startSecondPhase();
4.360 + }
4.361 +
4.362 +};
4.363 +
4.364 +int main() {
4.365 +
4.366 + typedef concepts::Digraph GR;
4.367 + typedef concepts::ReadMap<GR::Arc, int> CM1;
4.368 + typedef concepts::ReadMap<GR::Arc, double> CM2;
4.369 +
4.370 + // Check the interface of Preflow
4.371 + checkConcept< MaxFlowClassConcept<GR, CM1>,
4.372 + Preflow<GR, CM1> >();
4.373 + checkConcept< MaxFlowClassConcept<GR, CM2>,
4.374 + Preflow<GR, CM2> >();
4.375 +
4.376 + // Check the interface of EdmondsKarp
4.377 + checkConcept< MaxFlowClassConcept<GR, CM1>,
4.378 + EdmondsKarp<GR, CM1> >();
4.379 + checkConcept< MaxFlowClassConcept<GR, CM2>,
4.380 + EdmondsKarp<GR, CM2> >();
4.381 +
4.382 + // Check Preflow
4.383 + typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<int> > PType1;
4.384 + typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<float> > PType2;
4.385 + checkMaxFlowAlg<PType1, PreflowStartFunctions<PType1> >();
4.386 + checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >();
4.387 + initFlowTest();
4.388 +
4.389 + // Check EdmondsKarp
4.390 + typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<int> > EKType1;
4.391 + typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<float> > EKType2;
4.392 + checkMaxFlowAlg<EKType1, GeneralStartFunctions<EKType1> >();
4.393 + checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >();
4.394 +
4.395 + initFlowTest();
4.396 +
4.397 + return 0;
4.398 +}
5.1 --- a/test/preflow_test.cc Thu Feb 28 18:13:48 2013 +0100
5.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
5.3 @@ -1,277 +0,0 @@
5.4 -/* -*- mode: C++; indent-tabs-mode: nil; -*-
5.5 - *
5.6 - * This file is a part of LEMON, a generic C++ optimization library.
5.7 - *
5.8 - * Copyright (C) 2003-2010
5.9 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5.10 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
5.11 - *
5.12 - * Permission to use, modify and distribute this software is granted
5.13 - * provided that this copyright notice appears in all copies. For
5.14 - * precise terms see the accompanying LICENSE file.
5.15 - *
5.16 - * This software is provided "AS IS" with no warranty of any kind,
5.17 - * express or implied, and with no claim as to its suitability for any
5.18 - * purpose.
5.19 - *
5.20 - */
5.21 -
5.22 -#include <iostream>
5.23 -
5.24 -#include "test_tools.h"
5.25 -#include <lemon/smart_graph.h>
5.26 -#include <lemon/preflow.h>
5.27 -#include <lemon/concepts/digraph.h>
5.28 -#include <lemon/concepts/maps.h>
5.29 -#include <lemon/lgf_reader.h>
5.30 -#include <lemon/elevator.h>
5.31 -
5.32 -using namespace lemon;
5.33 -
5.34 -char test_lgf[] =
5.35 - "@nodes\n"
5.36 - "label\n"
5.37 - "0\n"
5.38 - "1\n"
5.39 - "2\n"
5.40 - "3\n"
5.41 - "4\n"
5.42 - "5\n"
5.43 - "6\n"
5.44 - "7\n"
5.45 - "8\n"
5.46 - "9\n"
5.47 - "@arcs\n"
5.48 - " label capacity\n"
5.49 - "0 1 0 20\n"
5.50 - "0 2 1 0\n"
5.51 - "1 1 2 3\n"
5.52 - "1 2 3 8\n"
5.53 - "1 3 4 8\n"
5.54 - "2 5 5 5\n"
5.55 - "3 2 6 5\n"
5.56 - "3 5 7 5\n"
5.57 - "3 6 8 5\n"
5.58 - "4 3 9 3\n"
5.59 - "5 7 10 3\n"
5.60 - "5 6 11 10\n"
5.61 - "5 8 12 10\n"
5.62 - "6 8 13 8\n"
5.63 - "8 9 14 20\n"
5.64 - "8 1 15 5\n"
5.65 - "9 5 16 5\n"
5.66 - "@attributes\n"
5.67 - "source 1\n"
5.68 - "target 8\n";
5.69 -
5.70 -void checkPreflowCompile()
5.71 -{
5.72 - typedef int VType;
5.73 - typedef concepts::Digraph Digraph;
5.74 -
5.75 - typedef Digraph::Node Node;
5.76 - typedef Digraph::Arc Arc;
5.77 - typedef concepts::ReadMap<Arc,VType> CapMap;
5.78 - typedef concepts::ReadWriteMap<Arc,VType> FlowMap;
5.79 - typedef concepts::WriteMap<Node,bool> CutMap;
5.80 -
5.81 - typedef Elevator<Digraph, Digraph::Node> Elev;
5.82 - typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev;
5.83 -
5.84 - Digraph g;
5.85 - Node n;
5.86 - Arc e;
5.87 - CapMap cap;
5.88 - FlowMap flow;
5.89 - CutMap cut;
5.90 - VType v;
5.91 - bool b;
5.92 - ignore_unused_variable_warning(v,b);
5.93 -
5.94 - typedef Preflow<Digraph, CapMap>
5.95 - ::SetFlowMap<FlowMap>
5.96 - ::SetElevator<Elev>
5.97 - ::SetStandardElevator<LinkedElev>
5.98 - ::Create PreflowType;
5.99 - PreflowType preflow_test(g, cap, n, n);
5.100 - const PreflowType& const_preflow_test = preflow_test;
5.101 -
5.102 - const PreflowType::Elevator& elev = const_preflow_test.elevator();
5.103 - preflow_test.elevator(const_cast<PreflowType::Elevator&>(elev));
5.104 - PreflowType::Tolerance tol = const_preflow_test.tolerance();
5.105 - preflow_test.tolerance(tol);
5.106 -
5.107 - preflow_test
5.108 - .capacityMap(cap)
5.109 - .flowMap(flow)
5.110 - .source(n)
5.111 - .target(n);
5.112 -
5.113 - preflow_test.init();
5.114 - preflow_test.init(cap);
5.115 - preflow_test.startFirstPhase();
5.116 - preflow_test.startSecondPhase();
5.117 - preflow_test.run();
5.118 - preflow_test.runMinCut();
5.119 -
5.120 - v = const_preflow_test.flowValue();
5.121 - v = const_preflow_test.flow(e);
5.122 - const FlowMap& fm = const_preflow_test.flowMap();
5.123 - b = const_preflow_test.minCut(n);
5.124 - const_preflow_test.minCutMap(cut);
5.125 -
5.126 - ignore_unused_variable_warning(fm);
5.127 -}
5.128 -
5.129 -int cutValue (const SmartDigraph& g,
5.130 - const SmartDigraph::NodeMap<bool>& cut,
5.131 - const SmartDigraph::ArcMap<int>& cap) {
5.132 -
5.133 - int c=0;
5.134 - for(SmartDigraph::ArcIt e(g); e!=INVALID; ++e) {
5.135 - if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e];
5.136 - }
5.137 - return c;
5.138 -}
5.139 -
5.140 -bool checkFlow(const SmartDigraph& g,
5.141 - const SmartDigraph::ArcMap<int>& flow,
5.142 - const SmartDigraph::ArcMap<int>& cap,
5.143 - SmartDigraph::Node s, SmartDigraph::Node t) {
5.144 -
5.145 - for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) {
5.146 - if (flow[e] < 0 || flow[e] > cap[e]) return false;
5.147 - }
5.148 -
5.149 - for (SmartDigraph::NodeIt n(g); n != INVALID; ++n) {
5.150 - if (n == s || n == t) continue;
5.151 - int sum = 0;
5.152 - for (SmartDigraph::OutArcIt e(g, n); e != INVALID; ++e) {
5.153 - sum += flow[e];
5.154 - }
5.155 - for (SmartDigraph::InArcIt e(g, n); e != INVALID; ++e) {
5.156 - sum -= flow[e];
5.157 - }
5.158 - if (sum != 0) return false;
5.159 - }
5.160 - return true;
5.161 -}
5.162 -
5.163 -void initFlowTest()
5.164 -{
5.165 - DIGRAPH_TYPEDEFS(SmartDigraph);
5.166 -
5.167 - SmartDigraph g;
5.168 - SmartDigraph::ArcMap<int> cap(g),iflow(g);
5.169 - Node s=g.addNode(); Node t=g.addNode();
5.170 - Node n1=g.addNode(); Node n2=g.addNode();
5.171 - Arc a;
5.172 - a=g.addArc(s,n1); cap[a]=20; iflow[a]=20;
5.173 - a=g.addArc(n1,n2); cap[a]=10; iflow[a]=0;
5.174 - a=g.addArc(n2,t); cap[a]=20; iflow[a]=0;
5.175 -
5.176 - Preflow<SmartDigraph> pre(g,cap,s,t);
5.177 - pre.init(iflow);
5.178 - pre.startFirstPhase();
5.179 - check(pre.flowValue() == 10, "The incorrect max flow value.");
5.180 - check(pre.minCut(s), "Wrong min cut (Node s).");
5.181 - check(pre.minCut(n1), "Wrong min cut (Node n1).");
5.182 - check(!pre.minCut(n2), "Wrong min cut (Node n2).");
5.183 - check(!pre.minCut(t), "Wrong min cut (Node t).");
5.184 -}
5.185 -
5.186 -
5.187 -int main() {
5.188 -
5.189 - typedef SmartDigraph Digraph;
5.190 -
5.191 - typedef Digraph::Node Node;
5.192 - typedef Digraph::NodeIt NodeIt;
5.193 - typedef Digraph::ArcIt ArcIt;
5.194 - typedef Digraph::ArcMap<int> CapMap;
5.195 - typedef Digraph::ArcMap<int> FlowMap;
5.196 - typedef Digraph::NodeMap<bool> CutMap;
5.197 -
5.198 - typedef Preflow<Digraph, CapMap> PType;
5.199 -
5.200 - Digraph g;
5.201 - Node s, t;
5.202 - CapMap cap(g);
5.203 - std::istringstream input(test_lgf);
5.204 - DigraphReader<Digraph>(g,input).
5.205 - arcMap("capacity", cap).
5.206 - node("source",s).
5.207 - node("target",t).
5.208 - run();
5.209 -
5.210 - PType preflow_test(g, cap, s, t);
5.211 - preflow_test.run();
5.212 -
5.213 - check(checkFlow(g, preflow_test.flowMap(), cap, s, t),
5.214 - "The flow is not feasible.");
5.215 -
5.216 - CutMap min_cut(g);
5.217 - preflow_test.minCutMap(min_cut);
5.218 - int min_cut_value=cutValue(g,min_cut,cap);
5.219 -
5.220 - check(preflow_test.flowValue() == min_cut_value,
5.221 - "The max flow value is not equal to the three min cut values.");
5.222 -
5.223 - FlowMap flow(g);
5.224 - for(ArcIt e(g); e!=INVALID; ++e) flow[e] = preflow_test.flowMap()[e];
5.225 -
5.226 - int flow_value=preflow_test.flowValue();
5.227 -
5.228 - for(ArcIt e(g); e!=INVALID; ++e) cap[e]=2*cap[e];
5.229 - preflow_test.init(flow);
5.230 - preflow_test.startFirstPhase();
5.231 -
5.232 - CutMap min_cut1(g);
5.233 - preflow_test.minCutMap(min_cut1);
5.234 - min_cut_value=cutValue(g,min_cut1,cap);
5.235 -
5.236 - check(preflow_test.flowValue() == min_cut_value &&
5.237 - min_cut_value == 2*flow_value,
5.238 - "The max flow value or the min cut value is wrong.");
5.239 -
5.240 - preflow_test.startSecondPhase();
5.241 -
5.242 - check(checkFlow(g, preflow_test.flowMap(), cap, s, t),
5.243 - "The flow is not feasible.");
5.244 -
5.245 - CutMap min_cut2(g);
5.246 - preflow_test.minCutMap(min_cut2);
5.247 - min_cut_value=cutValue(g,min_cut2,cap);
5.248 -
5.249 - check(preflow_test.flowValue() == min_cut_value &&
5.250 - min_cut_value == 2*flow_value,
5.251 - "The max flow value or the three min cut values were not doubled");
5.252 -
5.253 -
5.254 - preflow_test.flowMap(flow);
5.255 -
5.256 - NodeIt tmp1(g,s);
5.257 - ++tmp1;
5.258 - if ( tmp1 != INVALID ) s=tmp1;
5.259 -
5.260 - NodeIt tmp2(g,t);
5.261 - ++tmp2;
5.262 - if ( tmp2 != INVALID ) t=tmp2;
5.263 -
5.264 - preflow_test.source(s);
5.265 - preflow_test.target(t);
5.266 -
5.267 - preflow_test.run();
5.268 -
5.269 - CutMap min_cut3(g);
5.270 - preflow_test.minCutMap(min_cut3);
5.271 - min_cut_value=cutValue(g,min_cut3,cap);
5.272 -
5.273 -
5.274 - check(preflow_test.flowValue() == min_cut_value,
5.275 - "The max flow value or the three min cut values are incorrect.");
5.276 -
5.277 - initFlowTest();
5.278 -
5.279 - return 0;
5.280 -}