1.1 --- a/src/work/athos/lp_old/max_flow_expression.cc Sun Apr 17 18:57:22 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,109 +0,0 @@
1.4 -// -*- c++ -*-
1.5 -#include <iostream>
1.6 -#include <fstream>
1.7 -
1.8 -#include <lemon/graph_utils.h>
1.9 -#include <lemon/smart_graph.h>
1.10 -#include <lemon/list_graph.h>
1.11 -#include <lemon/dimacs.h>
1.12 -#include <lemon/time_measure.h>
1.13 -#include <lp_solver_glpk.h>
1.14 -
1.15 -using std::cout;
1.16 -using std::endl;
1.17 -using namespace lemon;
1.18 -
1.19 -template<typename Edge, typename EdgeIndexMap>
1.20 -class PrimalMap {
1.21 -protected:
1.22 - LpGlpk* lp;
1.23 - EdgeIndexMap* edge_index_map;
1.24 -public:
1.25 - PrimalMap(LpGlpk& _lp, EdgeIndexMap& _edge_index_map) :
1.26 - lp(&_lp), edge_index_map(&_edge_index_map) { }
1.27 - double operator[](Edge e) const {
1.28 - return lp->getPrimal((*edge_index_map)[e]);
1.29 - }
1.30 -};
1.31 -
1.32 -// Use a DIMACS max flow file as stdin.
1.33 -// max_flow_expresion < dimacs_max_flow_file
1.34 -
1.35 -int main(int, char **) {
1.36 -
1.37 - typedef ListGraph Graph;
1.38 - typedef Graph::Node Node;
1.39 - typedef Graph::Edge Edge;
1.40 - typedef Graph::EdgeIt EdgeIt;
1.41 -
1.42 - Graph g;
1.43 -
1.44 - Node s, t;
1.45 - Graph::EdgeMap<int> cap(g);
1.46 - readDimacs(std::cin, g, cap, s, t);
1.47 - Timer ts;
1.48 -
1.49 - typedef LpGlpk LPSolver;
1.50 - LPSolver lp;
1.51 - lp.setMaximize();
1.52 - typedef LPSolver::Col Col;
1.53 - typedef LPSolver::Row Row;
1.54 - typedef Graph::EdgeMap<Col> EdgeIndexMap;
1.55 - typedef Graph::NodeMap<Row> NodeIndexMap;
1.56 - EdgeIndexMap edge_index_map(g);
1.57 - NodeIndexMap node_index_map(g);
1.58 - PrimalMap<Edge, EdgeIndexMap> flow(lp, edge_index_map);
1.59 -
1.60 - // nonnegativity of flow and capacity function
1.61 - for (Graph::EdgeIt e(g); e!=INVALID; ++e) {
1.62 - Col col=lp.addCol();
1.63 - edge_index_map.set(e, col);
1.64 - // interesting property in GLPK:
1.65 - // if you change the order of the following two lines, the
1.66 - // two runs of GLPK are extremely different
1.67 - lp.setColLowerBound(col, 0);
1.68 - lp.setColUpperBound(col, cap[e]);
1.69 - }
1.70 -
1.71 - for (Graph::NodeIt n(g); n!=INVALID; ++n) {
1.72 - LPSolver::Expression expr;
1.73 - for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e)
1.74 - expr+=edge_index_map[e];
1.75 - for (Graph::InEdgeIt e(g, n); e!=INVALID; ++e)
1.76 - expr-=edge_index_map[e];
1.77 - // cost function
1.78 - if (n==s) {
1.79 - lp.setObjCoeffs(expr);
1.80 - }
1.81 - // flow conservation constraints
1.82 - if ((n!=s) && (n!=t)) {
1.83 - node_index_map.set(n, lp.addRow(expr == 0.0));
1.84 - }
1.85 - }
1.86 - lp.solveSimplex();
1.87 - cout << "elapsed time: " << ts << endl;
1.88 -// cout << "rows:" << endl;
1.89 -// for (
1.90 -// LPSolver::Rows::ClassIt i(lp.row_iter_map, 0);
1.91 -// i!=INVALID;
1.92 -// ++i) {
1.93 -// cout << i << " ";
1.94 -// }
1.95 -// cout << endl;
1.96 -// cout << "cols:" << endl;
1.97 -// for (
1.98 -// LPSolver::Cols::ClassIt i(lp.col_iter_map, 0);
1.99 -// i!=INVALID;
1.100 -// ++i) {
1.101 -// cout << i << " ";
1.102 -// }
1.103 -// cout << endl;
1.104 - lp.setMIP();
1.105 - cout << "elapsed time: " << ts << endl;
1.106 - for (LPSolver::Cols::ClassIt it(lp.col_iter_map ,1); it!=INVALID; ++it) {
1.107 - lp.setColInt(it);
1.108 - }
1.109 - cout << "elapsed time: " << ts << endl;
1.110 - lp.solveBandB();
1.111 - cout << "elapsed time: " << ts << endl;
1.112 -}