diff -r ee5959aa4410 -r c280de819a73 src/work/marci/lp/min_cost_gen_flow.h
--- a/src/work/marci/lp/min_cost_gen_flow.h	Sun Apr 17 18:57:22 2005 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,268 +0,0 @@
-// -*- c++ -*-
-#ifndef LEMON_MIN_COST_GEN_FLOW_H
-#define LEMON_MIN_COST_GEN_FLOW_H
-#include <iostream>
-//#include <fstream>
-
-#include <lemon/smart_graph.h>
-#include <lemon/list_graph.h>
-//#include <lemon/dimacs.h>
-//#include <lemon/time_measure.h>
-//#include <graph_wrapper.h>
-#include <lemon/preflow.h>
-#include <lemon/min_cost_flow.h>
-//#include <augmenting_flow.h>
-//#include <preflow_res.h>
-#include <work/marci/merge_node_graph_wrapper.h>
-#include <work/marci/lp/lp_solver_wrapper_3.h>
-
-namespace lemon {
-
-  template<typename Edge, typename EdgeIndexMap> 
-  class PrimalMap {
-  protected:
-    LPGLPK* lp;
-    EdgeIndexMap* edge_index_map;
-  public:
-    PrimalMap(LPGLPK& _lp, EdgeIndexMap& _edge_index_map) : 
-      lp(&_lp), edge_index_map(&_edge_index_map) { }
-    double operator[](Edge e) const { 
-      return lp->getPrimal((*edge_index_map)[e]);
-    }
-  };
-
-  // excess: rho-delta egyelore csak =0-ra.
-  template <typename Graph, typename Num,
-	    typename Excess=typename Graph::template NodeMap<Num>, 
-	    typename LCapMap=typename Graph::template EdgeMap<Num>,
-	    typename CapMap=typename Graph::template EdgeMap<Num>,
-            typename FlowMap=typename Graph::template EdgeMap<Num>,
-	    typename CostMap=typename Graph::template EdgeMap<Num> >
-  class MinCostGenFlow {
-  protected:
-    const Graph& g;
-    const Excess& excess;
-    const LCapMap& lcapacity;
-    const CapMap& capacity;
-    FlowMap& flow;
-    const CostMap& cost;
-  public:
-    MinCostGenFlow(const Graph& _g, const Excess& _excess, 
-		   const LCapMap& _lcapacity, const CapMap& _capacity, 
-		   FlowMap& _flow, 
-		   const CostMap& _cost) :
-      g(_g), excess(_excess), lcapacity(_lcapacity),
-      capacity(_capacity), flow(_flow), cost(_cost) { }
-    bool feasible() {
-      //      std::cout << "making new vertices..." << std::endl; 
-      typedef ListGraph Graph2;
-      Graph2 g2;
-      typedef MergeEdgeGraphWrapper<const Graph, Graph2> GW;
-      //      std::cout << "merging..." << std::endl; 
-      GW gw(g, g2);
-      typename GW::Node s(INVALID, g2.addNode(), true);
-      typename GW::Node t(INVALID, g2.addNode(), true);
-      typedef SmartGraph Graph3;
-      //      std::cout << "making extender graph..." << std::endl; 
-      typedef NewEdgeSetGraphWrapper2<GW, Graph3> GWW;
-//       {
-// 	checkConcept<StaticGraph, GWW>();   
-//       }
-      GWW gww(gw);
-      typedef AugmentingGraphWrapper<GW, GWW> GWWW;
-      GWWW gwww(gw, gww);
-
-      //      std::cout << "making new edges..." << std::endl; 
-      typename GWWW::template EdgeMap<Num> translated_cap(gwww);
-
-      for (typename GW::EdgeIt e(gw); e!=INVALID; ++e) {
-	translated_cap.set(typename GWWW::Edge(e,INVALID,false), 
-			   capacity[e]-lcapacity[e]);
-	//	cout << "t_cap " << gw.id(e) << " " 
-	//	     << translated_cap[typename GWWW::Edge(e,INVALID,false)] << endl;
-      }
-
-      Num expected=0;
-
-      //      std::cout << "making new edges 2..." << std::endl; 
-      for (typename Graph::NodeIt n(g); n!=INVALID; ++n) {
-	Num a=0;
-	for (typename Graph::InEdgeIt e(g, n); e!=INVALID; ++e)
-	  a+=lcapacity[e];
-	for (typename Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) 
-	  a-=lcapacity[e];
-	if (excess[n]>a) {
-	  typename GWW::Edge e=
-	    gww.addEdge(typename GW::Node(n,INVALID,false), t);
-	  translated_cap.set(typename GWWW::Edge(INVALID, e, true), 
-			     excess[n]-a);
-	  //	  std::cout << g.id(n) << "->t " << excess[n]-a << std::endl;
-	}
-	if (excess[n]<a) {
-	  typename GWW::Edge e=
-	    gww.addEdge(s, typename GW::Node(n,INVALID,false));
-	  translated_cap.set(typename GWWW::Edge(INVALID, e, true), 
-			     a-excess[n]);
-	  expected+=a-excess[n];
-	  //	  std::cout << "s->" << g.id(n) << " "<< a-excess[n] <<std:: endl;
-	}
-      }
-
-      //      std::cout << "preflow..." << std::endl; 
-      typename GWWW::template EdgeMap<Num> translated_flow(gwww, 0);
-      Preflow<GWWW, Num> preflow(gwww, s, t, 
-				 translated_cap, translated_flow);
-      preflow.run();
-      //      std::cout << "fv: " << preflow.flowValue() << std::endl; 
-      //      std::cout << "expected: " << expected << std::endl; 
-
-      for (typename Graph::EdgeIt e(g); e!=INVALID; ++e) {
-	typename GW::Edge ew(e, INVALID, false);
-	typename GWWW::Edge ewww(ew, INVALID, false);
-	flow.set(e, translated_flow[ewww]+lcapacity[e]);
-      }
-      return (preflow.flowValue()>=expected);
-    }
-    // for nonnegative costs
-    bool run() {
-      //      std::cout << "making new vertices..." << std::endl; 
-      typedef ListGraph Graph2;
-      Graph2 g2;
-      typedef MergeEdgeGraphWrapper<const Graph, Graph2> GW;
-      //      std::cout << "merging..." << std::endl; 
-      GW gw(g, g2);
-      typename GW::Node s(INVALID, g2.addNode(), true);
-      typename GW::Node t(INVALID, g2.addNode(), true);
-      typedef SmartGraph Graph3;
-      //      std::cout << "making extender graph..." << std::endl; 
-      typedef NewEdgeSetGraphWrapper2<GW, Graph3> GWW;
-//       {
-// 	checkConcept<StaticGraph, GWW>();   
-//       }
-      GWW gww(gw);
-      typedef AugmentingGraphWrapper<GW, GWW> GWWW;
-      GWWW gwww(gw, gww);
-
-      //      std::cout << "making new edges..." << std::endl; 
-      typename GWWW::template EdgeMap<Num> translated_cap(gwww);
-
-      for (typename Graph::EdgeIt e(g); e!=INVALID; ++e) {
-	typename GW::Edge ew(e, INVALID, false);
-	typename GWWW::Edge ewww(ew, INVALID, false);
-	translated_cap.set(ewww, capacity[e]-lcapacity[e]);
-	//	cout << "t_cap " << g.id(e) << " " 
-	//	     << translated_cap[ewww] << endl;
-      }
-
-      Num expected=0;
-
-      //      std::cout << "making new edges 2..." << std::endl; 
-      for (typename Graph::NodeIt n(g); n!=INVALID; ++n) {
-	//	std::cout << "node: " << g.id(n) << std::endl;
-	Num a=0;
-	for (typename Graph::InEdgeIt e(g, n); e!=INVALID; ++e) {
-	  a+=lcapacity[e];
-	  //	  std::cout << "bee: " << g.id(e) << " " << lcapacity[e] << std::endl;
-	}
-	for (typename Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) {
-	  a-=lcapacity[e];
-	  //	  std::cout << "kie: " << g.id(e) << " " << lcapacity[e] << std::endl;
-	}
-	//	std::cout << "excess " << g.id(n) << ": " << a << std::endl;
-	if (0>a) {
-	  typename GWW::Edge e=
-	    gww.addEdge(typename GW::Node(n,INVALID,false), t);
-	  translated_cap.set(typename GWWW::Edge(INVALID, e, true), 
-			     -a);
-	  //	  std::cout << g.id(n) << "->t " << -a << std::endl;
-	}
-	if (0<a) {
-	  typename GWW::Edge e=
-	    gww.addEdge(s, typename GW::Node(n,INVALID,false));
-	  translated_cap.set(typename GWWW::Edge(INVALID, e, true), 
-			     a);
-	  expected+=a;
-	  //	  std::cout << "s->" << g.id(n) << " "<< a <<std:: endl;
-	}
-      }
-
-      //      std::cout << "preflow..." << std::endl; 
-      typename GWWW::template EdgeMap<Num> translated_cost(gwww, 0);
-      for (typename Graph::EdgeIt e(g); e!=INVALID; ++e) {
-	translated_cost.set(typename GWWW::Edge(
-        typename GW::Edge(e, INVALID, false), INVALID, false), cost[e]);
-      }
-      //      typename GWWW::template EdgeMap<Num> translated_flow(gwww, 0);
-      MinCostFlow<GWWW, typename GWWW::template EdgeMap<Num>, 
-      typename GWWW::template EdgeMap<Num> > 
-      min_cost_flow(gwww, translated_cost, translated_cap, 
-		    s, t);
-      while (min_cost_flow.augment()) { }
-      std::cout << "fv: " << min_cost_flow.flowValue() << std::endl; 
-      std::cout << "expected: " << expected << std::endl; 
-
-      for (typename Graph::EdgeIt e(g); e!=INVALID; ++e) {
-	typename GW::Edge ew(e, INVALID, false);
-	typename GWWW::Edge ewww(ew, INVALID, false);
-	//	std::cout << g.id(e) << " " << flow[e] << std::endl;
-	flow.set(e, lcapacity[e]+
-		 min_cost_flow.getFlow()[ewww]);
-      }
-      return (min_cost_flow.flowValue()>=expected);
-    }
-    void runByLP() {
-      typedef LPGLPK LPSolver;
-      LPSolver lp;
-      lp.setMinimize();
-      typedef LPSolver::ColIt ColIt;
-      typedef LPSolver::RowIt RowIt;
-      typedef typename Graph::template EdgeMap<ColIt> EdgeIndexMap;
-      EdgeIndexMap edge_index_map(g);
-      PrimalMap<typename Graph::Edge, EdgeIndexMap> lp_flow(lp, edge_index_map);
-      for (typename Graph::EdgeIt e(g); e!=INVALID; ++e) {
-	ColIt col_it=lp.addCol();
-	edge_index_map.set(e, col_it);
-	if (lcapacity[e]==capacity[e])
-	  lp.setColBounds(col_it, LPSolver::FIXED, lcapacity[e], capacity[e]);
-	else 
-	  lp.setColBounds(col_it, LPSolver::DOUBLE, lcapacity[e], capacity[e]);
-	lp.setObjCoef(col_it, cost[e]);
-      }
-      LPSolver::ColIt col_it;
-      for (lp.col_iter_map.first(col_it, lp.VALID_CLASS); 
-	   lp.col_iter_map.valid(col_it); 
-	   lp.col_iter_map.next(col_it)) {
-//	std::cout << "ize " << lp.col_iter_map[col_it] << std::endl;
-      }
-      for (typename Graph::NodeIt n(g); n!=INVALID; ++n) {
-	typename Graph::template EdgeMap<Num> coeffs(g, 0);
-	for (typename Graph::InEdgeIt e(g, n); e!=INVALID; ++e)
-	coeffs.set(e, coeffs[e]+1);
-	for (typename Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) 
-	coeffs.set(e, coeffs[e]-1);
-	RowIt row_it=lp.addRow();
-	typename std::vector< std::pair<ColIt, double> > row;
-	//std::cout << "node:" <<g.id(n)<<std::endl;
-	for (typename Graph::EdgeIt e(g); e!=INVALID; ++e) {
-	  if (coeffs[e]!=0) {
-	    //std::cout << " edge:" <<g.id(e)<<" "<<coeffs[e];
-	    row.push_back(std::make_pair(edge_index_map[e], coeffs[e]));
-	  }
-	}
-	//std::cout << std::endl;
-	//std::cout << " " << g.id(n) << " " << row.size() << std::endl;
-	lp.setRowCoeffs(row_it, row.begin(), row.end());
-	lp.setRowBounds(row_it, LPSolver::FIXED, 0.0, 0.0);
-      }
-      lp.solveSimplex();
-      //std::cout << lp.colNum() << std::endl;
-      //std::cout << lp.rowNum() << std::endl;
-      //std::cout << "flow value: "<< lp.getObjVal() << std::endl;
-      for (typename Graph::EdgeIt e(g); e!=INVALID; ++e) 
-      flow.set(e, lp_flow[e]);
-    }
-  };
-
-} // namespace lemon
-
-#endif //LEMON_MIN_COST_GEN_FLOW_H