COIN-OR::LEMON - Graph Library

Changeset 372:e6a156fc186d in lemon-0.x for src/work/jacint/preflow.h


Ignore:
Timestamp:
04/22/04 16:11:28 (17 years ago)
Author:
jacint
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@502
Message:
 
File:
1 edited

Legend:

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

    r330 r372  
    11// -*- C++ -*-
     2
     3//run gyorsan tudna adni a minmincutot a 2 fazis elejen , ne vegyuk be konstruktorba egy cutmapet?
     4//constzero jo igy?
     5
     6//majd marci megmondja betegyem-e bfs-t meg resgraphot
     7
    28/*
    39Heuristics:
     
    1319Constructors:
    1420
    15 Preflow(Graph, Node, Node, CapMap, FlowMap)
     21Preflow(Graph, Node, Node, CapMap, FlowMap, bool) : bool must be false if
     22     FlowMap is not constant zero, and should be true if it is
    1623
    1724Members:
     
    3037     a min cut. M should be a map of bools initialized to false.
    3138
     39FIXME reset
     40
    3241*/
    3342
     
    4554  template <typename Graph, typename T,
    4655            typename CapMap=typename Graph::EdgeMap<T>,
    47             typename FlowMap=typename Graph::EdgeMap<T> >
     56            typename FlowMap=typename Graph::EdgeMap<T> >
    4857  class Preflow {
    4958   
     
    6069    FlowMap& flow;
    6170    T value;
     71    bool constzero;
    6272
    6373  public:
    64     Preflow(const Graph& _G, Node _s, Node _t, const CapMap& _capacity,
    65             FlowMap& _flow ) :
    66       G(_G), s(_s), t(_t), capacity(_capacity), flow(_flow) {}
    67 
     74    Preflow(Graph& _G, Node _s, Node _t, CapMap& _capacity,
     75            FlowMap& _flow, bool _constzero ) :
     76      G(_G), s(_s), t(_t), capacity(_capacity), flow(_flow), constzero(_constzero) {}
     77   
     78   
    6879    void run() {
     80     
     81      value=0;                //for the subsequent runs
    6982
    7083      bool phase=0;        //phase 0 is the 1st phase, phase 1 is the 2nd
     
    90103      typename Graph::NodeMap<T> excess(G);
    91104
    92       std::vector<Node> active(n,INVALID);
     105      std::vector<Node> active(n-1,INVALID);
    93106      typename Graph::NodeMap<Node> next(G,INVALID);
    94107      //Stack of the active nodes in level i < n.
     
    102115      */
    103116
    104       /*Reverse_bfs from t, to find the starting level.*/
    105       level.set(t,0);
    106       std::queue<Node> bfs_queue;
    107       bfs_queue.push(t);
    108 
    109       while (!bfs_queue.empty()) {
    110 
    111         Node v=bfs_queue.front();       
    112         bfs_queue.pop();
    113         int l=level[v]+1;
    114 
    115         InEdgeIt e;
    116         for(G.first(e,v); G.valid(e); G.next(e)) {
    117           Node w=G.tail(e);
    118           if ( level[w] == n && w != s ) {
    119             bfs_queue.push(w);
    120             Node first=level_list[l];
    121             if ( G.valid(first) ) left.set(first,w);
    122             right.set(w,first);
    123             level_list[l]=w;
    124             level.set(w, l);
    125           }
    126         }
    127       }
    128      
    129       level.set(s,n);
    130      
    131 
    132       /* Starting flow. It is everywhere 0 at the moment. */     
    133       OutEdgeIt e;
    134       for(G.first(e,s); G.valid(e); G.next(e))
     117
     118      if ( constzero ) {
     119     
     120        /*Reverse_bfs from t, to find the starting level.*/
     121        level.set(t,0);
     122        std::queue<Node> bfs_queue;
     123        bfs_queue.push(t);
     124       
     125        while (!bfs_queue.empty()) {
     126         
     127          Node v=bfs_queue.front();     
     128          bfs_queue.pop();
     129          int l=level[v]+1;
     130         
     131          InEdgeIt e;
     132          for(G.first(e,v); G.valid(e); G.next(e)) {
     133            Node w=G.tail(e);
     134            if ( level[w] == n && w != s ) {
     135              bfs_queue.push(w);
     136              Node first=level_list[l];
     137              if ( G.valid(first) ) left.set(first,w);
     138              right.set(w,first);
     139              level_list[l]=w;
     140              level.set(w, l);
     141            }
     142          }
     143        }
     144
     145        //the starting flow
     146        OutEdgeIt e;
     147        for(G.first(e,s); G.valid(e); G.next(e))
    135148        {
    136149          T c=capacity[e];
     
    146159          }
    147160        }
     161      }
     162      else
     163      {
     164       
     165        /*
     166          Reverse_bfs from t in the residual graph,
     167          to find the starting level.
     168        */
     169        level.set(t,0);
     170        std::queue<Node> bfs_queue;
     171        bfs_queue.push(t);
     172       
     173        while (!bfs_queue.empty()) {
     174         
     175          Node v=bfs_queue.front();     
     176          bfs_queue.pop();
     177          int l=level[v]+1;
     178         
     179          InEdgeIt e;
     180          for(G.first(e,v); G.valid(e); G.next(e)) {
     181            if ( capacity[e] == flow[e] ) continue;
     182            Node w=G.tail(e);
     183            if ( level[w] == n && w != s ) {
     184              bfs_queue.push(w);
     185              Node first=level_list[l];
     186              if ( G.valid(first) ) left.set(first,w);
     187              right.set(w,first);
     188              level_list[l]=w;
     189              level.set(w, l);
     190            }
     191          }
     192           
     193          OutEdgeIt f;
     194          for(G.first(f,v); G.valid(f); G.next(f)) {
     195            if ( 0 == flow[f] ) continue;
     196            Node w=G.head(f);
     197            if ( level[w] == n && w != s ) {
     198              bfs_queue.push(w);
     199              Node first=level_list[l];
     200              if ( G.valid(first) ) left.set(first,w);
     201              right.set(w,first);
     202              level_list[l]=w;
     203              level.set(w, l);
     204            }
     205          }
     206        }
     207     
     208       
     209        /*
     210          Counting the excess
     211        */
     212        NodeIt v;
     213        for(G.first(v); G.valid(v); G.next(v)) {
     214          T exc=0;
     215
     216          InEdgeIt e;
     217          for(G.first(e,v); G.valid(e); G.next(e)) exc+=flow[e];
     218          OutEdgeIt f;
     219          for(G.first(f,v); G.valid(f); G.next(f)) exc-=flow[e];
     220
     221          excess.set(v,exc);     
     222
     223          //putting the active nodes into the stack
     224          int lev=level[v];
     225          if ( exc > 0 && lev < n ) {
     226            next.set(v,active[lev]);
     227            active[lev]=v;
     228          }
     229        }
     230
     231
     232        //the starting flow
     233        OutEdgeIt e;
     234        for(G.first(e,s); G.valid(e); G.next(e))
     235        {
     236          T rem=capacity[e]-flow[e];
     237          if ( rem == 0 ) continue;
     238          Node w=G.head(e);
     239          if ( level[w] < n ) {   
     240            if ( excess[w] == 0 && w!=t ) {
     241              next.set(w,active[level[w]]);
     242              active[level[w]]=w;
     243            }
     244            flow.set(e, capacity[e]);
     245            excess.set(w, excess[w]+rem);
     246          }
     247        }
     248       
     249        InEdgeIt f;
     250        for(G.first(f,s); G.valid(f); G.next(f))
     251        {
     252          if ( flow[f] == 0 ) continue;
     253          Node w=G.head(f);
     254          if ( level[w] < n ) {   
     255            if ( excess[w] == 0 && w!=t ) {
     256              next.set(w,active[level[w]]);
     257              active[level[w]]=w;
     258            }
     259            excess.set(w, excess[w]+flow[f]);
     260            flow.set(f, 0);
     261          }
     262        }
     263      }
     264
     265
     266
    148267
    149268      /*
     
    339458            //unlacing ends
    340459               
    341             //gapping starts
    342460            if ( !G.valid(level_list[lev]) ) {
    343461             
     462               //gapping starts
    344463              for (int i=lev; i!=k ; ) {
    345464                Node v=level_list[++i];
     
    356475              k=b;
    357476              //gapping ends
     477           
    358478            } else {
    359479             
     
    364484                active[newlevel]=w;
    365485                if ( what_heur ) b=newlevel;
    366                 if ( k < newlevel ) ++k;
     486                if ( k < newlevel ) ++k;      //now k=newlevel
    367487                Node first=level_list[newlevel];
    368488                if ( G.valid(first) ) left.set(first,w);
     
    519639    }
    520640
     641   
     642    void reset_target (Node _t) {t=_t;}
     643    void reset_source (Node _s) {s=_s;}
     644   
     645    template<typename _CapMap>   
     646    void reset_cap (_CapMap _cap) {capacity=_cap;}
     647
     648    template<typename _FlowMap>   
     649    void reset_cap (_FlowMap _flow, bool _constzero) {
     650      flow=_flow;
     651      constzero=_constzero;
     652    }
     653
     654
    521655
    522656  };
Note: See TracChangeset for help on using the changeset viewer.