diff -r cd72eae05bdf -r 3c00344f49c9 test/preflow_test.cc --- a/test/preflow_test.cc Mon Jul 16 16:21:40 2018 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,276 +0,0 @@ -/* -*- mode: C++; indent-tabs-mode: nil; -*- - * - * This file is a part of LEMON, a generic C++ optimization library. - * - * Copyright (C) 2003-2010 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Research Group on Combinatorial Optimization, EGRES). - * - * Permission to use, modify and distribute this software is granted - * provided that this copyright notice appears in all copies. For - * precise terms see the accompanying LICENSE file. - * - * This software is provided "AS IS" with no warranty of any kind, - * express or implied, and with no claim as to its suitability for any - * purpose. - * - */ - -#include - -#include "test_tools.h" -#include -#include -#include -#include -#include -#include - -using namespace lemon; - -char test_lgf[] = - "@nodes\n" - "label\n" - "0\n" - "1\n" - "2\n" - "3\n" - "4\n" - "5\n" - "6\n" - "7\n" - "8\n" - "9\n" - "@arcs\n" - " label capacity\n" - "0 1 0 20\n" - "0 2 1 0\n" - "1 1 2 3\n" - "1 2 3 8\n" - "1 3 4 8\n" - "2 5 5 5\n" - "3 2 6 5\n" - "3 5 7 5\n" - "3 6 8 5\n" - "4 3 9 3\n" - "5 7 10 3\n" - "5 6 11 10\n" - "5 8 12 10\n" - "6 8 13 8\n" - "8 9 14 20\n" - "8 1 15 5\n" - "9 5 16 5\n" - "@attributes\n" - "source 1\n" - "target 8\n"; - -void checkPreflowCompile() -{ - typedef int VType; - typedef concepts::Digraph Digraph; - - typedef Digraph::Node Node; - typedef Digraph::Arc Arc; - typedef concepts::ReadMap CapMap; - typedef concepts::ReadWriteMap FlowMap; - typedef concepts::WriteMap CutMap; - - typedef Elevator Elev; - typedef LinkedElevator LinkedElev; - - Digraph g; - Node n; - Arc e; - CapMap cap; - FlowMap flow; - CutMap cut; - VType v; - bool b; - - typedef Preflow - ::SetFlowMap - ::SetElevator - ::SetStandardElevator - ::Create PreflowType; - PreflowType preflow_test(g, cap, n, n); - const PreflowType& const_preflow_test = preflow_test; - - const PreflowType::Elevator& elev = const_preflow_test.elevator(); - preflow_test.elevator(const_cast(elev)); - PreflowType::Tolerance tol = const_preflow_test.tolerance(); - preflow_test.tolerance(tol); - - preflow_test - .capacityMap(cap) - .flowMap(flow) - .source(n) - .target(n); - - preflow_test.init(); - preflow_test.init(cap); - preflow_test.startFirstPhase(); - preflow_test.startSecondPhase(); - preflow_test.run(); - preflow_test.runMinCut(); - - v = const_preflow_test.flowValue(); - v = const_preflow_test.flow(e); - const FlowMap& fm = const_preflow_test.flowMap(); - b = const_preflow_test.minCut(n); - const_preflow_test.minCutMap(cut); - - ignore_unused_variable_warning(fm); -} - -int cutValue (const SmartDigraph& g, - const SmartDigraph::NodeMap& cut, - const SmartDigraph::ArcMap& cap) { - - int c=0; - for(SmartDigraph::ArcIt e(g); e!=INVALID; ++e) { - if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e]; - } - return c; -} - -bool checkFlow(const SmartDigraph& g, - const SmartDigraph::ArcMap& flow, - const SmartDigraph::ArcMap& cap, - SmartDigraph::Node s, SmartDigraph::Node t) { - - for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) { - if (flow[e] < 0 || flow[e] > cap[e]) return false; - } - - for (SmartDigraph::NodeIt n(g); n != INVALID; ++n) { - if (n == s || n == t) continue; - int sum = 0; - for (SmartDigraph::OutArcIt e(g, n); e != INVALID; ++e) { - sum += flow[e]; - } - for (SmartDigraph::InArcIt e(g, n); e != INVALID; ++e) { - sum -= flow[e]; - } - if (sum != 0) return false; - } - return true; -} - -void initFlowTest() -{ - DIGRAPH_TYPEDEFS(SmartDigraph); - - SmartDigraph g; - SmartDigraph::ArcMap cap(g),iflow(g); - Node s=g.addNode(); Node t=g.addNode(); - Node n1=g.addNode(); Node n2=g.addNode(); - Arc a; - a=g.addArc(s,n1); cap[a]=20; iflow[a]=20; - a=g.addArc(n1,n2); cap[a]=10; iflow[a]=0; - a=g.addArc(n2,t); cap[a]=20; iflow[a]=0; - - Preflow pre(g,cap,s,t); - pre.init(iflow); - pre.startFirstPhase(); - check(pre.flowValue() == 10, "The incorrect max flow value."); - check(pre.minCut(s), "Wrong min cut (Node s)."); - check(pre.minCut(n1), "Wrong min cut (Node n1)."); - check(!pre.minCut(n2), "Wrong min cut (Node n2)."); - check(!pre.minCut(t), "Wrong min cut (Node t)."); -} - - -int main() { - - typedef SmartDigraph Digraph; - - typedef Digraph::Node Node; - typedef Digraph::NodeIt NodeIt; - typedef Digraph::ArcIt ArcIt; - typedef Digraph::ArcMap CapMap; - typedef Digraph::ArcMap FlowMap; - typedef Digraph::NodeMap CutMap; - - typedef Preflow PType; - - Digraph g; - Node s, t; - CapMap cap(g); - std::istringstream input(test_lgf); - DigraphReader(g,input). - arcMap("capacity", cap). - node("source",s). - node("target",t). - run(); - - PType preflow_test(g, cap, s, t); - preflow_test.run(); - - check(checkFlow(g, preflow_test.flowMap(), cap, s, t), - "The flow is not feasible."); - - CutMap min_cut(g); - preflow_test.minCutMap(min_cut); - int min_cut_value=cutValue(g,min_cut,cap); - - check(preflow_test.flowValue() == min_cut_value, - "The max flow value is not equal to the three min cut values."); - - FlowMap flow(g); - for(ArcIt e(g); e!=INVALID; ++e) flow[e] = preflow_test.flowMap()[e]; - - int flow_value=preflow_test.flowValue(); - - for(ArcIt e(g); e!=INVALID; ++e) cap[e]=2*cap[e]; - preflow_test.init(flow); - preflow_test.startFirstPhase(); - - CutMap min_cut1(g); - preflow_test.minCutMap(min_cut1); - min_cut_value=cutValue(g,min_cut1,cap); - - check(preflow_test.flowValue() == min_cut_value && - min_cut_value == 2*flow_value, - "The max flow value or the min cut value is wrong."); - - preflow_test.startSecondPhase(); - - check(checkFlow(g, preflow_test.flowMap(), cap, s, t), - "The flow is not feasible."); - - CutMap min_cut2(g); - preflow_test.minCutMap(min_cut2); - min_cut_value=cutValue(g,min_cut2,cap); - - check(preflow_test.flowValue() == min_cut_value && - min_cut_value == 2*flow_value, - "The max flow value or the three min cut values were not doubled"); - - - preflow_test.flowMap(flow); - - NodeIt tmp1(g,s); - ++tmp1; - if ( tmp1 != INVALID ) s=tmp1; - - NodeIt tmp2(g,t); - ++tmp2; - if ( tmp2 != INVALID ) t=tmp2; - - preflow_test.source(s); - preflow_test.target(t); - - preflow_test.run(); - - CutMap min_cut3(g); - preflow_test.minCutMap(min_cut3); - min_cut_value=cutValue(g,min_cut3,cap); - - - check(preflow_test.flowValue() == min_cut_value, - "The max flow value or the three min cut values are incorrect."); - - initFlowTest(); - - return 0; -}