Several changes. \n If new map is added to mapstorage it emits signal with the name of the new map. This was important, because from now on not only tha mapwin should be updated. \n Furthermore algobox gets a pointer to mapstorage instead of only the mapnames from it. This is important because without it it would be complicated to pass all of the required maps to algobox.
2 * demo/lp_maxflow_demo.cc - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
19 ///\brief Max flow problem solved with an LP solver (demo).
21 /// This demo program shows how to solve a maximum (or maximal) flow
22 /// problem using the LEMON LP solver interface. We would like to lay
23 /// the emphasis on the simplicity of the way one can formulate LP
24 /// constraints that arise in graph theory in our library LEMON .
26 /// \include lp_maxflow_demo.cc
28 #include<lemon/graph_reader.h>
29 #include<lemon/list_graph.h>
37 using namespace lemon;
39 template<class G,class C>
40 double maxFlow(const G &g,const C &cap,typename G::Node s,typename G::Node t)
45 typedef typename G::Node Node;
46 typedef typename G::NodeIt NodeIt;
47 typedef typename G::Edge Edge;
48 typedef typename G::EdgeIt EdgeIt;
49 typedef typename G::OutEdgeIt OutEdgeIt;
50 typedef typename G::InEdgeIt InEdgeIt;
52 //Define a map on the edges for the variables of the LP problem
53 typename G::template EdgeMap<Lp::Col> x(g);
56 //Nonnegativity and capacity constraints
57 for(EdgeIt e(g);e!=INVALID;++e) {
58 lp.colUpperBound(x[e],cap[e]);
59 lp.colLowerBound(x[e],0);
63 //Flow conservation constraints for the nodes (except for 's' and 't')
64 for(NodeIt n(g);n!=INVALID;++n) if(n!=s&&n!=t) {
66 for(InEdgeIt e(g,n);e!=INVALID;++e) ex+=x[e];
67 for(OutEdgeIt e(g,n);e!=INVALID;++e) ex-=x[e];
71 //Objective function: the flow value entering 't'
73 for(InEdgeIt e(g,t);e!=INVALID;++e) obj+=x[e];
74 for(OutEdgeIt e(g,t);e!=INVALID;++e) obj-=x[e];
86 std::cout<<"Solver used: "<<default_solver_name<<std::endl;
88 //Solve with the underlying solver
91 return lp.primalValue();
94 int main(int argc, char *argv[])
98 std::cerr << " USAGE: lp_maxflow_demo input_file.lgf" << std::endl;
99 std::cerr << " The file 'input_file.lgf' has to contain a max "
100 << "flow instance in\n"
101 << " LEMON format (e.g. sample.lgf is such a file)."
107 //input stream to read the graph from
108 std::ifstream is(argv[1]);
115 ListGraph::EdgeMap<double> cap(g);
117 GraphReader<ListGraph> reader(is,g);
118 reader.readNode("source",s).readNode("target",t)
119 .readEdgeMap("capacity",cap).run();
121 std::cout << "Max flow value = " << maxFlow(g,cap,s,t) << std::endl;