1.1 --- a/test/circulation_test.cc Sun Nov 30 14:51:05 2008 +0100
1.2 +++ b/test/circulation_test.cc Mon Dec 01 14:23:59 2008 +0100
1.3 @@ -16,103 +16,141 @@
1.4 *
1.5 */
1.6
1.7 -///\ingroup demos
1.8 -///\file
1.9 -///\brief Demonstrating the usage of LEMON's General Flow algorithm
1.10 -///
1.11 -/// This demo program reads a general network circulation problem from the
1.12 -/// file 'circulation-input.lgf', runs the preflow based algorithm for
1.13 -/// finding a feasible solution and writes the output
1.14 -/// to 'circulation-input.lgf'
1.15 -///
1.16 -/// \include circulation_demo.cc
1.17 -
1.18 #include <iostream>
1.19
1.20 #include "test_tools.h"
1.21 #include <lemon/list_graph.h>
1.22 #include <lemon/circulation.h>
1.23 #include <lemon/lgf_reader.h>
1.24 +#include <lemon/concepts/digraph.h>
1.25 +#include <lemon/concepts/maps.h>
1.26
1.27 using namespace lemon;
1.28
1.29 char test_lgf[] =
1.30 "@nodes\n"
1.31 - "label delta\n"
1.32 - "0 0\n"
1.33 - "1 13\n"
1.34 - "2 0\n"
1.35 - "3 0\n"
1.36 - "4 0\n"
1.37 - "5 0\n"
1.38 - "6 0\n"
1.39 - "7 0\n"
1.40 - "8 -13\n"
1.41 - "9 0\n"
1.42 - "@edges\n"
1.43 - " label lo_cap up_cap\n"
1.44 - "0 1 0 0 20\n"
1.45 - "0 2 1 0 0\n"
1.46 - "1 1 2 0 3\n"
1.47 - "1 2 3 0 8\n"
1.48 - "1 3 4 0 8\n"
1.49 - "2 5 5 0 5\n"
1.50 - "3 2 6 0 5\n"
1.51 - "3 5 7 0 5\n"
1.52 - "3 6 8 0 5\n"
1.53 - "4 3 9 0 3\n"
1.54 - "5 7 10 0 3\n"
1.55 - "5 6 11 0 10\n"
1.56 - "5 8 12 0 10\n"
1.57 - "6 8 13 0 8\n"
1.58 - "8 9 14 0 20\n"
1.59 - "8 1 15 0 5\n"
1.60 - "9 5 16 0 5\n"
1.61 + "label\n"
1.62 + "0\n"
1.63 + "1\n"
1.64 + "2\n"
1.65 + "3\n"
1.66 + "4\n"
1.67 + "5\n"
1.68 + "@arcs\n"
1.69 + " lcap ucap\n"
1.70 + "0 1 2 10\n"
1.71 + "0 2 2 6\n"
1.72 + "1 3 4 7\n"
1.73 + "1 4 0 5\n"
1.74 + "2 4 1 3\n"
1.75 + "3 5 3 8\n"
1.76 + "4 5 3 7\n"
1.77 "@attributes\n"
1.78 - "source 1\n"
1.79 - "sink 8\n";
1.80 + "source 0\n"
1.81 + "sink 5\n";
1.82 +
1.83 +void checkCirculationCompile()
1.84 +{
1.85 + typedef int VType;
1.86 + typedef concepts::Digraph Digraph;
1.87 +
1.88 + typedef Digraph::Node Node;
1.89 + typedef Digraph::Arc Arc;
1.90 + typedef concepts::ReadMap<Arc,VType> CapMap;
1.91 + typedef concepts::ReadMap<Node,VType> DeltaMap;
1.92 + typedef concepts::ReadWriteMap<Arc,VType> FlowMap;
1.93 + typedef concepts::WriteMap<Node,bool> BarrierMap;
1.94 +
1.95 + typedef Elevator<Digraph, Digraph::Node> Elev;
1.96 + typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev;
1.97 +
1.98 + Digraph g;
1.99 + Node n;
1.100 + Arc a;
1.101 + CapMap lcap, ucap;
1.102 + DeltaMap delta;
1.103 + FlowMap flow;
1.104 + BarrierMap bar;
1.105 +
1.106 + Circulation<Digraph, CapMap, CapMap, DeltaMap>
1.107 + ::SetFlowMap<FlowMap>
1.108 + ::SetElevator<Elev>
1.109 + ::SetStandardElevator<LinkedElev>
1.110 + ::Create circ_test(g,lcap,ucap,delta);
1.111 +
1.112 + circ_test.lowerCapMap(lcap);
1.113 + circ_test.upperCapMap(ucap);
1.114 + circ_test.deltaMap(delta);
1.115 + flow = circ_test.flowMap();
1.116 + circ_test.flowMap(flow);
1.117 +
1.118 + circ_test.init();
1.119 + circ_test.greedyInit();
1.120 + circ_test.start();
1.121 + circ_test.run();
1.122 +
1.123 + circ_test.barrier(n);
1.124 + circ_test.barrierMap(bar);
1.125 + circ_test.flow(a);
1.126 +}
1.127 +
1.128 +template <class G, class LM, class UM, class DM>
1.129 +void checkCirculation(const G& g, const LM& lm, const UM& um,
1.130 + const DM& dm, bool find)
1.131 +{
1.132 + Circulation<G, LM, UM, DM> circ(g, lm, um, dm);
1.133 + bool ret = circ.run();
1.134 + if (find) {
1.135 + check(ret, "A feasible solution should have been found.");
1.136 + check(circ.checkFlow(), "The found flow is corrupt.");
1.137 + check(!circ.checkBarrier(), "A barrier should not have been found.");
1.138 + } else {
1.139 + check(!ret, "A feasible solution should not have been found.");
1.140 + check(circ.checkBarrier(), "The found barrier is corrupt.");
1.141 + }
1.142 +}
1.143
1.144 int main (int, char*[])
1.145 {
1.146 + typedef ListDigraph Digraph;
1.147 + DIGRAPH_TYPEDEFS(Digraph);
1.148
1.149 - typedef ListDigraph Digraph;
1.150 - typedef Digraph::Node Node;
1.151 - typedef Digraph::NodeIt NodeIt;
1.152 - typedef Digraph::Arc Arc;
1.153 - typedef Digraph::ArcIt ArcIt;
1.154 - typedef Digraph::ArcMap<int> ArcMap;
1.155 - typedef Digraph::NodeMap<int> NodeMap;
1.156 - typedef Digraph::NodeMap<double> DNodeMap;
1.157 + Digraph g;
1.158 + IntArcMap lo(g), up(g);
1.159 + IntNodeMap delta(g, 0);
1.160 + Node s, t;
1.161
1.162 - Digraph g;
1.163 - ArcMap lo(g);
1.164 - ArcMap up(g);
1.165 - NodeMap delta(g);
1.166 - NodeMap nid(g);
1.167 - ArcMap eid(g);
1.168 - Node source, sink;
1.169 -
1.170 - std::istringstream input(test_lgf);
1.171 - DigraphReader<Digraph>(g,input).
1.172 - arcMap("lo_cap", lo).
1.173 - arcMap("up_cap", up).
1.174 - nodeMap("delta", delta).
1.175 - arcMap("label", eid).
1.176 - nodeMap("label", nid).
1.177 - node("source",source).
1.178 - node("sink",sink).
1.179 - run();
1.180 + std::istringstream input(test_lgf);
1.181 + DigraphReader<Digraph>(g,input).
1.182 + arcMap("lcap", lo).
1.183 + arcMap("ucap", up).
1.184 + node("source",s).
1.185 + node("sink",t).
1.186 + run();
1.187
1.188 - Circulation<Digraph> gen(g,lo,up,delta);
1.189 - bool ret=gen.run();
1.190 - check(ret,"A feasible solution should have been found.");
1.191 - check(gen.checkFlow(), "The found flow is corrupt.");
1.192 -
1.193 - delta[source]=14;
1.194 - delta[sink]=-14;
1.195 -
1.196 - bool ret2=gen.run();
1.197 - check(!ret2,"A feasible solution should not have been found.");
1.198 - check(gen.checkBarrier(), "The found barrier is corrupt.");
1.199 + delta[s] = 7; delta[t] = -7;
1.200 + checkCirculation(g, lo, up, delta, true);
1.201
1.202 + delta[s] = 13; delta[t] = -13;
1.203 + checkCirculation(g, lo, up, delta, true);
1.204 +
1.205 + delta[s] = 6; delta[t] = -6;
1.206 + checkCirculation(g, lo, up, delta, false);
1.207 +
1.208 + delta[s] = 14; delta[t] = -14;
1.209 + checkCirculation(g, lo, up, delta, false);
1.210 +
1.211 + delta[s] = 7; delta[t] = -13;
1.212 + checkCirculation(g, lo, up, delta, true);
1.213 +
1.214 + delta[s] = 5; delta[t] = -15;
1.215 + checkCirculation(g, lo, up, delta, true);
1.216 +
1.217 + delta[s] = 10; delta[t] = -11;
1.218 + checkCirculation(g, lo, up, delta, true);
1.219 +
1.220 + delta[s] = 11; delta[t] = -10;
1.221 + checkCirculation(g, lo, up, delta, false);
1.222 +
1.223 + return 0;
1.224 }