diff --git a/test/circulation_test.cc b/test/circulation_test.cc new file mode 100644 --- /dev/null +++ b/test/circulation_test.cc @@ -0,0 +1,118 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2008 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +///\ingroup demos +///\file +///\brief Demonstrating the usage of LEMON's General Flow algorithm +/// +/// This demo program reads a general network circulation problem from the +/// file 'circulation-input.lgf', runs the preflow based algorithm for +/// finding a feasible solution and writes the output +/// to 'circulation-input.lgf' +/// +/// \include circulation_demo.cc + +#include + +#include "test_tools.h" +#include +#include +#include + +using namespace lemon; + +char test_lgf[] = + "@nodes\n" + "label delta\n" + "0 0\n" + "1 13\n" + "2 0\n" + "3 0\n" + "4 0\n" + "5 0\n" + "6 0\n" + "7 0\n" + "8 -13\n" + "9 0\n" + "@edges\n" + " label lo_cap up_cap\n" + "0 1 0 0 20\n" + "0 2 1 0 0\n" + "1 1 2 0 3\n" + "1 2 3 0 8\n" + "1 3 4 0 8\n" + "2 5 5 0 5\n" + "3 2 6 0 5\n" + "3 5 7 0 5\n" + "3 6 8 0 5\n" + "4 3 9 0 3\n" + "5 7 10 0 3\n" + "5 6 11 0 10\n" + "5 8 12 0 10\n" + "6 8 13 0 8\n" + "8 9 14 0 20\n" + "8 1 15 0 5\n" + "9 5 16 0 5\n" + "@attributes\n" + "source 1\n" + "sink 8\n"; + +int main (int, char*[]) +{ + + typedef ListDigraph Digraph; + typedef Digraph::Node Node; + typedef Digraph::NodeIt NodeIt; + typedef Digraph::Arc Arc; + typedef Digraph::ArcIt ArcIt; + typedef Digraph::ArcMap ArcMap; + typedef Digraph::NodeMap NodeMap; + typedef Digraph::NodeMap DNodeMap; + + Digraph g; + ArcMap lo(g); + ArcMap up(g); + NodeMap delta(g); + NodeMap nid(g); + ArcMap eid(g); + Node source, sink; + + std::istringstream input(test_lgf); + DigraphReader(g,input). + arcMap("lo_cap", lo). + arcMap("up_cap", up). + nodeMap("delta", delta). + arcMap("label", eid). + nodeMap("label", nid). + node("source",source). + node("sink",sink). + run(); + + Circulation gen(g,lo,up,delta); + bool ret=gen.run(); + check(ret,"A feasible solution should have been found."); + check(gen.checkFlow(), "The found flow is corrupt."); + + delta[source]=14; + delta[sink]=-14; + + bool ret2=gen.run(); + check(!ret2,"A feasible solution should not have been found."); + check(gen.checkBarrier(), "The found barrier is corrupt."); + +}