marci@1017: // -*- c++ -*- marci@1017: #ifndef LEMON_MIN_COST_GEN_FLOW_H marci@1017: #define LEMON_MIN_COST_GEN_FLOW_H marci@1017: //#include <iostream> marci@1017: //#include <fstream> marci@1017: marci@1017: //#include <lemon/smart_graph.h> marci@1017: //#include <lemon/list_graph.h> marci@1017: //#include <lemon/dimacs.h> marci@1017: //#include <lemon/time_measure.h> marci@1017: //#include <graph_wrapper.h> marci@1017: //#include <lemon/preflow.h> marci@1017: //#include <augmenting_flow.h> marci@1017: //#include <preflow_res.h> marci@1017: #include <lemon/../work/marci/lp/lp_solver_wrapper.h> marci@1017: marci@1017: namespace lemon { marci@1017: marci@1017: template<typename Edge, typename EdgeIndexMap> marci@1017: class PrimalMap { marci@1017: protected: marci@1017: LPSolverWrapper* lp; marci@1017: EdgeIndexMap* edge_index_map; marci@1017: public: marci@1017: PrimalMap(LPSolverWrapper& _lp, EdgeIndexMap& _edge_index_map) : marci@1017: lp(&_lp), edge_index_map(&_edge_index_map) { } marci@1017: double operator[](Edge e) const { marci@1017: return lp->getPrimal((*edge_index_map)[e]); marci@1017: } marci@1017: }; marci@1017: marci@1017: // excess: rho-delta marci@1017: template <typename Graph, typename Num, marci@1017: typename Excess=typename Graph::template NodeMap<Num>, marci@1017: typename LCapMap=typename Graph::template EdgeMap<Num>, marci@1017: typename CapMap=typename Graph::template EdgeMap<Num>, marci@1017: typename FlowMap=typename Graph::template EdgeMap<Num>, marci@1017: typename CostMap=typename Graph::template EdgeMap<Num> > marci@1017: class MinCostGenFlow { marci@1017: protected: marci@1017: const Graph& g; marci@1017: const Excess& excess; marci@1017: const LCapMap& lcapacity; marci@1017: const CapMap& capacity; marci@1017: FlowMap& flow; marci@1017: const CostMap& cost; marci@1017: public: marci@1017: MinCostGenFlow(const Graph& _g, const Excess& _excess, marci@1017: const LCapMap& _lcapacity, const CapMap& _capacity, marci@1017: FlowMap& _flow, marci@1017: const CostMap& _cost) : marci@1017: g(_g), excess(_excess), lcapacity(_lcapacity), marci@1017: capacity(_capacity), flow(_flow), cost(_cost) { } marci@1017: void run() { marci@1017: LPSolverWrapper lp; marci@1017: lp.setMinimize(); marci@1017: typedef LPSolverWrapper::ColIt ColIt; marci@1017: typedef LPSolverWrapper::RowIt RowIt; marci@1017: typedef typename Graph::template EdgeMap<ColIt> EdgeIndexMap; marci@1017: EdgeIndexMap edge_index_map(g); marci@1017: PrimalMap<typename Graph::Edge, EdgeIndexMap> lp_flow(lp, edge_index_map); marci@1017: for (typename Graph::EdgeIt e(g); e!=INVALID; ++e) { marci@1017: ColIt col_it=lp.addCol(); marci@1017: edge_index_map.set(e, col_it); marci@1017: if (lcapacity[e]==capacity[e]) marci@1017: lp.setColBounds(col_it, LPX_FX, lcapacity[e], capacity[e]); marci@1017: else marci@1017: lp.setColBounds(col_it, LPX_DB, lcapacity[e], capacity[e]); marci@1017: lp.setObjCoef(col_it, cost[e]); marci@1017: } marci@1017: for (typename Graph::NodeIt n(g); n!=INVALID; ++n) { marci@1017: typename Graph::template EdgeMap<Num> coeffs(g, 0); marci@1017: for (typename Graph::InEdgeIt e(g, n); e!=INVALID; ++e) marci@1017: coeffs.set(e, coeffs[e]+1); marci@1017: for (typename Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) marci@1017: coeffs.set(e, coeffs[e]-1); marci@1017: RowIt row_it=lp.addRow(); marci@1017: typename std::vector< std::pair<ColIt, double> > row; marci@1017: //std::cout << "node:" <<g.id(n)<<std::endl; marci@1017: for (typename Graph::EdgeIt e(g); e!=INVALID; ++e) { marci@1017: if (coeffs[e]!=0) { marci@1017: //std::cout << " edge:" <<g.id(e)<<" "<<coeffs[e]; marci@1017: row.push_back(std::make_pair(edge_index_map[e], coeffs[e])); marci@1017: } marci@1017: } marci@1017: //std::cout << std::endl; marci@1017: lp.setRowCoeffs(row_it, row.begin(), row.end()); marci@1017: lp.setRowBounds(row_it, LPX_FX, 0.0, 0.0); marci@1017: } marci@1017: lp.solveSimplex(); marci@1017: //std::cout << lp.colNum() << std::endl; marci@1017: //std::cout << lp.rowNum() << std::endl; marci@1017: //std::cout << "flow value: "<< lp.getObjVal() << std::endl; marci@1017: for (typename Graph::EdgeIt e(g); e!=INVALID; ++e) marci@1017: flow.set(e, lp_flow[e]); marci@1017: } marci@1017: }; marci@1017: marci@1017: } // namespace lemon marci@1017: marci@1017: #endif //LEMON_MIN_COST_GEN_FLOW_H