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@400: * Copyright (C) 2003-2008 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: ///\ingroup demos alpar@400: ///\file alpar@400: ///\brief Demonstrating the usage of LEMON's General Flow algorithm alpar@400: /// alpar@400: /// This demo program reads a general network circulation problem from the alpar@400: /// file 'circulation-input.lgf', runs the preflow based algorithm for alpar@400: /// finding a feasible solution and writes the output alpar@400: /// to 'circulation-input.lgf' alpar@400: /// alpar@400: /// \include circulation_demo.cc alpar@400: alpar@400: #include alpar@400: alpar@400: #include "test_tools.h" alpar@400: #include alpar@400: #include alpar@400: #include alpar@400: alpar@400: using namespace lemon; alpar@400: alpar@400: char test_lgf[] = alpar@400: "@nodes\n" alpar@400: "label delta\n" alpar@400: "0 0\n" alpar@400: "1 13\n" alpar@400: "2 0\n" alpar@400: "3 0\n" alpar@400: "4 0\n" alpar@400: "5 0\n" alpar@400: "6 0\n" alpar@400: "7 0\n" alpar@400: "8 -13\n" alpar@400: "9 0\n" alpar@400: "@edges\n" alpar@400: " label lo_cap up_cap\n" alpar@400: "0 1 0 0 20\n" alpar@400: "0 2 1 0 0\n" alpar@400: "1 1 2 0 3\n" alpar@400: "1 2 3 0 8\n" alpar@400: "1 3 4 0 8\n" alpar@400: "2 5 5 0 5\n" alpar@400: "3 2 6 0 5\n" alpar@400: "3 5 7 0 5\n" alpar@400: "3 6 8 0 5\n" alpar@400: "4 3 9 0 3\n" alpar@400: "5 7 10 0 3\n" alpar@400: "5 6 11 0 10\n" alpar@400: "5 8 12 0 10\n" alpar@400: "6 8 13 0 8\n" alpar@400: "8 9 14 0 20\n" alpar@400: "8 1 15 0 5\n" alpar@400: "9 5 16 0 5\n" alpar@400: "@attributes\n" alpar@400: "source 1\n" alpar@400: "sink 8\n"; alpar@400: alpar@400: int main (int, char*[]) alpar@400: { alpar@400: alpar@400: typedef ListDigraph Digraph; alpar@400: typedef Digraph::Node Node; alpar@400: typedef Digraph::NodeIt NodeIt; alpar@400: typedef Digraph::Arc Arc; alpar@400: typedef Digraph::ArcIt ArcIt; alpar@400: typedef Digraph::ArcMap ArcMap; alpar@400: typedef Digraph::NodeMap NodeMap; alpar@400: typedef Digraph::NodeMap DNodeMap; alpar@400: alpar@400: Digraph g; alpar@400: ArcMap lo(g); alpar@400: ArcMap up(g); alpar@400: NodeMap delta(g); alpar@400: NodeMap nid(g); alpar@400: ArcMap eid(g); alpar@400: Node source, sink; alpar@400: alpar@400: std::istringstream input(test_lgf); alpar@400: DigraphReader(g,input). alpar@400: arcMap("lo_cap", lo). alpar@400: arcMap("up_cap", up). alpar@400: nodeMap("delta", delta). alpar@400: arcMap("label", eid). alpar@400: nodeMap("label", nid). alpar@400: node("source",source). alpar@400: node("sink",sink). alpar@400: run(); alpar@400: alpar@400: Circulation gen(g,lo,up,delta); alpar@400: bool ret=gen.run(); alpar@400: check(ret,"A feasible solution should have been found."); alpar@400: check(gen.checkFlow(), "The found flow is corrupt."); alpar@400: alpar@400: delta[source]=14; alpar@400: delta[sink]=-14; alpar@400: alpar@400: bool ret2=gen.run(); alpar@400: check(!ret2,"A feasible solution should not have been found."); alpar@400: check(gen.checkBarrier(), "The found barrier is corrupt."); alpar@400: alpar@400: }