kpeter@54: /* -*- mode: C++; indent-tabs-mode: nil; -*-
kpeter@54:  *
kpeter@54:  * This file is a part of LEMON, a generic C++ optimization library.
kpeter@54:  *
kpeter@54:  * Copyright (C) 2003-2010
kpeter@54:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
kpeter@54:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
kpeter@54:  *
kpeter@54:  * Permission to use, modify and distribute this software is granted
kpeter@54:  * provided that this copyright notice appears in all copies. For
kpeter@54:  * precise terms see the accompanying LICENSE file.
kpeter@54:  *
kpeter@54:  * This software is provided "AS IS" with no warranty of any kind,
kpeter@54:  * express or implied, and with no claim as to its suitability for any
kpeter@54:  * purpose.
kpeter@54:  *
kpeter@54:  */
kpeter@54: 
kpeter@54: ///\file
kpeter@54: ///\brief Demo program that solves maximum flow problems using the LP interface
kpeter@54: ///
kpeter@54: /// This demo program shows how to solve the maximum flow problem using
kpeter@54: /// the LEMON LP solver interface. We would like to lay the emphasis on the
kpeter@54: /// simplicity of the way one can formulate LP constraints that arise in graph
kpeter@54: /// theory using LEMON.
kpeter@54: ///
kpeter@54: /// \include lp_maxflow_demo.cc
kpeter@54: 
kpeter@54: #include <iostream>
kpeter@54: #include <lemon/smart_graph.h>
kpeter@54: #include <lemon/lgf_reader.h>
kpeter@54: #include <lemon/lp.h>
kpeter@54: 
kpeter@54: using namespace lemon;
kpeter@54: 
kpeter@54: template <typename GR, typename CAP>
kpeter@54: double maxFlow(const GR &g, const CAP &capacity,
kpeter@54:                typename GR::Node source, typename GR::Node target)
kpeter@54: {
kpeter@54:   TEMPLATE_DIGRAPH_TYPEDEFS(GR);
kpeter@54:   
kpeter@54:   // Create an instance of the default LP solver
kpeter@54:   Lp lp;
kpeter@54: 
kpeter@54:   // Add a column to the problem for each arc
kpeter@54:   typename GR::template ArcMap<Lp::Col> f(g);
kpeter@54:   lp.addColSet(f);
kpeter@54: 
kpeter@54:   // Capacity constraints
kpeter@54:   for (ArcIt a(g); a != INVALID; ++a) {
kpeter@54:     lp.colLowerBound(f[a], 0);
kpeter@54:     lp.colUpperBound(f[a], capacity[a]);
kpeter@54:   }
kpeter@54: 
kpeter@54:   // Flow conservation constraints
kpeter@54:   for (NodeIt n(g); n != INVALID; ++n) {
kpeter@54:     if (n == source || n == target) continue;
kpeter@54:     Lp::Expr e;
kpeter@54:     for (OutArcIt a(g, n); a != INVALID; ++a) e += f[a];
kpeter@54:     for (InArcIt a(g, n); a != INVALID; ++a) e -= f[a];
kpeter@54:     lp.addRow(e == 0);
kpeter@54:   }
kpeter@54: 
kpeter@54:   // Objective function
kpeter@54:   Lp::Expr o;
kpeter@54:   for (OutArcIt a(g, source); a != INVALID; ++a) o += f[a];
kpeter@54:   for (InArcIt a(g, source); a != INVALID; ++a) o -= f[a];
kpeter@54:   lp.max();
kpeter@54:   lp.obj(o);
kpeter@54: 
kpeter@54:   // Solve the LP problem
kpeter@54:   lp.solve();
kpeter@54: 
kpeter@54:   return lp.primal();
kpeter@54: }
kpeter@54: 
kpeter@54: 
kpeter@54: int main(int argc, char *argv[])
kpeter@54: {
kpeter@54:   // Check the arguments
kpeter@54:   if (argc < 2) {
kpeter@54:     std::cerr << "Usage:" << std::endl;
kpeter@54:     std::cerr << "  lp_maxflow_demo <input_file>" << std::endl;
kpeter@54:     std::cerr << "The given input file has to contain a maximum flow\n"
kpeter@54:               << "problem in LGF format (like 'maxflow.lgf')."
kpeter@54:               << std::endl;
kpeter@54:     return 0;
kpeter@54:   }
kpeter@54:   
kpeter@54:   // Read the input file
kpeter@54:   SmartDigraph g;
kpeter@54:   SmartDigraph::ArcMap<double> cap(g);
kpeter@54:   SmartDigraph::Node s, t;
kpeter@54: 
kpeter@54:   digraphReader(g, argv[1])
kpeter@54:     .arcMap("capacity", cap)
kpeter@54:     .node("source", s)
kpeter@54:     .node("target", t)
kpeter@54:     .run();
kpeter@54: 
kpeter@54:   // Solve the problem and print the result
kpeter@54:   std::cout << "Max flow value: " << maxFlow(g, cap, s, t) << std::endl;
kpeter@54:  
kpeter@54:   return 0;
kpeter@54: }