Changeset 1017:f588efc6d607 in lemon0.x for src/work/marci/lp/max_flow_by_lp.cc
 Timestamp:
 11/22/04 10:12:33 (19 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1407
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/marci/lp/max_flow_by_lp.cc
r1015 r1017 12 12 //#include <preflow_res.h> 13 13 #include <lp_solver_wrapper.h> 14 #include <min_cost_gen_flow.h> 14 15 15 16 // Use a DIMACS max flow file as stdin. … … 17 18 18 19 using namespace lemon; 19 20 namespace lemon {21 22 template<typename Edge, typename EdgeIndexMap>23 class PrimalMap {24 protected:25 LPSolverWrapper* lp;26 EdgeIndexMap* edge_index_map;27 public:28 PrimalMap(LPSolverWrapper& _lp, EdgeIndexMap& _edge_index_map) :29 lp(&_lp), edge_index_map(&_edge_index_map) { }30 double operator[](Edge e) const {31 return lp>getPrimal((*edge_index_map)[e]);32 }33 };34 35 // excess: rhodelta36 template <typename Graph, typename Num,37 typename Excess=typename Graph::template NodeMap<Num>,38 typename LCapMap=typename Graph::template EdgeMap<Num>,39 typename CapMap=typename Graph::template EdgeMap<Num>,40 typename FlowMap=typename Graph::template EdgeMap<Num>,41 typename CostMap=typename Graph::template EdgeMap<Num> >42 class MinCostGenFlow {43 protected:44 const Graph& g;45 const Excess& excess;46 const LCapMap& lcapacity;47 const CapMap& capacity;48 FlowMap& flow;49 const CostMap& cost;50 public:51 MinCostGenFlow(const Graph& _g, const Excess& _excess,52 const LCapMap& _lcapacity, const CapMap& _capacity,53 FlowMap& _flow,54 const CostMap& _cost) :55 g(_g), excess(_excess), lcapacity(_lcapacity),56 capacity(_capacity), flow(_flow), cost(_cost) { }57 void run() {58 LPSolverWrapper lp;59 lp.setMinimize();60 typedef LPSolverWrapper::ColIt ColIt;61 typedef LPSolverWrapper::RowIt RowIt;62 typedef typename Graph::template EdgeMap<ColIt> EdgeIndexMap;63 EdgeIndexMap edge_index_map(g);64 PrimalMap<typename Graph::Edge, EdgeIndexMap> lp_flow(lp, edge_index_map);65 for (typename Graph::EdgeIt e(g); e!=INVALID; ++e) {66 ColIt col_it=lp.addCol();67 edge_index_map.set(e, col_it);68 if (lcapacity[e]==capacity[e])69 lp.setColBounds(col_it, LPX_FX, lcapacity[e], capacity[e]);70 else71 lp.setColBounds(col_it, LPX_DB, lcapacity[e], capacity[e]);72 lp.setObjCoef(col_it, cost[e]);73 }74 for (typename Graph::NodeIt n(g); n!=INVALID; ++n) {75 typename Graph::template EdgeMap<Num> coeffs(g, 0);76 for (typename Graph::InEdgeIt e(g, n); e!=INVALID; ++e)77 coeffs.set(e, coeffs[e]+1);78 for (typename Graph::OutEdgeIt e(g, n); e!=INVALID; ++e)79 coeffs.set(e, coeffs[e]1);80 RowIt row_it=lp.addRow();81 typename std::vector< std::pair<ColIt, double> > row;82 //std::cout << "node:" <<g.id(n)<<std::endl;83 for (typename Graph::EdgeIt e(g); e!=INVALID; ++e) {84 if (coeffs[e]!=0) {85 //std::cout << " edge:" <<g.id(e)<<" "<<coeffs[e];86 row.push_back(std::make_pair(edge_index_map[e], coeffs[e]));87 }88 }89 //std::cout << std::endl;90 lp.setRowCoeffs(row_it, row.begin(), row.end());91 lp.setRowBounds(row_it, LPX_FX, 0.0, 0.0);92 }93 lp.solveSimplex();94 //std::cout << lp.colNum() << std::endl;95 //std::cout << lp.rowNum() << std::endl;96 //std::cout << "flow value: "<< lp.getObjVal() << std::endl;97 for (typename Graph::EdgeIt e(g); e!=INVALID; ++e)98 flow.set(e, lp_flow[e]);99 }100 };101 102 }103 20 104 21 int main(int, char **) {
Note: See TracChangeset
for help on using the changeset viewer.