1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/test/circulation_test.cc Mon Dec 01 14:18:40 2008 +0000
1.3 @@ -0,0 +1,156 @@
1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library.
1.7 + *
1.8 + * Copyright (C) 2003-2008
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +#include <iostream>
1.23 +
1.24 +#include "test_tools.h"
1.25 +#include <lemon/list_graph.h>
1.26 +#include <lemon/circulation.h>
1.27 +#include <lemon/lgf_reader.h>
1.28 +#include <lemon/concepts/digraph.h>
1.29 +#include <lemon/concepts/maps.h>
1.30 +
1.31 +using namespace lemon;
1.32 +
1.33 +char test_lgf[] =
1.34 + "@nodes\n"
1.35 + "label\n"
1.36 + "0\n"
1.37 + "1\n"
1.38 + "2\n"
1.39 + "3\n"
1.40 + "4\n"
1.41 + "5\n"
1.42 + "@arcs\n"
1.43 + " lcap ucap\n"
1.44 + "0 1 2 10\n"
1.45 + "0 2 2 6\n"
1.46 + "1 3 4 7\n"
1.47 + "1 4 0 5\n"
1.48 + "2 4 1 3\n"
1.49 + "3 5 3 8\n"
1.50 + "4 5 3 7\n"
1.51 + "@attributes\n"
1.52 + "source 0\n"
1.53 + "sink 5\n";
1.54 +
1.55 +void checkCirculationCompile()
1.56 +{
1.57 + typedef int VType;
1.58 + typedef concepts::Digraph Digraph;
1.59 +
1.60 + typedef Digraph::Node Node;
1.61 + typedef Digraph::Arc Arc;
1.62 + typedef concepts::ReadMap<Arc,VType> CapMap;
1.63 + typedef concepts::ReadMap<Node,VType> DeltaMap;
1.64 + typedef concepts::ReadWriteMap<Arc,VType> FlowMap;
1.65 + typedef concepts::WriteMap<Node,bool> BarrierMap;
1.66 +
1.67 + typedef Elevator<Digraph, Digraph::Node> Elev;
1.68 + typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev;
1.69 +
1.70 + Digraph g;
1.71 + Node n;
1.72 + Arc a;
1.73 + CapMap lcap, ucap;
1.74 + DeltaMap delta;
1.75 + FlowMap flow;
1.76 + BarrierMap bar;
1.77 +
1.78 + Circulation<Digraph, CapMap, CapMap, DeltaMap>
1.79 + ::SetFlowMap<FlowMap>
1.80 + ::SetElevator<Elev>
1.81 + ::SetStandardElevator<LinkedElev>
1.82 + ::Create circ_test(g,lcap,ucap,delta);
1.83 +
1.84 + circ_test.lowerCapMap(lcap);
1.85 + circ_test.upperCapMap(ucap);
1.86 + circ_test.deltaMap(delta);
1.87 + flow = circ_test.flowMap();
1.88 + circ_test.flowMap(flow);
1.89 +
1.90 + circ_test.init();
1.91 + circ_test.greedyInit();
1.92 + circ_test.start();
1.93 + circ_test.run();
1.94 +
1.95 + circ_test.barrier(n);
1.96 + circ_test.barrierMap(bar);
1.97 + circ_test.flow(a);
1.98 +}
1.99 +
1.100 +template <class G, class LM, class UM, class DM>
1.101 +void checkCirculation(const G& g, const LM& lm, const UM& um,
1.102 + const DM& dm, bool find)
1.103 +{
1.104 + Circulation<G, LM, UM, DM> circ(g, lm, um, dm);
1.105 + bool ret = circ.run();
1.106 + if (find) {
1.107 + check(ret, "A feasible solution should have been found.");
1.108 + check(circ.checkFlow(), "The found flow is corrupt.");
1.109 + check(!circ.checkBarrier(), "A barrier should not have been found.");
1.110 + } else {
1.111 + check(!ret, "A feasible solution should not have been found.");
1.112 + check(circ.checkBarrier(), "The found barrier is corrupt.");
1.113 + }
1.114 +}
1.115 +
1.116 +int main (int, char*[])
1.117 +{
1.118 + typedef ListDigraph Digraph;
1.119 + DIGRAPH_TYPEDEFS(Digraph);
1.120 +
1.121 + Digraph g;
1.122 + IntArcMap lo(g), up(g);
1.123 + IntNodeMap delta(g, 0);
1.124 + Node s, t;
1.125 +
1.126 + std::istringstream input(test_lgf);
1.127 + DigraphReader<Digraph>(g,input).
1.128 + arcMap("lcap", lo).
1.129 + arcMap("ucap", up).
1.130 + node("source",s).
1.131 + node("sink",t).
1.132 + run();
1.133 +
1.134 + delta[s] = 7; delta[t] = -7;
1.135 + checkCirculation(g, lo, up, delta, true);
1.136 +
1.137 + delta[s] = 13; delta[t] = -13;
1.138 + checkCirculation(g, lo, up, delta, true);
1.139 +
1.140 + delta[s] = 6; delta[t] = -6;
1.141 + checkCirculation(g, lo, up, delta, false);
1.142 +
1.143 + delta[s] = 14; delta[t] = -14;
1.144 + checkCirculation(g, lo, up, delta, false);
1.145 +
1.146 + delta[s] = 7; delta[t] = -13;
1.147 + checkCirculation(g, lo, up, delta, true);
1.148 +
1.149 + delta[s] = 5; delta[t] = -15;
1.150 + checkCirculation(g, lo, up, delta, true);
1.151 +
1.152 + delta[s] = 10; delta[t] = -11;
1.153 + checkCirculation(g, lo, up, delta, true);
1.154 +
1.155 + delta[s] = 11; delta[t] = -10;
1.156 + checkCirculation(g, lo, up, delta, false);
1.157 +
1.158 + return 0;
1.159 +}