/* -*- mode: C++; indent-tabs-mode: nil; -*-

  *

  * This file is a part of LEMON, a generic C++ optimization library.

  *

  * Copyright (C) 2003-2010

  * 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.

  *

  */

 ///\file

 ///\brief Demo program that solves maximum flow problems using the LP interface

 ///

 /// This demo program shows how to solve the maximum flow problem using

 /// the LEMON LP solver interface. We would like to lay the emphasis on the

 /// simplicity of the way one can formulate LP constraints that arise in graph

 /// theory using LEMON.

 ///

 /// \include lp_maxflow_demo.cc

 #include <iostream>

 #include <lemon/smart_graph.h>

 #include <lemon/lgf_reader.h>

 #include <lemon/lp.h>

 using namespace lemon;

 template <typename GR, typename CAP>

 double maxFlow(const GR &g, const CAP &capacity,

                typename GR::Node source, typename GR::Node target)

 {

   TEMPLATE_DIGRAPH_TYPEDEFS(GR);

   // Create an instance of the default LP solver

   Lp lp;

   // Add a column to the problem for each arc

   typename GR::template ArcMap<Lp::Col> f(g);

   lp.addColSet(f);

   // Capacity constraints

   for (ArcIt a(g); a != INVALID; ++a) {

     lp.colLowerBound(f[a], 0);

     lp.colUpperBound(f[a], capacity[a]);

   }

   // Flow conservation constraints

   for (NodeIt n(g); n != INVALID; ++n) {

     if (n == source || n == target) continue;

     Lp::Expr e;

     for (OutArcIt a(g, n); a != INVALID; ++a) e += f[a];

     for (InArcIt a(g, n); a != INVALID; ++a) e -= f[a];

     lp.addRow(e == 0);

   }

   // Objective function

   Lp::Expr o;

   for (OutArcIt a(g, source); a != INVALID; ++a) o += f[a];

   for (InArcIt a(g, source); a != INVALID; ++a) o -= f[a];

   lp.max();

   lp.obj(o);

   // Solve the LP problem

   lp.solve();

   return lp.primal();

 }

 int main(int argc, char *argv[])

 {

   // Check the arguments

   if (argc < 2) {

     std::cerr << "Usage:" << std::endl;

     std::cerr << "  lp_maxflow_demo <input_file>" << std::endl;

     std::cerr << "The given input file has to contain a maximum flow\n"

               << "problem in LGF format (like 'maxflow.lgf')."

               << std::endl;

     return 0;

   }

   // Read the input file

   SmartDigraph g;

   SmartDigraph::ArcMap<double> cap(g);

   SmartDigraph::Node s, t;

   digraphReader(g, argv[1])

     .arcMap("capacity", cap)

     .node("source", s)

     .node("target", t)

     .run();

   // Solve the problem and print the result

   std::cout << "Max flow value: " << maxFlow(g, cap, s, t) << std::endl;

   return 0;

 }