lp_maxflow_demo.cc File Reference

---

Detailed Description

This demo program shows how to solve a maximum (or maximal) 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 in our library LEMON .

/* -*- C++ -*-
 *
 * 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.
 *
 */


#include<lemon/graph_reader.h>
#include<lemon/list_graph.h>
#include <lemon/lp.h>

#include <fstream>
#include <iostream>



using namespace lemon;

template<class G,class C>
double maxFlow(const G &g,const C &cap,typename G::Node s,typename G::Node t)
{
  Lp lp;
  
  typedef G Graph;
  typedef typename G::Node Node;
  typedef typename G::NodeIt NodeIt;
  typedef typename G::Edge Edge;
  typedef typename G::EdgeIt EdgeIt;
  typedef typename G::OutEdgeIt OutEdgeIt;
  typedef typename G::InEdgeIt InEdgeIt;
  
  //Define a map on the edges for the variables of the LP problem
  typename G::template EdgeMap<Lp::Col> x(g);
  lp.addColSet(x);
  
  //Nonnegativity and capacity constraints
  for(EdgeIt e(g);e!=INVALID;++e) {
    lp.colUpperBound(x[e],cap[e]);
    lp.colLowerBound(x[e],0);
  }


  //Flow conservation constraints for the nodes (except for 's' and 't')
  for(NodeIt n(g);n!=INVALID;++n) if(n!=s&&n!=t) {
    Lp::Expr ex;
    for(InEdgeIt  e(g,n);e!=INVALID;++e) ex+=x[e];
    for(OutEdgeIt e(g,n);e!=INVALID;++e) ex-=x[e];
    lp.addRow(ex==0);
  }
  
  //Objective function: the flow value entering 't'
  Lp::Expr obj;
  for(InEdgeIt  e(g,t);e!=INVALID;++e) obj+=x[e];
  for(OutEdgeIt e(g,t);e!=INVALID;++e) obj-=x[e];
  lp.obj(obj);


  //Maximization
  lp.max();

#if DEFAULT_LP==GLPK
  lp.presolver(true);
  lp.messageLevel(3);
#endif

  std::cout<<"Solver used: "<<default_solver_name<<std::endl;

  //Solve with the underlying solver
  lp.solve();

  return lp.primalValue();
}

int main(int argc, char *argv[]) 
{
  if(argc<2)
  {
      std::cerr << "  USAGE: lp_maxflow_demo input_file.lgf" << std::endl;
      std::cerr << "  The file 'input_file.lgf' has to contain a max "
                << "flow instance in\n"
                << "  LEMON format (e.g. sample.lgf is such a file)."
                << std::endl;
      return 0;
  }


  //input stream to read the graph from
  std::ifstream is(argv[1]);


  ListGraph g;
  ListGraph::Node s;
  ListGraph::Node t;
  
  ListGraph::EdgeMap<double> cap(g);
  
  GraphReader<ListGraph> reader(is,g);
  reader.readNode("source",s).readNode("target",t)
    .readEdgeMap("capacity",cap).run();
  
  std::cout << "Max flow value = " << maxFlow(g,cap,s,t) << std::endl;

}

#include <lemon/graph_reader.h>
#include <lemon/list_graph.h>
#include <lemon/lp.h>
#include <fstream>
#include <iostream>