LEMON Tutorial  59
lp_maxflow_demo.cc File Reference

Demo program that solves maximum flow problems using the LP interface. More...

#include <iostream>
#include <lemon/smart_graph.h>
#include <lemon/lgf_reader.h>
#include <lemon/lp.h>

Detailed Description

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.

/* -*- 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.
#include <iostream>
#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)
// 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);
// 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;
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
for (OutArcIt a(g, source); a != INVALID; ++a) o += f[a];
for (InArcIt a(g, source); a != INVALID; ++a) o -= f[a];
// Solve the LP problem
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')."
return 0;
// Read the input file
SmartDigraph::ArcMap<double> cap(g);
SmartDigraph::Node s, t;
digraphReader(g, argv[1])
.arcMap("capacity", cap)
.node("source", s)
.node("target", t)
// Solve the problem and print the result
std::cout << "Max flow value: " << maxFlow(g, cap, s, t) << std::endl;
return 0;