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 <iostream>
alpar@415:
alpar@415: #include "test_tools.h"
alpar@415: #include <lemon/list_graph.h>
alpar@415: #include <lemon/circulation.h>
alpar@415: #include <lemon/lgf_reader.h>
kpeter@418: #include <lemon/concepts/digraph.h>
kpeter@418: #include <lemon/concepts/maps.h>
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<Arc,VType> CapMap;
kpeter@657: typedef concepts::ReadMap<Node,VType> SupplyMap;
kpeter@418: typedef concepts::ReadWriteMap<Arc,VType> FlowMap;
kpeter@418: typedef concepts::WriteMap<Node,bool> BarrierMap;
kpeter@418:
kpeter@418: typedef Elevator<Digraph, Digraph::Node> Elev;
kpeter@418: typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev;
kpeter@418:
kpeter@418: Digraph g;
kpeter@418: Node n;
kpeter@418: Arc a;
kpeter@418: CapMap lcap, ucap;
kpeter@657: SupplyMap supply;
kpeter@418: FlowMap flow;
kpeter@418: BarrierMap bar;
kpeter@632: VType v;
kpeter@632: bool b;
kpeter@418:
alpar@658: typedef Circulation<Digraph, CapMap, CapMap, SupplyMap>
kpeter@632: ::SetFlowMap<FlowMap>
kpeter@632: ::SetElevator<Elev>
kpeter@632: ::SetStandardElevator<LinkedElev>
kpeter@632: ::Create CirculationType;
alpar@658: CirculationType circ_test(g, lcap, ucap, supply);
kpeter@632: const CirculationType& const_circ_test = circ_test;
kpeter@632:
kpeter@632: circ_test
alpar@658: .lowerMap(lcap)
alpar@658: .upperMap(ucap)
alpar@658: .supplyMap(supply)
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 <class G, class LM, class UM, class DM>
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<G, LM, UM, DM> 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<Digraph>(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: }