source: lemon-tutorial/demo/lp_maxflow_demo.cc @ 58:10b6a5b7d4c0

/* -*- 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;
}