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 +}