alpar@400: /* -*- mode: C++; indent-tabs-mode: nil; -*- alpar@400: * alpar@400: * This file is a part of LEMON, a generic C++ optimization library. alpar@400: * alpar@761: * Copyright (C) 2003-2011 alpar@400: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@400: * (Egervary Research Group on Combinatorial Optimization, EGRES). alpar@400: * alpar@400: * Permission to use, modify and distribute this software is granted alpar@400: * provided that this copyright notice appears in all copies. For alpar@400: * precise terms see the accompanying LICENSE file. alpar@400: * alpar@400: * This software is provided "AS IS" with no warranty of any kind, alpar@400: * express or implied, and with no claim as to its suitability for any alpar@400: * purpose. alpar@400: * alpar@400: */ alpar@400: alpar@400: #include alpar@400: alpar@400: #include "test_tools.h" alpar@400: #include alpar@400: #include alpar@400: #include kpeter@403: #include kpeter@403: #include alpar@400: alpar@400: using namespace lemon; alpar@400: alpar@400: char test_lgf[] = alpar@400: "@nodes\n" kpeter@403: "label\n" kpeter@403: "0\n" kpeter@403: "1\n" kpeter@403: "2\n" kpeter@403: "3\n" kpeter@403: "4\n" kpeter@403: "5\n" kpeter@403: "@arcs\n" kpeter@403: " lcap ucap\n" kpeter@403: "0 1 2 10\n" kpeter@403: "0 2 2 6\n" kpeter@403: "1 3 4 7\n" kpeter@403: "1 4 0 5\n" kpeter@403: "2 4 1 3\n" kpeter@403: "3 5 3 8\n" kpeter@403: "4 5 3 7\n" alpar@400: "@attributes\n" kpeter@403: "source 0\n" kpeter@403: "sink 5\n"; kpeter@403: kpeter@403: void checkCirculationCompile() kpeter@403: { kpeter@403: typedef int VType; kpeter@403: typedef concepts::Digraph Digraph; kpeter@403: kpeter@403: typedef Digraph::Node Node; kpeter@403: typedef Digraph::Arc Arc; kpeter@403: typedef concepts::ReadMap CapMap; kpeter@602: typedef concepts::ReadMap SupplyMap; kpeter@403: typedef concepts::ReadWriteMap FlowMap; kpeter@403: typedef concepts::WriteMap BarrierMap; kpeter@403: kpeter@403: typedef Elevator Elev; kpeter@403: typedef LinkedElevator LinkedElev; kpeter@403: kpeter@403: Digraph g; kpeter@403: Node n; kpeter@403: Arc a; kpeter@403: CapMap lcap, ucap; kpeter@602: SupplyMap supply; kpeter@403: FlowMap flow; kpeter@403: BarrierMap bar; kpeter@577: VType v; kpeter@577: bool b; kpeter@403: alpar@603: typedef Circulation kpeter@577: ::SetFlowMap kpeter@577: ::SetElevator kpeter@577: ::SetStandardElevator kpeter@577: ::Create CirculationType; alpar@603: CirculationType circ_test(g, lcap, ucap, supply); kpeter@577: const CirculationType& const_circ_test = circ_test; alpar@761: kpeter@577: circ_test alpar@603: .lowerMap(lcap) alpar@603: .upperMap(ucap) alpar@603: .supplyMap(supply) kpeter@577: .flowMap(flow); kpeter@403: kpeter@403: circ_test.init(); kpeter@403: circ_test.greedyInit(); kpeter@403: circ_test.start(); kpeter@403: circ_test.run(); kpeter@403: kpeter@577: v = const_circ_test.flow(a); kpeter@577: const FlowMap& fm = const_circ_test.flowMap(); kpeter@577: b = const_circ_test.barrier(n); kpeter@577: const_circ_test.barrierMap(bar); alpar@761: kpeter@577: ignore_unused_variable_warning(fm); kpeter@403: } kpeter@403: kpeter@403: template kpeter@403: void checkCirculation(const G& g, const LM& lm, const UM& um, kpeter@403: const DM& dm, bool find) kpeter@403: { kpeter@403: Circulation circ(g, lm, um, dm); kpeter@403: bool ret = circ.run(); kpeter@403: if (find) { kpeter@403: check(ret, "A feasible solution should have been found."); kpeter@403: check(circ.checkFlow(), "The found flow is corrupt."); kpeter@403: check(!circ.checkBarrier(), "A barrier should not have been found."); kpeter@403: } else { kpeter@403: check(!ret, "A feasible solution should not have been found."); kpeter@403: check(circ.checkBarrier(), "The found barrier is corrupt."); kpeter@403: } kpeter@403: } alpar@400: alpar@400: int main (int, char*[]) alpar@400: { kpeter@403: typedef ListDigraph Digraph; kpeter@403: DIGRAPH_TYPEDEFS(Digraph); alpar@400: kpeter@403: Digraph g; kpeter@403: IntArcMap lo(g), up(g); kpeter@403: IntNodeMap delta(g, 0); kpeter@403: Node s, t; alpar@400: kpeter@403: std::istringstream input(test_lgf); kpeter@403: DigraphReader(g,input). kpeter@403: arcMap("lcap", lo). kpeter@403: arcMap("ucap", up). kpeter@403: node("source",s). kpeter@403: node("sink",t). kpeter@403: run(); alpar@400: kpeter@403: delta[s] = 7; delta[t] = -7; kpeter@403: checkCirculation(g, lo, up, delta, true); alpar@400: kpeter@403: delta[s] = 13; delta[t] = -13; kpeter@403: checkCirculation(g, lo, up, delta, true); kpeter@403: kpeter@403: delta[s] = 6; delta[t] = -6; kpeter@403: checkCirculation(g, lo, up, delta, false); kpeter@403: kpeter@403: delta[s] = 14; delta[t] = -14; kpeter@403: checkCirculation(g, lo, up, delta, false); kpeter@403: kpeter@403: delta[s] = 7; delta[t] = -13; kpeter@403: checkCirculation(g, lo, up, delta, true); kpeter@403: kpeter@403: delta[s] = 5; delta[t] = -15; kpeter@403: checkCirculation(g, lo, up, delta, true); kpeter@403: kpeter@403: delta[s] = 10; delta[t] = -11; kpeter@403: checkCirculation(g, lo, up, delta, true); kpeter@403: kpeter@403: delta[s] = 11; delta[t] = -10; kpeter@403: checkCirculation(g, lo, up, delta, false); kpeter@403: kpeter@403: return 0; alpar@400: }