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 -}