NewMapWin has become Dialog instead of Window. Therefore it is created dynamically, when there is need for it, instead of keeping one instance in memory. This solution is slower, but more correct than before.
2 * demo/lp_maxflow_demo.cc - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 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;