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