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@418:   typedef concepts::ReadMap<Node,VType> DeltaMap;
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@418:   DeltaMap delta;
kpeter@418:   FlowMap flow;
kpeter@418:   BarrierMap bar;
kpeter@418: 
kpeter@418:   Circulation<Digraph, CapMap, CapMap, DeltaMap>
kpeter@418:     ::SetFlowMap<FlowMap>
kpeter@418:     ::SetElevator<Elev>
kpeter@418:     ::SetStandardElevator<LinkedElev>
kpeter@418:     ::Create circ_test(g,lcap,ucap,delta);
kpeter@418: 
kpeter@418:   circ_test.lowerCapMap(lcap);
kpeter@418:   circ_test.upperCapMap(ucap);
kpeter@418:   circ_test.deltaMap(delta);
kpeter@418:   flow = circ_test.flowMap();
kpeter@418:   circ_test.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@418:   circ_test.barrier(n);
kpeter@418:   circ_test.barrierMap(bar);
kpeter@418:   circ_test.flow(a);
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: }