athos@1560: /* -*- C++ -*- athos@1560: * alpar@1956: * This file is a part of LEMON, a generic C++ optimization library alpar@1956: * alpar@2553: * Copyright (C) 2003-2008 alpar@1956: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport athos@1560: * (Egervary Research Group on Combinatorial Optimization, EGRES). athos@1560: * athos@1560: * Permission to use, modify and distribute this software is granted athos@1560: * provided that this copyright notice appears in all copies. For athos@1560: * precise terms see the accompanying LICENSE file. athos@1560: * athos@1560: * This software is provided "AS IS" with no warranty of any kind, athos@1560: * express or implied, and with no claim as to its suitability for any athos@1560: * purpose. athos@1560: * athos@1560: */ athos@1560: athos@1560: ///\ingroup demos athos@1560: ///\file athos@1560: ///\brief Max flow problem solved with an LP solver (demo). athos@1560: /// athos@1583: /// This demo program shows how to solve a maximum (or maximal) flow athos@1583: /// problem using the LEMON LP solver interface. We would like to lay athos@1583: /// the emphasis on the simplicity of the way one can formulate LP athos@1583: /// constraints that arise in graph theory in our library LEMON . alpar@1641: /// alpar@1641: /// \include lp_maxflow_demo.cc athos@1560: alpar@1361: #include alpar@1361: #include alpar@1610: #include alpar@1361: athos@1560: #include athos@1560: #include athos@1560: alpar@1381: alpar@1381: alpar@1361: using namespace lemon; alpar@1361: alpar@1361: template alpar@1361: double maxFlow(const G &g,const C &cap,typename G::Node s,typename G::Node t) alpar@1361: { alpar@1610: Lp lp; alpar@1361: alpar@1361: typedef G Graph; alpar@1361: typedef typename G::Node Node; alpar@1361: typedef typename G::NodeIt NodeIt; alpar@1361: typedef typename G::Edge Edge; alpar@1361: typedef typename G::EdgeIt EdgeIt; alpar@1361: typedef typename G::OutEdgeIt OutEdgeIt; alpar@1361: typedef typename G::InEdgeIt InEdgeIt; alpar@1361: athos@1518: //Define a map on the edges for the variables of the LP problem alpar@1610: typename G::template EdgeMap x(g); alpar@1361: lp.addColSet(x); alpar@1361: athos@1518: //Nonnegativity and capacity constraints alpar@1361: for(EdgeIt e(g);e!=INVALID;++e) { alpar@1361: lp.colUpperBound(x[e],cap[e]); alpar@1361: lp.colLowerBound(x[e],0); alpar@1361: } alpar@1361: athos@1518: athos@1518: //Flow conservation constraints for the nodes (except for 's' and 't') alpar@1361: for(NodeIt n(g);n!=INVALID;++n) if(n!=s&&n!=t) { alpar@1610: Lp::Expr ex; alpar@1361: for(InEdgeIt e(g,n);e!=INVALID;++e) ex+=x[e]; alpar@1361: for(OutEdgeIt e(g,n);e!=INVALID;++e) ex-=x[e]; alpar@1361: lp.addRow(ex==0); alpar@1361: } athos@1518: athos@1518: //Objective function: the flow value entering 't' alpar@1610: Lp::Expr obj; alpar@1571: for(InEdgeIt e(g,t);e!=INVALID;++e) obj+=x[e]; alpar@1571: for(OutEdgeIt e(g,t);e!=INVALID;++e) obj-=x[e]; deba@2369: lp.obj(obj); alpar@1571: athos@1518: athos@1518: //Maximization alpar@1361: lp.max(); alpar@1361: alpar@1610: #if DEFAULT_LP==GLPK alpar@1361: lp.presolver(true); alpar@1361: lp.messageLevel(3); alpar@1381: #endif alpar@1361: athos@1577: std::cout<<"Solver used: "< cap(g); alpar@1361: athos@1560: GraphReader reader(is,g); deba@1394: reader.readNode("source",s).readNode("target",t) deba@1394: .readEdgeMap("capacity",cap).run(); alpar@1361: alpar@1361: std::cout << "Max flow value = " << maxFlow(g,cap,s,t) << std::endl; alpar@1361: alpar@1361: }