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