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@440:  * Copyright (C) 2003-2009
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 <iostream>
alpar@400: 
alpar@400: #include "test_tools.h"
alpar@400: #include <lemon/list_graph.h>
alpar@400: #include <lemon/circulation.h>
alpar@400: #include <lemon/lgf_reader.h>
kpeter@403: #include <lemon/concepts/digraph.h>
kpeter@403: #include <lemon/concepts/maps.h>
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<Arc,VType> CapMap;
kpeter@403:   typedef concepts::ReadMap<Node,VType> DeltaMap;
kpeter@403:   typedef concepts::ReadWriteMap<Arc,VType> FlowMap;
kpeter@403:   typedef concepts::WriteMap<Node,bool> BarrierMap;
kpeter@403: 
kpeter@403:   typedef Elevator<Digraph, Digraph::Node> Elev;
kpeter@403:   typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev;
kpeter@403: 
kpeter@403:   Digraph g;
kpeter@403:   Node n;
kpeter@403:   Arc a;
kpeter@403:   CapMap lcap, ucap;
kpeter@403:   DeltaMap delta;
kpeter@403:   FlowMap flow;
kpeter@403:   BarrierMap bar;
kpeter@403: 
kpeter@403:   Circulation<Digraph, CapMap, CapMap, DeltaMap>
kpeter@403:     ::SetFlowMap<FlowMap>
kpeter@403:     ::SetElevator<Elev>
kpeter@403:     ::SetStandardElevator<LinkedElev>
kpeter@403:     ::Create circ_test(g,lcap,ucap,delta);
kpeter@403: 
kpeter@403:   circ_test.lowerCapMap(lcap);
kpeter@403:   circ_test.upperCapMap(ucap);
kpeter@403:   circ_test.deltaMap(delta);
kpeter@403:   flow = circ_test.flowMap();
kpeter@403:   circ_test.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@403:   circ_test.barrier(n);
kpeter@403:   circ_test.barrierMap(bar);
kpeter@403:   circ_test.flow(a);
kpeter@403: }
kpeter@403: 
kpeter@403: template <class G, class LM, class UM, class DM>
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<G, LM, UM, DM> 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<Digraph>(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: }