COIN-OR::LEMON - Graph Library

Changeset 109:fc5982b39e10 in lemon-0.x for src/work/jacint/preflow_hl3.h


Ignore:
Timestamp:
02/21/04 22:01:22 (16 years ago)
Author:
jacint
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@144
Message:

Flows with test files. The best is preflow.h

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/jacint/preflow_hl3.h

    r105 r109  
    33preflow_hl3.h
    44by jacint.
    5 Runs the highest label variant of the preflow push algorithm with
    6 running time O(n^2\sqrt(m)), with the felszippantos 'empty level'
    7 and with the two-phase heuristic: if there is no active node of
    8 level at most n, then we go into phase 1, do a bfs
    9 from s, and flow the excess back to s.
    10 
    11 In phase 1 we shift everything downwards by n.
    12 
    13 'A' is a parameter for the empty_level heuristic
    14 
    15 Member functions:
    16 
    17 void run() : runs the algorithm
    18 
    19  The following functions should be used after run() was already run.
    20 
    21 T maxflow() : returns the value of a maximum flow
    22 
    23 T flowonedge(EdgeIt e) : for a fixed maximum flow x it returns x(e)
    24 
    25 FlowMap allflow() : returns the fixed maximum flow x
    26 
    27 void mincut(CutMap& M) : sets M to the characteristic vector of a
     5
     6Heuristics:
     7
     8 suck gap : if there is a gap, then we put all
     9   nodes reachable from the relabelled node to level n
     10 2 phase
     11 highest label
     12
     13The constructor runs the algorithm.
     14
     15Members:
     16
     17T maxFlow() : returns the value of a maximum flow
     18
     19T flowOnEdge(EdgeIt e) : for a fixed maximum flow x it returns x(e)
     20
     21FlowMap Flow() : returns the fixed maximum flow x
     22
     23void minCut(CutMap& M) : sets M to the characteristic vector of a
    2824     minimum cut. M should be a map of bools initialized to false.
    2925
    30 void min_mincut(CutMap& M) : sets M to the characteristic vector of the
     26void minMinCut(CutMap& M) : sets M to the characteristic vector of the
    3127     minimum min cut. M should be a map of bools initialized to false.
    3228
    33 void max_mincut(CutMap& M) : sets M to the characteristic vector of the
     29void maxMinCut(CutMap& M) : sets M to the characteristic vector of the
    3430     maximum min cut. M should be a map of bools initialized to false.
    3531
     
    3834#ifndef PREFLOW_HL3_H
    3935#define PREFLOW_HL3_H
    40 
    41 #define A 1
    4236
    4337#include <vector>
     
    4539#include <queue>
    4640
     41#include <time_measure.h> //for test
     42
    4743namespace hugo {
    4844
    4945  template <typename Graph, typename T,
    50     typename FlowMap=typename Graph::EdgeMap<T>, typename CapMap=typename Graph::EdgeMap<T>,
    51     typename IntMap=typename Graph::NodeMap<int>, typename TMap=typename Graph::NodeMap<T> >
     46    typename FlowMap=typename Graph::EdgeMap<T>,
     47    typename CapMap=typename Graph::EdgeMap<T> >
    5248  class preflow_hl3 {
    5349   
     
    6763  public:
    6864
     65    double time; //for test
     66
    6967    preflow_hl3(Graph& _G, NodeIt _s, NodeIt _t, CapMap& _capacity) :
    70       G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity) { }
    71 
    72 
    73     void run() {
    74  
     68      G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity) {
     69     
    7570      bool phase=0;
    7671      int n=G.nodeNum();
     
    8176      */
    8277
    83       IntMap level(G,n);     
    84       TMap excess(G);
     78      typename Graph::NodeMap<int> level(G,n);     
     79      typename Graph::NodeMap<T> excess(G);
    8580     
    8681      std::vector<int> numb(n);   
     
    149144          if ( phase ) break;
    150145          phase=1;
    151 
     146          time=currTime();
     147         
    152148          level.set(s,0);
    153149
     
    188184        else {
    189185         
    190           NodeIt w=stack[b].top();        //w is a highest label active node.
     186          NodeIt w=stack[b].top();
    191187          stack[b].pop();           
    192188          int lev=level.get(w);
    193           int exc=excess.get(w);
    194           int newlevel=n;                 //In newlevel we bound the next level of w.
     189          T exc=excess.get(w);
     190          int newlevel=n;          //bound on the next level of w.
    195191         
    196192          for(OutEdgeIt e=G.template first<OutEdgeIt>(w); e.valid(); ++e) {
     
    207203              /*v becomes active.*/
    208204             
    209               int cap=capacity.get(e);
    210               int flo=flow.get(e);
    211               int remcap=cap-flo;
     205              T cap=capacity.get(e);
     206              T flo=flow.get(e);
     207              T remcap=cap-flo;
    212208             
    213209              if ( remcap >= exc ) {       
     
    245241              /*v becomes active.*/
    246242             
    247               int flo=flow.get(e);
     243              T flo=flow.get(e);
    248244             
    249245              if ( flo >= exc ) {
     
    350346     */
    351347
    352     T maxflow() {
     348    T maxFlow() {
    353349      return value;
    354350    }
     
    357353
    358354    /*
    359       For the maximum flow x found by the algorithm, it returns the flow value on Edge e, i.e. x(e).
     355      For the maximum flow x found by the algorithm,
     356      it returns the flow value on edge e, i.e. x(e).
    360357    */
    361358
    362     T flowonedge(EdgeIt e) {
     359    T flowOnEdge(EdgeIt e) {
    363360      return flow.get(e);
    364361    }
     
    370367    */
    371368
    372     FlowMap allflow() {
     369    FlowMap Flow() {
    373370      return flow;
    374371    }
     
    382379   
    383380    template<typename CutMap>
    384     void mincut(CutMap& M) {
     381    void minCut(CutMap& M) {
    385382   
    386383      std::queue<NodeIt> queue;
     
    421418   
    422419    template<typename CutMap>
    423     void max_mincut(CutMap& M) {
     420    void maxMinCut(CutMap& M) {
    424421   
    425422      std::queue<NodeIt> queue;
     
    458455
    459456    template<typename CutMap>
    460     void min_mincut(CutMap& M) {
    461       mincut(M);
     457    void minMinCut(CutMap& M) {
     458      minCut(M);
    462459    }
    463460
     
    465462
    466463  };
    467 }//namespace hugo
     464}//namespace
    468465#endif
    469466
Note: See TracChangeset for help on using the changeset viewer.