1.1 --- a/src/work/marci/lp/makefile Mon Nov 22 09:09:18 2004 +0000
1.2 +++ b/src/work/marci/lp/makefile Mon Nov 22 09:12:33 2004 +0000
1.3 @@ -1,9 +1,9 @@
1.4 #INCLUDEDIRS ?= -I.. -I. -I./{marci,jacint,alpar,klao,akos}
1.5 -GLPKROOT = /usr/local/glpk-4.4
1.6 -INCLUDEDIRS ?= -I../../{marci,alpar,klao,akos,athos} -I. -I../../.. -I../.. -I.. -I$(GLPKROOT)/include
1.7 +#GLPKROOT = /usr/local/glpk-4.4
1.8 +INCLUDEDIRS ?= -I../../{marci,alpar,klao,akos,athos} -I. -I../../.. -I../.. -I..# -I$(GLPKROOT)/include
1.9 #INCLUDEDIRS ?= -I../.. -I../.. -I../../{marci,jacint,alpar,klao,akos} -I/usr/local/glpk-4.4/include
1.10 CXXFLAGS = -g -O2 -W -Wall $(INCLUDEDIRS) -ansi -pedantic
1.11 -LDFLAGS = -L$(GLPKROOT)/lib -lglpk
1.12 +LDFLAGS = -lglpk# -L$(GLPKROOT)/lib
1.13
1.14 BINARIES = max_flow_by_lp# sample sample2 sample11 sample15
1.15
2.1 --- a/src/work/marci/lp/max_flow_by_lp.cc Mon Nov 22 09:09:18 2004 +0000
2.2 +++ b/src/work/marci/lp/max_flow_by_lp.cc Mon Nov 22 09:12:33 2004 +0000
2.3 @@ -11,96 +11,13 @@
2.4 #include <augmenting_flow.h>
2.5 //#include <preflow_res.h>
2.6 #include <lp_solver_wrapper.h>
2.7 +#include <min_cost_gen_flow.h>
2.8
2.9 // Use a DIMACS max flow file as stdin.
2.10 // max_flow_demo < dimacs_max_flow_file
2.11
2.12 using namespace lemon;
2.13
2.14 -namespace lemon {
2.15 -
2.16 - template<typename Edge, typename EdgeIndexMap>
2.17 - class PrimalMap {
2.18 - protected:
2.19 - LPSolverWrapper* lp;
2.20 - EdgeIndexMap* edge_index_map;
2.21 - public:
2.22 - PrimalMap(LPSolverWrapper& _lp, EdgeIndexMap& _edge_index_map) :
2.23 - lp(&_lp), edge_index_map(&_edge_index_map) { }
2.24 - double operator[](Edge e) const {
2.25 - return lp->getPrimal((*edge_index_map)[e]);
2.26 - }
2.27 - };
2.28 -
2.29 - // excess: rho-delta
2.30 - template <typename Graph, typename Num,
2.31 - typename Excess=typename Graph::template NodeMap<Num>,
2.32 - typename LCapMap=typename Graph::template EdgeMap<Num>,
2.33 - typename CapMap=typename Graph::template EdgeMap<Num>,
2.34 - typename FlowMap=typename Graph::template EdgeMap<Num>,
2.35 - typename CostMap=typename Graph::template EdgeMap<Num> >
2.36 - class MinCostGenFlow {
2.37 - protected:
2.38 - const Graph& g;
2.39 - const Excess& excess;
2.40 - const LCapMap& lcapacity;
2.41 - const CapMap& capacity;
2.42 - FlowMap& flow;
2.43 - const CostMap& cost;
2.44 - public:
2.45 - MinCostGenFlow(const Graph& _g, const Excess& _excess,
2.46 - const LCapMap& _lcapacity, const CapMap& _capacity,
2.47 - FlowMap& _flow,
2.48 - const CostMap& _cost) :
2.49 - g(_g), excess(_excess), lcapacity(_lcapacity),
2.50 - capacity(_capacity), flow(_flow), cost(_cost) { }
2.51 - void run() {
2.52 - LPSolverWrapper lp;
2.53 - lp.setMinimize();
2.54 - typedef LPSolverWrapper::ColIt ColIt;
2.55 - typedef LPSolverWrapper::RowIt RowIt;
2.56 - typedef typename Graph::template EdgeMap<ColIt> EdgeIndexMap;
2.57 - EdgeIndexMap edge_index_map(g);
2.58 - PrimalMap<typename Graph::Edge, EdgeIndexMap> lp_flow(lp, edge_index_map);
2.59 - for (typename Graph::EdgeIt e(g); e!=INVALID; ++e) {
2.60 - ColIt col_it=lp.addCol();
2.61 - edge_index_map.set(e, col_it);
2.62 - if (lcapacity[e]==capacity[e])
2.63 - lp.setColBounds(col_it, LPX_FX, lcapacity[e], capacity[e]);
2.64 - else
2.65 - lp.setColBounds(col_it, LPX_DB, lcapacity[e], capacity[e]);
2.66 - lp.setObjCoef(col_it, cost[e]);
2.67 - }
2.68 - for (typename Graph::NodeIt n(g); n!=INVALID; ++n) {
2.69 - typename Graph::template EdgeMap<Num> coeffs(g, 0);
2.70 - for (typename Graph::InEdgeIt e(g, n); e!=INVALID; ++e)
2.71 - coeffs.set(e, coeffs[e]+1);
2.72 - for (typename Graph::OutEdgeIt e(g, n); e!=INVALID; ++e)
2.73 - coeffs.set(e, coeffs[e]-1);
2.74 - RowIt row_it=lp.addRow();
2.75 - typename std::vector< std::pair<ColIt, double> > row;
2.76 - //std::cout << "node:" <<g.id(n)<<std::endl;
2.77 - for (typename Graph::EdgeIt e(g); e!=INVALID; ++e) {
2.78 - if (coeffs[e]!=0) {
2.79 - //std::cout << " edge:" <<g.id(e)<<" "<<coeffs[e];
2.80 - row.push_back(std::make_pair(edge_index_map[e], coeffs[e]));
2.81 - }
2.82 - }
2.83 - //std::cout << std::endl;
2.84 - lp.setRowCoeffs(row_it, row.begin(), row.end());
2.85 - lp.setRowBounds(row_it, LPX_FX, 0.0, 0.0);
2.86 - }
2.87 - lp.solveSimplex();
2.88 - //std::cout << lp.colNum() << std::endl;
2.89 - //std::cout << lp.rowNum() << std::endl;
2.90 - //std::cout << "flow value: "<< lp.getObjVal() << std::endl;
2.91 - for (typename Graph::EdgeIt e(g); e!=INVALID; ++e)
2.92 - flow.set(e, lp_flow[e]);
2.93 - }
2.94 - };
2.95 -
2.96 -}
2.97 -
2.98 int main(int, char **) {
2.99
2.100 typedef ListGraph MutableGraph;
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/src/work/marci/lp/min_cost_gen_flow.h Mon Nov 22 09:12:33 2004 +0000
3.3 @@ -0,0 +1,101 @@
3.4 +// -*- c++ -*-
3.5 +#ifndef LEMON_MIN_COST_GEN_FLOW_H
3.6 +#define LEMON_MIN_COST_GEN_FLOW_H
3.7 +//#include <iostream>
3.8 +//#include <fstream>
3.9 +
3.10 +//#include <lemon/smart_graph.h>
3.11 +//#include <lemon/list_graph.h>
3.12 +//#include <lemon/dimacs.h>
3.13 +//#include <lemon/time_measure.h>
3.14 +//#include <graph_wrapper.h>
3.15 +//#include <lemon/preflow.h>
3.16 +//#include <augmenting_flow.h>
3.17 +//#include <preflow_res.h>
3.18 +#include <lemon/../work/marci/lp/lp_solver_wrapper.h>
3.19 +
3.20 +namespace lemon {
3.21 +
3.22 + template<typename Edge, typename EdgeIndexMap>
3.23 + class PrimalMap {
3.24 + protected:
3.25 + LPSolverWrapper* lp;
3.26 + EdgeIndexMap* edge_index_map;
3.27 + public:
3.28 + PrimalMap(LPSolverWrapper& _lp, EdgeIndexMap& _edge_index_map) :
3.29 + lp(&_lp), edge_index_map(&_edge_index_map) { }
3.30 + double operator[](Edge e) const {
3.31 + return lp->getPrimal((*edge_index_map)[e]);
3.32 + }
3.33 + };
3.34 +
3.35 + // excess: rho-delta
3.36 + template <typename Graph, typename Num,
3.37 + typename Excess=typename Graph::template NodeMap<Num>,
3.38 + typename LCapMap=typename Graph::template EdgeMap<Num>,
3.39 + typename CapMap=typename Graph::template EdgeMap<Num>,
3.40 + typename FlowMap=typename Graph::template EdgeMap<Num>,
3.41 + typename CostMap=typename Graph::template EdgeMap<Num> >
3.42 + class MinCostGenFlow {
3.43 + protected:
3.44 + const Graph& g;
3.45 + const Excess& excess;
3.46 + const LCapMap& lcapacity;
3.47 + const CapMap& capacity;
3.48 + FlowMap& flow;
3.49 + const CostMap& cost;
3.50 + public:
3.51 + MinCostGenFlow(const Graph& _g, const Excess& _excess,
3.52 + const LCapMap& _lcapacity, const CapMap& _capacity,
3.53 + FlowMap& _flow,
3.54 + const CostMap& _cost) :
3.55 + g(_g), excess(_excess), lcapacity(_lcapacity),
3.56 + capacity(_capacity), flow(_flow), cost(_cost) { }
3.57 + void run() {
3.58 + LPSolverWrapper lp;
3.59 + lp.setMinimize();
3.60 + typedef LPSolverWrapper::ColIt ColIt;
3.61 + typedef LPSolverWrapper::RowIt RowIt;
3.62 + typedef typename Graph::template EdgeMap<ColIt> EdgeIndexMap;
3.63 + EdgeIndexMap edge_index_map(g);
3.64 + PrimalMap<typename Graph::Edge, EdgeIndexMap> lp_flow(lp, edge_index_map);
3.65 + for (typename Graph::EdgeIt e(g); e!=INVALID; ++e) {
3.66 + ColIt col_it=lp.addCol();
3.67 + edge_index_map.set(e, col_it);
3.68 + if (lcapacity[e]==capacity[e])
3.69 + lp.setColBounds(col_it, LPX_FX, lcapacity[e], capacity[e]);
3.70 + else
3.71 + lp.setColBounds(col_it, LPX_DB, lcapacity[e], capacity[e]);
3.72 + lp.setObjCoef(col_it, cost[e]);
3.73 + }
3.74 + for (typename Graph::NodeIt n(g); n!=INVALID; ++n) {
3.75 + typename Graph::template EdgeMap<Num> coeffs(g, 0);
3.76 + for (typename Graph::InEdgeIt e(g, n); e!=INVALID; ++e)
3.77 + coeffs.set(e, coeffs[e]+1);
3.78 + for (typename Graph::OutEdgeIt e(g, n); e!=INVALID; ++e)
3.79 + coeffs.set(e, coeffs[e]-1);
3.80 + RowIt row_it=lp.addRow();
3.81 + typename std::vector< std::pair<ColIt, double> > row;
3.82 + //std::cout << "node:" <<g.id(n)<<std::endl;
3.83 + for (typename Graph::EdgeIt e(g); e!=INVALID; ++e) {
3.84 + if (coeffs[e]!=0) {
3.85 + //std::cout << " edge:" <<g.id(e)<<" "<<coeffs[e];
3.86 + row.push_back(std::make_pair(edge_index_map[e], coeffs[e]));
3.87 + }
3.88 + }
3.89 + //std::cout << std::endl;
3.90 + lp.setRowCoeffs(row_it, row.begin(), row.end());
3.91 + lp.setRowBounds(row_it, LPX_FX, 0.0, 0.0);
3.92 + }
3.93 + lp.solveSimplex();
3.94 + //std::cout << lp.colNum() << std::endl;
3.95 + //std::cout << lp.rowNum() << std::endl;
3.96 + //std::cout << "flow value: "<< lp.getObjVal() << std::endl;
3.97 + for (typename Graph::EdgeIt e(g); e!=INVALID; ++e)
3.98 + flow.set(e, lp_flow[e]);
3.99 + }
3.100 + };
3.101 +
3.102 +} // namespace lemon
3.103 +
3.104 +#endif //LEMON_MIN_COST_GEN_FLOW_H