test/circulation_test.cc
changeset 400 fa341dd6ab23
child 403 940587667b47
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/test/circulation_test.cc	Mon Dec 01 14:11:31 2008 +0000
     1.3 @@ -0,0 +1,118 @@
     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 +///\ingroup demos
    1.23 +///\file
    1.24 +///\brief Demonstrating the usage of LEMON's General Flow algorithm
    1.25 +///
    1.26 +/// This demo program reads a general network circulation problem from the
    1.27 +/// file 'circulation-input.lgf', runs the preflow based algorithm for
    1.28 +/// finding a feasible solution and writes the output
    1.29 +/// to 'circulation-input.lgf'
    1.30 +///
    1.31 +/// \include circulation_demo.cc
    1.32 +
    1.33 +#include <iostream>
    1.34 +
    1.35 +#include "test_tools.h"
    1.36 +#include <lemon/list_graph.h>
    1.37 +#include <lemon/circulation.h>
    1.38 +#include <lemon/lgf_reader.h>
    1.39 +
    1.40 +using namespace lemon;
    1.41 +
    1.42 +char test_lgf[] =
    1.43 +  "@nodes\n"
    1.44 +  "label delta\n"
    1.45 +  "0     0\n"
    1.46 +  "1     13\n"
    1.47 +  "2     0\n"
    1.48 +  "3     0\n"
    1.49 +  "4     0\n"
    1.50 +  "5     0\n"
    1.51 +  "6     0\n"
    1.52 +  "7     0\n"
    1.53 +  "8     -13\n"
    1.54 +  "9     0\n"
    1.55 +  "@edges\n"
    1.56 +  "    label lo_cap up_cap\n"
    1.57 +  "0 1 0     0      20\n"
    1.58 +  "0 2 1     0      0\n"
    1.59 +  "1 1 2     0      3\n"
    1.60 +  "1 2 3     0      8\n"
    1.61 +  "1 3 4     0      8\n"
    1.62 +  "2 5 5     0      5\n"
    1.63 +  "3 2 6     0      5\n"
    1.64 +  "3 5 7     0      5\n"
    1.65 +  "3 6 8     0      5\n"
    1.66 +  "4 3 9     0      3\n"
    1.67 +  "5 7 10    0      3\n"
    1.68 +  "5 6 11    0      10\n"
    1.69 +  "5 8 12    0      10\n"
    1.70 +  "6 8 13    0      8\n"
    1.71 +  "8 9 14    0      20\n"
    1.72 +  "8 1 15    0      5\n"
    1.73 +  "9 5 16    0      5\n"
    1.74 +  "@attributes\n"
    1.75 +  "source 1\n"
    1.76 +  "sink   8\n";
    1.77 +
    1.78 +int main (int, char*[])
    1.79 +{
    1.80 +
    1.81 +    typedef ListDigraph Digraph;
    1.82 +    typedef Digraph::Node Node;
    1.83 +    typedef Digraph::NodeIt NodeIt;
    1.84 +    typedef Digraph::Arc Arc;
    1.85 +    typedef Digraph::ArcIt ArcIt;
    1.86 +    typedef Digraph::ArcMap<int> ArcMap;
    1.87 +    typedef Digraph::NodeMap<int> NodeMap;
    1.88 +    typedef Digraph::NodeMap<double> DNodeMap;
    1.89 +
    1.90 +    Digraph g;
    1.91 +    ArcMap lo(g);
    1.92 +    ArcMap up(g);
    1.93 +    NodeMap delta(g);
    1.94 +    NodeMap nid(g);
    1.95 +    ArcMap eid(g);
    1.96 +    Node source, sink;
    1.97 +    
    1.98 +    std::istringstream input(test_lgf);
    1.99 +    DigraphReader<Digraph>(g,input).
   1.100 +      arcMap("lo_cap", lo).
   1.101 +      arcMap("up_cap", up).
   1.102 +      nodeMap("delta", delta).
   1.103 +      arcMap("label", eid).
   1.104 +      nodeMap("label", nid).
   1.105 +      node("source",source).
   1.106 +      node("sink",sink).
   1.107 +      run();
   1.108 +
   1.109 +    Circulation<Digraph> gen(g,lo,up,delta);
   1.110 +    bool ret=gen.run();
   1.111 +    check(ret,"A feasible solution should have been found.");
   1.112 +    check(gen.checkFlow(), "The found flow is corrupt.");
   1.113 +    
   1.114 +    delta[source]=14;
   1.115 +    delta[sink]=-14;
   1.116 +    
   1.117 +    bool ret2=gen.run();
   1.118 +    check(!ret2,"A feasible solution should not have been found.");
   1.119 +    check(gen.checkBarrier(), "The found barrier is corrupt.");
   1.120 +
   1.121 +}