alpar@389: /* -*- mode: C++; indent-tabs-mode: nil; -*- alpar@389: * alpar@389: * This file is a part of LEMON, a generic C++ optimization library. alpar@389: * alpar@389: * Copyright (C) 2003-2008 alpar@389: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@389: * (Egervary Research Group on Combinatorial Optimization, EGRES). alpar@389: * alpar@389: * Permission to use, modify and distribute this software is granted alpar@389: * provided that this copyright notice appears in all copies. For alpar@389: * precise terms see the accompanying LICENSE file. alpar@389: * alpar@389: * This software is provided "AS IS" with no warranty of any kind, alpar@389: * express or implied, and with no claim as to its suitability for any alpar@389: * purpose. alpar@389: * alpar@389: */ alpar@389: alpar@389: #include alpar@389: #include alpar@389: alpar@389: #include "test_tools.h" alpar@389: #include alpar@389: #include alpar@389: #include alpar@389: #include alpar@389: #include alpar@389: alpar@389: using namespace lemon; alpar@389: alpar@389: void checkPreflow() alpar@389: { alpar@389: typedef int VType; alpar@389: typedef concepts::Digraph Digraph; alpar@389: alpar@389: typedef Digraph::Node Node; alpar@389: typedef Digraph::Arc Arc; alpar@389: typedef concepts::ReadMap CapMap; alpar@389: typedef concepts::ReadWriteMap FlowMap; alpar@389: typedef concepts::WriteMap CutMap; alpar@389: alpar@389: Digraph g; alpar@389: Node n; alpar@389: Arc e; alpar@389: CapMap cap; alpar@389: FlowMap flow; alpar@389: CutMap cut; alpar@389: alpar@391: Preflow::SetFlowMap::Create preflow_test(g,cap,n,n); alpar@389: alpar@389: preflow_test.capacityMap(cap); alpar@389: flow = preflow_test.flowMap(); alpar@389: preflow_test.flowMap(flow); alpar@389: preflow_test.source(n); alpar@389: preflow_test.target(n); alpar@389: alpar@389: preflow_test.init(); alpar@389: preflow_test.flowInit(cap); alpar@389: preflow_test.startFirstPhase(); alpar@389: preflow_test.startSecondPhase(); alpar@389: preflow_test.run(); alpar@389: preflow_test.runMinCut(); alpar@389: alpar@389: preflow_test.flowValue(); alpar@389: preflow_test.minCut(n); alpar@389: preflow_test.minCutMap(cut); alpar@389: preflow_test.flow(e); alpar@389: alpar@389: } alpar@389: alpar@389: int cutValue (const SmartDigraph& g, alpar@389: const SmartDigraph::NodeMap& cut, alpar@389: const SmartDigraph::ArcMap& cap) { alpar@389: alpar@389: int c=0; alpar@389: for(SmartDigraph::ArcIt e(g); e!=INVALID; ++e) { alpar@389: if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e]; alpar@389: } alpar@389: return c; alpar@389: } alpar@389: alpar@389: bool checkFlow(const SmartDigraph& g, alpar@389: const SmartDigraph::ArcMap& flow, alpar@389: const SmartDigraph::ArcMap& cap, alpar@389: SmartDigraph::Node s, SmartDigraph::Node t) { alpar@389: alpar@389: for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) { alpar@389: if (flow[e] < 0 || flow[e] > cap[e]) return false; alpar@389: } alpar@389: alpar@389: for (SmartDigraph::NodeIt n(g); n != INVALID; ++n) { alpar@389: if (n == s || n == t) continue; alpar@389: int sum = 0; alpar@389: for (SmartDigraph::OutArcIt e(g, n); e != INVALID; ++e) { alpar@389: sum += flow[e]; alpar@389: } alpar@389: for (SmartDigraph::InArcIt e(g, n); e != INVALID; ++e) { alpar@389: sum -= flow[e]; alpar@389: } alpar@389: if (sum != 0) return false; alpar@389: } alpar@389: return true; alpar@389: } alpar@389: alpar@389: int main() { alpar@389: alpar@389: typedef SmartDigraph Digraph; alpar@389: alpar@389: typedef Digraph::Node Node; alpar@389: typedef Digraph::NodeIt NodeIt; alpar@389: typedef Digraph::ArcIt ArcIt; alpar@389: typedef Digraph::ArcMap CapMap; alpar@389: typedef Digraph::ArcMap FlowMap; alpar@389: typedef Digraph::NodeMap CutMap; alpar@389: alpar@389: typedef Preflow PType; alpar@389: alpar@389: std::string f_name; alpar@389: if( getenv("srcdir") ) alpar@389: f_name = std::string(getenv("srcdir")); alpar@389: else f_name = "."; alpar@389: f_name += "/test/preflow_graph.lgf"; alpar@389: alpar@389: std::ifstream file(f_name.c_str()); alpar@389: alpar@389: check(file, "Input file '" << f_name << "' not found."); alpar@389: alpar@389: Digraph g; alpar@389: Node s, t; alpar@389: CapMap cap(g); alpar@389: DigraphReader(g,file). alpar@389: arcMap("capacity", cap). alpar@389: node("source",s). alpar@389: node("target",t). alpar@389: run(); alpar@389: alpar@389: PType preflow_test(g, cap, s, t); alpar@389: preflow_test.run(); alpar@389: alpar@389: check(checkFlow(g, preflow_test.flowMap(), cap, s, t), alpar@389: "The flow is not feasible."); alpar@389: alpar@389: CutMap min_cut(g); alpar@389: preflow_test.minCutMap(min_cut); alpar@389: int min_cut_value=cutValue(g,min_cut,cap); alpar@389: alpar@389: check(preflow_test.flowValue() == min_cut_value, alpar@389: "The max flow value is not equal to the three min cut values."); alpar@389: alpar@389: FlowMap flow(g); alpar@389: for(ArcIt e(g); e!=INVALID; ++e) flow[e] = preflow_test.flowMap()[e]; alpar@389: alpar@389: int flow_value=preflow_test.flowValue(); alpar@389: alpar@389: for(ArcIt e(g); e!=INVALID; ++e) cap[e]=2*cap[e]; alpar@389: preflow_test.flowInit(flow); alpar@389: preflow_test.startFirstPhase(); alpar@389: alpar@389: CutMap min_cut1(g); alpar@389: preflow_test.minCutMap(min_cut1); alpar@389: min_cut_value=cutValue(g,min_cut1,cap); alpar@389: alpar@389: check(preflow_test.flowValue() == min_cut_value && alpar@389: min_cut_value == 2*flow_value, alpar@389: "The max flow value or the min cut value is wrong."); alpar@389: alpar@389: preflow_test.startSecondPhase(); alpar@389: alpar@389: check(checkFlow(g, preflow_test.flowMap(), cap, s, t), alpar@389: "The flow is not feasible."); alpar@389: alpar@389: CutMap min_cut2(g); alpar@389: preflow_test.minCutMap(min_cut2); alpar@389: min_cut_value=cutValue(g,min_cut2,cap); alpar@389: alpar@389: check(preflow_test.flowValue() == min_cut_value && alpar@389: min_cut_value == 2*flow_value, alpar@389: "The max flow value or the three min cut values were not doubled"); alpar@389: alpar@389: alpar@389: preflow_test.flowMap(flow); alpar@389: alpar@389: NodeIt tmp1(g,s); alpar@389: ++tmp1; alpar@389: if ( tmp1 != INVALID ) s=tmp1; alpar@389: alpar@389: NodeIt tmp2(g,t); alpar@389: ++tmp2; alpar@389: if ( tmp2 != INVALID ) t=tmp2; alpar@389: alpar@389: preflow_test.source(s); alpar@389: preflow_test.target(t); alpar@389: alpar@389: preflow_test.run(); alpar@389: alpar@389: CutMap min_cut3(g); alpar@389: preflow_test.minCutMap(min_cut3); alpar@389: min_cut_value=cutValue(g,min_cut3,cap); alpar@389: alpar@389: alpar@389: check(preflow_test.flowValue() == min_cut_value, alpar@389: "The max flow value or the three min cut values are incorrect."); alpar@389: alpar@389: return 0; alpar@389: }