1.1 --- a/src/work/marci/lp/min_cost_gen_flow.h	Mon Nov 29 16:11:51 2004 +0000
     1.2 +++ b/src/work/marci/lp/min_cost_gen_flow.h	Mon Nov 29 17:55:46 2004 +0000
     1.3 @@ -1,17 +1,18 @@
     1.4  // -*- c++ -*-
     1.5  #ifndef LEMON_MIN_COST_GEN_FLOW_H
     1.6  #define LEMON_MIN_COST_GEN_FLOW_H
     1.7 -//#include <iostream>
     1.8 +#include <iostream>
     1.9  //#include <fstream>
    1.10  
    1.11 -//#include <lemon/smart_graph.h>
    1.12 -//#include <lemon/list_graph.h>
    1.13 +#include <lemon/smart_graph.h>
    1.14 +#include <lemon/list_graph.h>
    1.15  //#include <lemon/dimacs.h>
    1.16  //#include <lemon/time_measure.h>
    1.17  //#include <graph_wrapper.h>
    1.18 -//#include <lemon/preflow.h>
    1.19 +#include <lemon/preflow.h>
    1.20  //#include <augmenting_flow.h>
    1.21  //#include <preflow_res.h>
    1.22 +#include <../merge_node_graph_wrapper.h>
    1.23  #include <lemon/../work/marci/lp/lp_solver_wrapper.h>
    1.24  
    1.25  namespace lemon {
    1.26 @@ -51,6 +52,71 @@
    1.27  		   const CostMap& _cost) :
    1.28        g(_g), excess(_excess), lcapacity(_lcapacity),
    1.29        capacity(_capacity), flow(_flow), cost(_cost) { }
    1.30 +    bool feasible() {
    1.31 +      //      std::cout << "making new vertices..." << std::endl; 
    1.32 +      typedef ListGraph Graph2;
    1.33 +      Graph2 g2;
    1.34 +      typedef MergeEdgeGraphWrapper<const Graph, Graph2> GW;
    1.35 +      //      std::cout << "merging..." << std::endl; 
    1.36 +      GW gw(g, g2);
    1.37 +      typename GW::Node s(INVALID, g2.addNode(), true);
    1.38 +      typename GW::Node t(INVALID, g2.addNode(), true);
    1.39 +      typedef SmartGraph Graph3;
    1.40 +      //      std::cout << "making extender graph..." << std::endl; 
    1.41 +      typedef NewEdgeSetGraphWrapper2<GW, Graph3> GWW;
    1.42 +//       {
    1.43 +// 	checkConcept<StaticGraph, GWW>();   
    1.44 +//       }
    1.45 +      GWW gww(gw);
    1.46 +      typedef AugmentingGraphWrapper<GW, GWW> GWWW;
    1.47 +      GWWW gwww(gw, gww);
    1.48 +
    1.49 +      //      std::cout << "making new edges..." << std::endl; 
    1.50 +      typename GWWW::template EdgeMap<Num> translated_cap(gwww);
    1.51 +
    1.52 +      for (typename GW::EdgeIt e(gw); e!=INVALID; ++e)
    1.53 +      translated_cap.set(typename GWWW::Edge(e,INVALID,false), 
    1.54 +			 capacity[e]-lcapacity[e]);
    1.55 +
    1.56 +      Num expected=0;
    1.57 +
    1.58 +      //      std::cout << "making new edges 2..." << std::endl; 
    1.59 +      for (typename Graph::NodeIt n(g); n!=INVALID; ++n) {
    1.60 +	Num a=0;
    1.61 +	for (typename Graph::InEdgeIt e(g, n); e!=INVALID; ++e)
    1.62 +	  a+=lcapacity[e];
    1.63 +	for (typename Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) 
    1.64 +	  a-=lcapacity[e];
    1.65 +	if (excess[n]>a) {
    1.66 +	  typename GWW::Edge e=
    1.67 +	    gww.addEdge(typename GW::Node(n,INVALID,false), t);
    1.68 +	  translated_cap.set(typename GWWW::Edge(INVALID, e, true), 
    1.69 +			     excess[n]-a);
    1.70 +	}
    1.71 +	if (excess[n]<a) {
    1.72 +	  typename GWW::Edge e=
    1.73 +	    gww.addEdge(s, typename GW::Node(n,INVALID,false));
    1.74 +	  translated_cap.set(typename GWWW::Edge(INVALID, e, true), 
    1.75 +			     a-excess[n]);
    1.76 +	  expected+=a-excess[n];
    1.77 +	}
    1.78 +      }
    1.79 +
    1.80 +      //      std::cout << "preflow..." << std::endl; 
    1.81 +      typename GWWW::template EdgeMap<Num> translated_flow(gwww, 0);
    1.82 +      Preflow<GWWW, Num> preflow(gwww, s, t, 
    1.83 +				 translated_cap, translated_flow);
    1.84 +      preflow.run();
    1.85 +      //      std::cout << "fv: " << preflow.flowValue() << std::endl; 
    1.86 +      //      std::cout << "expected: " << expected << std::endl; 
    1.87 +
    1.88 +      for (typename Graph::EdgeIt e(g); e!=INVALID; ++e) {
    1.89 +	typename GW::Edge ew(e, INVALID, false);
    1.90 +	typename GWWW::Edge ewww(ew, INVALID, false);
    1.91 +	flow.set(e, translated_flow[ewww]+lcapacity[e]);
    1.92 +      }
    1.93 +      return (expected>=preflow.flowValue());
    1.94 +    }
    1.95      void run() {
    1.96        LPSolverWrapper lp;
    1.97        lp.setMinimize();