COIN-OR::LEMON - Graph Library

Changeset 1028:2497336d7e14 in lemon-0.x


Ignore:
Timestamp:
12/02/04 20:59:30 (15 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1418
Message:

:-)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/marci/lp/min_cost_gen_flow.h

    r1025 r1028  
    1111//#include <graph_wrapper.h>
    1212#include <lemon/preflow.h>
     13#include <lemon/min_cost_flow.h>
    1314//#include <augmenting_flow.h>
    1415//#include <preflow_res.h>
    15 #include <../merge_node_graph_wrapper.h>
    16 #include <lemon/../work/marci/lp/lp_solver_wrapper.h>
     16#include <work/marci/merge_node_graph_wrapper.h>
     17#include <work/marci/lp/lp_solver_wrapper.h>
    1718
    1819namespace lemon {
     
    3132  };
    3233
    33   // excess: rho-delta
     34  // excess: rho-delta egyelore csak =0-ra.
    3435  template <typename Graph, typename Num,
    3536            typename Excess=typename Graph::template NodeMap<Num>,
     
    7576      typename GWWW::template EdgeMap<Num> translated_cap(gwww);
    7677
    77       for (typename GW::EdgeIt e(gw); e!=INVALID; ++e)
    78       translated_cap.set(typename GWWW::Edge(e,INVALID,false),
    79                          capacity[e]-lcapacity[e]);
     78      for (typename GW::EdgeIt e(gw); e!=INVALID; ++e) {
     79        translated_cap.set(typename GWWW::Edge(e,INVALID,false),
     80                           capacity[e]-lcapacity[e]);
     81        //      cout << "t_cap " << gw.id(e) << " "
     82        //           << translated_cap[typename GWWW::Edge(e,INVALID,false)] << endl;
     83      }
    8084
    8185      Num expected=0;
     
    9397          translated_cap.set(typename GWWW::Edge(INVALID, e, true),
    9498                             excess[n]-a);
     99          //      std::cout << g.id(n) << "->t " << excess[n]-a << std::endl;
    95100        }
    96101        if (excess[n]<a) {
     
    100105                             a-excess[n]);
    101106          expected+=a-excess[n];
     107          //      std::cout << "s->" << g.id(n) << " "<< a-excess[n] <<std:: endl;
    102108        }
    103109      }
     
    118124      return (expected>=preflow.flowValue());
    119125    }
    120     void run() {
     126    // for nonnegative costs
     127    bool run() {
     128      //      std::cout << "making new vertices..." << std::endl;
     129      typedef ListGraph Graph2;
     130      Graph2 g2;
     131      typedef MergeEdgeGraphWrapper<const Graph, Graph2> GW;
     132      //      std::cout << "merging..." << std::endl;
     133      GW gw(g, g2);
     134      typename GW::Node s(INVALID, g2.addNode(), true);
     135      typename GW::Node t(INVALID, g2.addNode(), true);
     136      typedef SmartGraph Graph3;
     137      //      std::cout << "making extender graph..." << std::endl;
     138      typedef NewEdgeSetGraphWrapper2<GW, Graph3> GWW;
     139//       {
     140//      checkConcept<StaticGraph, GWW>();   
     141//       }
     142      GWW gww(gw);
     143      typedef AugmentingGraphWrapper<GW, GWW> GWWW;
     144      GWWW gwww(gw, gww);
     145
     146      //      std::cout << "making new edges..." << std::endl;
     147      typename GWWW::template EdgeMap<Num> translated_cap(gwww);
     148
     149      for (typename Graph::EdgeIt e(g); e!=INVALID; ++e) {
     150        typename GW::Edge ew(e, INVALID, false);
     151        typename GWWW::Edge ewww(ew, INVALID, false);
     152        translated_cap.set(ewww, capacity[e]-lcapacity[e]);
     153        //      cout << "t_cap " << g.id(e) << " "
     154        //           << translated_cap[ewww] << endl;
     155      }
     156
     157      Num expected=0;
     158
     159      //      std::cout << "making new edges 2..." << std::endl;
     160      for (typename Graph::NodeIt n(g); n!=INVALID; ++n) {
     161        //      std::cout << "node: " << g.id(n) << std::endl;
     162        Num a=0;
     163        for (typename Graph::InEdgeIt e(g, n); e!=INVALID; ++e) {
     164          a+=lcapacity[e];
     165          //      std::cout << "bee: " << g.id(e) << " " << lcapacity[e] << std::endl;
     166        }
     167        for (typename Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) {
     168          a-=lcapacity[e];
     169          //      std::cout << "kie: " << g.id(e) << " " << lcapacity[e] << std::endl;
     170        }
     171        //      std::cout << "excess " << g.id(n) << ": " << a << std::endl;
     172        if (0>a) {
     173          typename GWW::Edge e=
     174            gww.addEdge(typename GW::Node(n,INVALID,false), t);
     175          translated_cap.set(typename GWWW::Edge(INVALID, e, true),
     176                             -a);
     177          //      std::cout << g.id(n) << "->t " << -a << std::endl;
     178        }
     179        if (0<a) {
     180          typename GWW::Edge e=
     181            gww.addEdge(s, typename GW::Node(n,INVALID,false));
     182          translated_cap.set(typename GWWW::Edge(INVALID, e, true),
     183                             a);
     184          expected+=a;
     185          //      std::cout << "s->" << g.id(n) << " "<< a <<std:: endl;
     186        }
     187      }
     188
     189      //      std::cout << "preflow..." << std::endl;
     190      typename GWWW::template EdgeMap<Num> translated_cost(gwww, 0);
     191      for (typename Graph::EdgeIt e(g); e!=INVALID; ++e) {
     192        translated_cost.set(typename GWWW::Edge(
     193        typename GW::Edge(e, INVALID, false), INVALID, false), cost[e]);
     194      }
     195      //      typename GWWW::template EdgeMap<Num> translated_flow(gwww, 0);
     196      MinCostFlow<GWWW, typename GWWW::template EdgeMap<Num>,
     197      typename GWWW::template EdgeMap<Num> >
     198      min_cost_flow(gwww, translated_cost, translated_cap,
     199                    s, t);
     200      while (min_cost_flow.augment()) { }
     201      std::cout << "fv: " << min_cost_flow.flowValue() << std::endl;
     202      std::cout << "expected: " << expected << std::endl;
     203
     204      for (typename Graph::EdgeIt e(g); e!=INVALID; ++e) {
     205        typename GW::Edge ew(e, INVALID, false);
     206        typename GWWW::Edge ewww(ew, INVALID, false);
     207        //      std::cout << g.id(e) << " " << flow[e] << std::endl;
     208        flow.set(e, lcapacity[e]+
     209                 min_cost_flow.getFlow()[ewww]);
     210      }
     211      return (expected>=min_cost_flow.flowValue());
     212    }
     213    void runByLP() {
    121214      LPSolverWrapper lp;
    122215      lp.setMinimize();
Note: See TracChangeset for help on using the changeset viewer.