COIN-OR::LEMON - Graph Library

source: lemon-tutorial/demo/lp_maxflow_demo.cc @ 54:e99a7fb6bff5

Last change on this file since 54:e99a7fb6bff5 was 54:e99a7fb6bff5, checked in by Peter Kovacs <kpeter@…>, 14 years ago

Port and rework LP demo files from SVN -r3524

File size: 2.8 KB
Line 
1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
5 * Copyright (C) 2003-2010
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19///\file
20///\brief Demo program that solves maximum flow problems using the LP interface
21///
22/// This demo program shows how to solve the maximum flow problem using
23/// the LEMON LP solver interface. We would like to lay the emphasis on the
24/// simplicity of the way one can formulate LP constraints that arise in graph
25/// theory using LEMON.
26///
27/// \include lp_maxflow_demo.cc
28
29#include <iostream>
30#include <lemon/smart_graph.h>
31#include <lemon/lgf_reader.h>
32#include <lemon/lp.h>
33
34using namespace lemon;
35
36template <typename GR, typename CAP>
37double maxFlow(const GR &g, const CAP &capacity,
38               typename GR::Node source, typename GR::Node target)
39{
40  TEMPLATE_DIGRAPH_TYPEDEFS(GR);
41 
42  // Create an instance of the default LP solver
43  Lp lp;
44
45  // Add a column to the problem for each arc
46  typename GR::template ArcMap<Lp::Col> f(g);
47  lp.addColSet(f);
48
49  // Capacity constraints
50  for (ArcIt a(g); a != INVALID; ++a) {
51    lp.colLowerBound(f[a], 0);
52    lp.colUpperBound(f[a], capacity[a]);
53  }
54
55  // Flow conservation constraints
56  for (NodeIt n(g); n != INVALID; ++n) {
57    if (n == source || n == target) continue;
58    Lp::Expr e;
59    for (OutArcIt a(g, n); a != INVALID; ++a) e += f[a];
60    for (InArcIt a(g, n); a != INVALID; ++a) e -= f[a];
61    lp.addRow(e == 0);
62  }
63
64  // Objective function
65  Lp::Expr o;
66  for (OutArcIt a(g, source); a != INVALID; ++a) o += f[a];
67  for (InArcIt a(g, source); a != INVALID; ++a) o -= f[a];
68  lp.max();
69  lp.obj(o);
70
71  // Solve the LP problem
72  lp.solve();
73
74  return lp.primal();
75}
76
77
78int main(int argc, char *argv[])
79{
80  // Check the arguments
81  if (argc < 2) {
82    std::cerr << "Usage:" << std::endl;
83    std::cerr << "  lp_maxflow_demo <input_file>" << std::endl;
84    std::cerr << "The given input file has to contain a maximum flow\n"
85              << "problem in LGF format (like 'maxflow.lgf')."
86              << std::endl;
87    return 0;
88  }
89 
90  // Read the input file
91  SmartDigraph g;
92  SmartDigraph::ArcMap<double> cap(g);
93  SmartDigraph::Node s, t;
94
95  digraphReader(g, argv[1])
96    .arcMap("capacity", cap)
97    .node("source", s)
98    .node("target", t)
99    .run();
100
101  // Solve the problem and print the result
102  std::cout << "Max flow value: " << maxFlow(g, cap, s, t) << std::endl;
103 
104  return 0;
105}
Note: See TracBrowser for help on using the repository browser.