1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/marci/lp/min_cost_gen_flow.h Mon Nov 22 09:12:33 2004 +0000
1.3 @@ -0,0 +1,101 @@
1.4 +// -*- c++ -*-
1.5 +#ifndef LEMON_MIN_COST_GEN_FLOW_H
1.6 +#define LEMON_MIN_COST_GEN_FLOW_H
1.7 +//#include <iostream>
1.8 +//#include <fstream>
1.9 +
1.10 +//#include <lemon/smart_graph.h>
1.11 +//#include <lemon/list_graph.h>
1.12 +//#include <lemon/dimacs.h>
1.13 +//#include <lemon/time_measure.h>
1.14 +//#include <graph_wrapper.h>
1.15 +//#include <lemon/preflow.h>
1.16 +//#include <augmenting_flow.h>
1.17 +//#include <preflow_res.h>
1.18 +#include <lemon/../work/marci/lp/lp_solver_wrapper.h>
1.19 +
1.20 +namespace lemon {
1.21 +
1.22 + template<typename Edge, typename EdgeIndexMap>
1.23 + class PrimalMap {
1.24 + protected:
1.25 + LPSolverWrapper* lp;
1.26 + EdgeIndexMap* edge_index_map;
1.27 + public:
1.28 + PrimalMap(LPSolverWrapper& _lp, EdgeIndexMap& _edge_index_map) :
1.29 + lp(&_lp), edge_index_map(&_edge_index_map) { }
1.30 + double operator[](Edge e) const {
1.31 + return lp->getPrimal((*edge_index_map)[e]);
1.32 + }
1.33 + };
1.34 +
1.35 + // excess: rho-delta
1.36 + template <typename Graph, typename Num,
1.37 + typename Excess=typename Graph::template NodeMap<Num>,
1.38 + typename LCapMap=typename Graph::template EdgeMap<Num>,
1.39 + typename CapMap=typename Graph::template EdgeMap<Num>,
1.40 + typename FlowMap=typename Graph::template EdgeMap<Num>,
1.41 + typename CostMap=typename Graph::template EdgeMap<Num> >
1.42 + class MinCostGenFlow {
1.43 + protected:
1.44 + const Graph& g;
1.45 + const Excess& excess;
1.46 + const LCapMap& lcapacity;
1.47 + const CapMap& capacity;
1.48 + FlowMap& flow;
1.49 + const CostMap& cost;
1.50 + public:
1.51 + MinCostGenFlow(const Graph& _g, const Excess& _excess,
1.52 + const LCapMap& _lcapacity, const CapMap& _capacity,
1.53 + FlowMap& _flow,
1.54 + const CostMap& _cost) :
1.55 + g(_g), excess(_excess), lcapacity(_lcapacity),
1.56 + capacity(_capacity), flow(_flow), cost(_cost) { }
1.57 + void run() {
1.58 + LPSolverWrapper lp;
1.59 + lp.setMinimize();
1.60 + typedef LPSolverWrapper::ColIt ColIt;
1.61 + typedef LPSolverWrapper::RowIt RowIt;
1.62 + typedef typename Graph::template EdgeMap<ColIt> EdgeIndexMap;
1.63 + EdgeIndexMap edge_index_map(g);
1.64 + PrimalMap<typename Graph::Edge, EdgeIndexMap> lp_flow(lp, edge_index_map);
1.65 + for (typename Graph::EdgeIt e(g); e!=INVALID; ++e) {
1.66 + ColIt col_it=lp.addCol();
1.67 + edge_index_map.set(e, col_it);
1.68 + if (lcapacity[e]==capacity[e])
1.69 + lp.setColBounds(col_it, LPX_FX, lcapacity[e], capacity[e]);
1.70 + else
1.71 + lp.setColBounds(col_it, LPX_DB, lcapacity[e], capacity[e]);
1.72 + lp.setObjCoef(col_it, cost[e]);
1.73 + }
1.74 + for (typename Graph::NodeIt n(g); n!=INVALID; ++n) {
1.75 + typename Graph::template EdgeMap<Num> coeffs(g, 0);
1.76 + for (typename Graph::InEdgeIt e(g, n); e!=INVALID; ++e)
1.77 + coeffs.set(e, coeffs[e]+1);
1.78 + for (typename Graph::OutEdgeIt e(g, n); e!=INVALID; ++e)
1.79 + coeffs.set(e, coeffs[e]-1);
1.80 + RowIt row_it=lp.addRow();
1.81 + typename std::vector< std::pair<ColIt, double> > row;
1.82 + //std::cout << "node:" <<g.id(n)<<std::endl;
1.83 + for (typename Graph::EdgeIt e(g); e!=INVALID; ++e) {
1.84 + if (coeffs[e]!=0) {
1.85 + //std::cout << " edge:" <<g.id(e)<<" "<<coeffs[e];
1.86 + row.push_back(std::make_pair(edge_index_map[e], coeffs[e]));
1.87 + }
1.88 + }
1.89 + //std::cout << std::endl;
1.90 + lp.setRowCoeffs(row_it, row.begin(), row.end());
1.91 + lp.setRowBounds(row_it, LPX_FX, 0.0, 0.0);
1.92 + }
1.93 + lp.solveSimplex();
1.94 + //std::cout << lp.colNum() << std::endl;
1.95 + //std::cout << lp.rowNum() << std::endl;
1.96 + //std::cout << "flow value: "<< lp.getObjVal() << std::endl;
1.97 + for (typename Graph::EdgeIt e(g); e!=INVALID; ++e)
1.98 + flow.set(e, lp_flow[e]);
1.99 + }
1.100 + };
1.101 +
1.102 +} // namespace lemon
1.103 +
1.104 +#endif //LEMON_MIN_COST_GEN_FLOW_H