1.1 --- a/src/work/marci/lp/lp_solver_wrapper_3.h Fri Jan 28 09:09:59 2005 +0000
1.2 +++ b/src/work/marci/lp/lp_solver_wrapper_3.h Fri Jan 28 14:33:32 2005 +0000
1.3 @@ -10,6 +10,7 @@
1.4 #include <stdlib.h>
1.5 #include <iostream>
1.6 #include <map>
1.7 +#include <limits>
1.8 // #include <stdio>
1.9 //#include <stdlib>
1.10 extern "C" {
1.11 @@ -196,6 +197,8 @@
1.12 const int VALID_CLASS;
1.13 /// \e
1.14 const int INVALID_CLASS;
1.15 + /// \e
1.16 + static const _Value INF;
1.17 public:
1.18 /// \e
1.19 LPSolverBase() : row_iter_map(2),
1.20 @@ -221,10 +224,10 @@
1.21 virtual int _addCol() = 0;
1.22 /// \e
1.23 virtual void _setRowCoeffs(int i,
1.24 - std::vector<std::pair<int, double> > coeffs) = 0;
1.25 + const std::vector<std::pair<int, _Value> >& coeffs) = 0;
1.26 /// \e
1.27 virtual void _setColCoeffs(int i,
1.28 - std::vector<std::pair<int, double> > coeffs) = 0;
1.29 + const std::vector<std::pair<int, _Value> >& coeffs) = 0;
1.30 /// \e
1.31 virtual void _eraseCol(int i) = 0;
1.32 /// \e
1.33 @@ -423,6 +426,9 @@
1.34 virtual void printColStatus(int i) = 0;
1.35 };
1.36
1.37 + template <typename _Value>
1.38 + const _Value LPSolverBase<_Value>::INF=std::numeric_limits<_Value>::infinity();
1.39 +
1.40
1.41 /// \brief Wrappers for LP solvers
1.42 ///
1.43 @@ -474,7 +480,7 @@
1.44 }
1.45 /// \e
1.46 virtual void _setRowCoeffs(int i,
1.47 - std::vector<std::pair<int, double> > coeffs) {
1.48 + const std::vector<std::pair<int, double> >& coeffs) {
1.49 int mem_length=1+colNum();
1.50 int* indices = new int[mem_length];
1.51 double* doubles = new double[mem_length];
1.52 @@ -494,7 +500,7 @@
1.53 }
1.54 /// \e
1.55 virtual void _setColCoeffs(int i,
1.56 - std::vector<std::pair<int, double> > coeffs) {
1.57 + const std::vector<std::pair<int, double> >& coeffs) {
1.58 int mem_length=1+rowNum();
1.59 int* indices = new int[mem_length];
1.60 double* doubles = new double[mem_length];
2.1 --- a/src/work/marci/lp/makefile Fri Jan 28 09:09:59 2005 +0000
2.2 +++ b/src/work/marci/lp/makefile Fri Jan 28 14:33:32 2005 +0000
2.3 @@ -5,7 +5,7 @@
2.4 CXXFLAGS = -g -O2 -W -Wall $(INCLUDEDIRS) -ansi -pedantic
2.5 LDFLAGS = -lglpk#-lcplex -lm -lpthread -lilocplex -L/usr/local/cplex/cplex75/lib/i86_linux2_glibc2.2_gcc3.0/static_mt# -L$(GLPKROOT)/lib
2.6
2.7 -BINARIES = expression_test max_flow_by_lp# sample sample2 sample11 sample15
2.8 +BINARIES = max_flow_expression expression_test max_flow_by_lp# sample sample2 sample11 sample15
2.9
2.10 #include ../makefile
2.11
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/src/work/marci/lp/max_flow_expression.cc Fri Jan 28 14:33:32 2005 +0000
3.3 @@ -0,0 +1,87 @@
3.4 +// -*- c++ -*-
3.5 +#include <iostream>
3.6 +#include <fstream>
3.7 +
3.8 +#include <lemon/smart_graph.h>
3.9 +#include <lemon/list_graph.h>
3.10 +#include <lemon/dimacs.h>
3.11 +#include <lemon/time_measure.h>
3.12 +#include <lp_solver_wrapper_3.h>
3.13 +
3.14 +using std::cout;
3.15 +using std::endl;
3.16 +using namespace lemon;
3.17 +
3.18 +template<typename Edge, typename EdgeIndexMap>
3.19 +class PrimalMap {
3.20 +protected:
3.21 + LPGLPK* lp;
3.22 + EdgeIndexMap* edge_index_map;
3.23 +public:
3.24 + PrimalMap(LPGLPK& _lp, EdgeIndexMap& _edge_index_map) :
3.25 + lp(&_lp), edge_index_map(&_edge_index_map) { }
3.26 + double operator[](Edge e) const {
3.27 + return lp->getPrimal((*edge_index_map)[e]);
3.28 + }
3.29 +};
3.30 +
3.31 +// Use a DIMACS max flow file as stdin.
3.32 +// max_flow_expresion < dimacs_max_flow_file
3.33 +
3.34 +int main(int, char **) {
3.35 +
3.36 + typedef ListGraph Graph;
3.37 + typedef Graph::Node Node;
3.38 + typedef Graph::Edge Edge;
3.39 + typedef Graph::EdgeIt EdgeIt;
3.40 +
3.41 + Graph g;
3.42 +
3.43 + Node s, t;
3.44 + Graph::EdgeMap<int> cap(g);
3.45 + readDimacs(std::cin, g, cap, s, t);
3.46 + Timer ts;
3.47 +
3.48 + typedef LPGLPK LPSolver;
3.49 + LPSolver lp;
3.50 + lp.setMaximize();
3.51 + typedef LPSolver::ColIt ColIt;
3.52 + typedef LPSolver::RowIt RowIt;
3.53 + typedef Graph::EdgeMap<ColIt> EdgeIndexMap;
3.54 + EdgeIndexMap edge_index_map(g);
3.55 + PrimalMap<Edge, EdgeIndexMap> lp_flow(lp, edge_index_map);
3.56 +
3.57 + // capacity function
3.58 + for (Graph::EdgeIt e(g); e!=INVALID; ++e) {
3.59 + ColIt col_it=lp.addCol();
3.60 + edge_index_map.set(e, col_it);
3.61 + if (cap[e]==0)
3.62 + lp.setColBounds(col_it, LPSolver::FIXED, 0, cap[e]);
3.63 + else
3.64 + lp.setColBounds(col_it, LPSolver::DOUBLE, 0, cap[e]);
3.65 + }
3.66 +
3.67 + for (Graph::NodeIt n(g); n!=INVALID; ++n) {
3.68 + LPSolver::Expression expr;
3.69 + for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e)
3.70 + expr+=edge_index_map[e];
3.71 + for (Graph::InEdgeIt e(g, n); e!=INVALID; ++e)
3.72 + expr-=edge_index_map[e];
3.73 + // cost function
3.74 + if (n==s) {
3.75 + lp.setObjCoeffs(expr);
3.76 + }
3.77 + // flow conservation
3.78 + if ((n!=s) && (n!=t)) {
3.79 + RowIt row_it=lp.addRow();
3.80 + lp.setRowCoeffs(row_it, expr);
3.81 + lp.setRowBounds(row_it, LPSolver::FIXED, 0.0, 0.0);
3.82 + }
3.83 + }
3.84 + lp.solveSimplex();
3.85 + //std::cout << lp.colNum() << std::endl;
3.86 + //std::cout << lp.rowNum() << std::endl;
3.87 + //std::cout << "flow value: "<< lp.getObjVal() << std::endl;
3.88 + for (Graph::EdgeIt e(g); e!=INVALID; ++e)
3.89 + flow.set(e, lp_flow[e]);
3.90 +}