/* -*- 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 <iostream>

 #include "test_tools.h"

 #include <lemon/list_graph.h>

 #include <lemon/circulation.h>

 #include <lemon/lgf_reader.h>

 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<int> ArcMap;

     typedef Digraph::NodeMap<int> NodeMap;

     typedef Digraph::NodeMap<double> 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<Digraph>(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<Digraph> 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.");

 }