COIN-OR::LEMON - Graph Library

Changeset 211:9222a9b8b323 in lemon-0.x for src/work/jacint/preflow.h


Ignore:
Timestamp:
03/19/04 23:16:05 (18 years ago)
Author:
jacint
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@306
Message:

updating

File:
1 edited

Legend:

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

    r174 r211  
    11// -*- C++ -*-
    22/*
    3 preflow.h
    4 by jacint.
    53Heuristics:
    64 2 phase
     
    1311Parameters H0 and H1 are initialized to 20 and 10.
    1412
    15 The best preflow I could ever write.
    16 
    17 The constructor runs the algorithm.
     13Constructors:
     14
     15Preflow(Graph, Node, Node, CapMap, FlowMap)
    1816
    1917Members:
    2018
    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 Flow() : returns the fixed maximum flow x
     19void run()
     20
     21T flowValue() : returns the value of a maximum flow
    2622
    2723void minMinCut(CutMap& M) : sets M to the characteristic vector of the
     
    3632*/
    3733
    38 #ifndef PREFLOW_H
    39 #define PREFLOW_H
     34#ifndef HUGO_PREFLOW_H
     35#define HUGO_PREFLOW_H
    4036
    4137#define H0 20
     
    4440#include <vector>
    4541#include <queue>
    46 
    47 #include <time_measure.h>
    4842
    4943namespace hugo {
     
    5246    typename FlowMap=typename Graph::EdgeMap<T>,
    5347    typename CapMap=typename Graph::EdgeMap<T> >
    54   class preflow {
     48  class Preflow {
    5549   
     50    typedef typename Graph::Node Node;
     51    typedef typename Graph::Edge Edge;
    5652    typedef typename Graph::NodeIt NodeIt;
    57     typedef typename Graph::EdgeIt EdgeIt;
    58     typedef typename Graph::EachNodeIt EachNodeIt;
    5953    typedef typename Graph::OutEdgeIt OutEdgeIt;
    6054    typedef typename Graph::InEdgeIt InEdgeIt;
    6155   
    62     Graph& G;
    63     NodeIt s;
    64     NodeIt t;
    65     FlowMap flow;
    66     CapMap& capacity; 
     56    const Graph& G;
     57    Node s;
     58    Node t;
     59    FlowMap& flow;
     60    const CapMap& capacity; 
    6761    T value;
    6862
    6963  public:
    70     double time;
    71     preflow(Graph& _G, NodeIt _s, NodeIt _t, CapMap& _capacity ) :
    72       G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity)
    73     {
     64    Preflow(Graph& _G, Node _s, Node _t, CapMap& _capacity, FlowMap& _flow ) :
     65      G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) {}
     66
     67
     68    void run() {
    7469
    7570      bool phase=0;        //phase 0 is the 1st phase, phase 1 is the 2nd
     
    9590      typename Graph::NodeMap<T> excess(G);
    9691
    97       std::vector<NodeIt> active(n);
    98       typename Graph::NodeMap<NodeIt> next(G);
     92      std::vector<Node> active(n,INVALID);
     93      typename Graph::NodeMap<Node> next(G,INVALID);
    9994      //Stack of the active nodes in level i < n.
    10095      //We use it in both phases.
    10196
    102       typename Graph::NodeMap<NodeIt> left(G);
    103       typename Graph::NodeMap<NodeIt> right(G);
    104       std::vector<NodeIt> level_list(n);
     97      typename Graph::NodeMap<Node> left(G,INVALID);
     98      typename Graph::NodeMap<Node> right(G,INVALID);
     99      std::vector<Node> level_list(n,INVALID);
    105100      /*
    106101        List of the nodes in level i<n.
     
    109104      /*Reverse_bfs from t, to find the starting level.*/
    110105      level.set(t,0);
    111       std::queue<NodeIt> bfs_queue;
     106      std::queue<Node> bfs_queue;
    112107      bfs_queue.push(t);
    113108
    114109      while (!bfs_queue.empty()) {
    115110
    116         NodeIt v=bfs_queue.front();     
     111        Node v=bfs_queue.front();       
    117112        bfs_queue.pop();
    118         int l=level.get(v)+1;
    119 
    120         for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) {
    121           NodeIt w=G.tail(e);
    122           if ( level.get(w) == n && w != s ) {
     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 ) {
    123119            bfs_queue.push(w);
    124             NodeIt first=level_list[l];
    125             if ( first != 0 ) left.set(first,w);
     120            Node first=level_list[l];
     121            if ( G.valid(first) ) left.set(first,w);
    126122            right.set(w,first);
    127123            level_list[l]=w;
     
    135131
    136132      /* Starting flow. It is everywhere 0 at the moment. */     
    137       for(OutEdgeIt e=G.template first<OutEdgeIt>(s); e.valid(); ++e)
     133      OutEdgeIt e;
     134      for(G.first(e,s); G.valid(e); G.next(e))
    138135        {
    139           T c=capacity.get(e);
     136          T c=capacity[e];
    140137          if ( c == 0 ) continue;
    141           NodeIt w=G.head(e);
    142           if ( level.get(w) < n ) {       
    143             if ( excess.get(w) == 0 && w!=t ) {
    144               next.set(w,active[level.get(w)]);
    145               active[level.get(w)]=w;
     138          Node w=G.head(e);
     139          if ( level[w] < n ) {   
     140            if ( excess[w] == 0 && w!=t ) {
     141              next.set(w,active[level[w]]);
     142              active[level[w]]=w;
    146143            }
    147144            flow.set(e, c);
    148             excess.set(w, excess.get(w)+c);
     145            excess.set(w, excess[w]+c);
    149146          }
    150147        }
     
    169166          } else {
    170167            phase=1;
    171             time=currTime();
    172168            level.set(s,0);
    173             std::queue<NodeIt> bfs_queue;
     169            std::queue<Node> bfs_queue;
    174170            bfs_queue.push(s);
    175171           
    176172            while (!bfs_queue.empty()) {
    177173             
    178               NodeIt v=bfs_queue.front();       
     174              Node v=bfs_queue.front();
    179175              bfs_queue.pop();
    180               int l=level.get(v)+1;
    181              
    182               for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) {
    183                 if ( capacity.get(e) == flow.get(e) ) continue;
    184                 NodeIt u=G.tail(e);
    185                 if ( level.get(u) >= n ) {
     176              int l=level[v]+1;
     177             
     178              InEdgeIt e;
     179              for(G.first(e,v); G.valid(e); G.next(e)) {
     180                if ( capacity[e] == flow[e] ) continue;
     181                Node u=G.tail(e);
     182                if ( level[u] >= n ) {
    186183                  bfs_queue.push(u);
    187184                  level.set(u, l);
    188                   if ( excess.get(u) > 0 ) {
     185                  if ( excess[u] > 0 ) {
    189186                    next.set(u,active[l]);
    190187                    active[l]=u;
     
    193190              }
    194191           
    195               for(OutEdgeIt e=G.template first<OutEdgeIt>(v); e.valid(); ++e) {
    196                 if ( 0 == flow.get(e) ) continue;
    197                 NodeIt u=G.head(e);
    198                 if ( level.get(u) >= n ) {
     192              OutEdgeIt f;
     193              for(G.first(f,v); G.valid(f); G.next(f)) {
     194                if ( 0 == flow[f] ) continue;
     195                Node u=G.head(f);
     196                if ( level[u] >= n ) {
    199197                  bfs_queue.push(u);
    200198                  level.set(u, l);
    201                   if ( excess.get(u) > 0 ) {
     199                  if ( excess[u] > 0 ) {
    202200                    next.set(u,active[l]);
    203201                    active[l]=u;
     
    212210         
    213211         
    214         if ( active[b] == 0 ) --b;
     212        if ( !G.valid(active[b]) ) --b;
    215213        else {
    216214          end=false; 
    217215
    218           NodeIt w=active[b];
    219           active[b]=next.get(w);
    220           int lev=level.get(w);
    221           T exc=excess.get(w);
     216          Node w=active[b];
     217          active[b]=next[w];
     218          int lev=level[w];
     219          T exc=excess[w];
    222220          int newlevel=n;       //bound on the next level of w
    223221         
    224           for(OutEdgeIt e=G.template first<OutEdgeIt>(w); e.valid(); ++e) {
    225            
    226             if ( flow.get(e) == capacity.get(e) ) continue;
    227             NodeIt v=G.head(e);           
     222          OutEdgeIt e;
     223          for(G.first(e,w); G.valid(e); G.next(e)) {
     224           
     225            if ( flow[e] == capacity[e] ) continue;
     226            Node v=G.head(e);           
    228227            //e=wv         
    229228           
    230             if( lev > level.get(v) ) {     
     229            if( lev > level[v] ) {     
    231230              /*Push is allowed now*/
    232231             
    233               if ( excess.get(v)==0 && v!=t && v!=s ) {
    234                 int lev_v=level.get(v);
     232              if ( excess[v]==0 && v!=t && v!=s ) {
     233                int lev_v=level[v];
    235234                next.set(v,active[lev_v]);
    236235                active[lev_v]=v;
    237236              }
    238237             
    239               T cap=capacity.get(e);
    240               T flo=flow.get(e);
     238              T cap=capacity[e];
     239              T flo=flow[e];
    241240              T remcap=cap-flo;
    242241             
     
    245244               
    246245                flow.set(e, flo+exc);
    247                 excess.set(v, excess.get(v)+exc);
     246                excess.set(v, excess[v]+exc);
    248247                exc=0;
    249248                break;
     
    253252               
    254253                flow.set(e, cap);
    255                 excess.set(v, excess.get(v)+remcap);
     254                excess.set(v, excess[v]+remcap);
    256255                exc-=remcap;
    257256              }
    258             } else if ( newlevel > level.get(v) ){
    259               newlevel = level.get(v);
     257            } else if ( newlevel > level[v] ){
     258              newlevel = level[v];
    260259            }       
    261260           
     
    264263       
    265264        if ( exc > 0 ) {       
    266           for( InEdgeIt e=G.template first<InEdgeIt>(w); e.valid(); ++e) {
    267            
    268             if( flow.get(e) == 0 ) continue;
    269             NodeIt v=G.tail(e); 
     265          InEdgeIt e;
     266          for(G.first(e,w); G.valid(e); G.next(e)) {
     267           
     268            if( flow[e] == 0 ) continue;
     269            Node v=G.tail(e); 
    270270            //e=vw
    271271           
    272             if( lev > level.get(v) ) { 
     272            if( lev > level[v] ) { 
    273273              /*Push is allowed now*/
    274274             
    275               if ( excess.get(v)==0 && v!=t && v!=s ) {
    276                 int lev_v=level.get(v);
     275              if ( excess[v]==0 && v!=t && v!=s ) {
     276                int lev_v=level[v];
    277277                next.set(v,active[lev_v]);
    278278                active[lev_v]=v;
    279279              }
    280280             
    281               T flo=flow.get(e);
     281              T flo=flow[e];
    282282             
    283283              if ( flo >= exc ) {
     
    285285               
    286286                flow.set(e, flo-exc);
    287                 excess.set(v, excess.get(v)+exc);
     287                excess.set(v, excess[v]+exc);
    288288                exc=0;
    289289                break;
     
    291291                /*A saturating push.*/
    292292               
    293                 excess.set(v, excess.get(v)+flo);
     293                excess.set(v, excess[v]+flo);
    294294                exc-=flo;
    295295                flow.set(e,0);
    296296              } 
    297             } else if ( newlevel > level.get(v) ) {
    298               newlevel = level.get(v);
     297            } else if ( newlevel > level[v] ) {
     298              newlevel = level[v];
    299299            }       
    300300          } //for in edges vw
     
    319319          } else {
    320320            //unlacing starts
    321             NodeIt right_n=right.get(w);
    322             NodeIt left_n=left.get(w);
    323 
    324             if ( right_n != 0 ) {
    325               if ( left_n != 0 ) {
     321            Node right_n=right[w];
     322            Node left_n=left[w];
     323
     324            if ( G.valid(right_n) ) {
     325              if ( G.valid(left_n) ) {
    326326                right.set(left_n, right_n);
    327327                left.set(right_n, left_n);
    328328              } else {
    329329                level_list[lev]=right_n;   
    330                 left.set(right_n, 0);
     330                left.set(right_n, INVALID);
    331331              }
    332332            } else {
    333               if ( left_n != 0 ) {
    334                 right.set(left_n, 0);
     333              if ( G.valid(left_n) ) {
     334                right.set(left_n, INVALID);
    335335              } else {
    336                 level_list[lev]=0;   
    337 
     336                level_list[lev]=INVALID;   
    338337              }
    339338            }
     
    341340               
    342341            //gapping starts
    343             if ( level_list[lev]==0 ) {
     342            if ( !G.valid(level_list[lev]) ) {
    344343             
    345344              for (int i=lev; i!=k ; ) {
    346                 NodeIt v=level_list[++i];
    347                 while ( v != 0 ) {
     345                Node v=level_list[++i];
     346                while ( G.valid(v) ) {
    348347                  level.set(v,n);
    349                   v=right.get(v);
     348                  v=right[v];
    350349                }
    351                 level_list[i]=0;
    352                 if ( !what_heur ) active[i]=0;
     350                level_list[i]=INVALID;
     351                if ( !what_heur ) active[i]=INVALID;
    353352              }     
    354353
     
    366365                if ( what_heur ) b=newlevel;
    367366                if ( k < newlevel ) ++k;
    368                 NodeIt first=level_list[newlevel];
    369                 if ( first != 0 ) left.set(first,w);
     367                Node first=level_list[newlevel];
     368                if ( G.valid(first) ) left.set(first,w);
    370369                right.set(w,first);
    371                 left.set(w,0);
     370                left.set(w,INVALID);
    372371                level_list[newlevel]=w;
    373372              }
     
    399398
    400399
    401       value = excess.get(t);
     400      value = excess[t];
    402401      /*Max flow value.*/
    403402     
     
    412411     */
    413412
    414     T maxFlow() {
     413    T flowValue() {
    415414      return value;
    416415    }
    417 
    418 
    419 
    420     /*
    421       For the maximum flow x found by the algorithm,
    422       it returns the flow value on edge e, i.e. x(e).
    423     */
    424    
    425     T flowOnEdge(EdgeIt e) {
    426       return flow.get(e);
    427     }
    428 
    429416
    430417
     
    436423   
    437424    void Flow(FlowMap& _flow ) {
    438       for(EachNodeIt v=G.template first<EachNodeIt>() ; v.valid(); ++v)
    439         _flow.set(v,flow.get(v));
    440         }
     425      NodeIt v;
     426      for(G.first(v) ; G.valid(v); G.next(v))
     427        _flow.set(v,flow[v]);
     428    }
    441429
    442430
     
    449437    void minMinCut(_CutMap& M) {
    450438   
    451       std::queue<NodeIt> queue;
     439      std::queue<Node> queue;
    452440     
    453441      M.set(s,true);     
     
    455443
    456444      while (!queue.empty()) {
    457         NodeIt w=queue.front();
     445        Node w=queue.front();
    458446        queue.pop();
    459447
    460         for(OutEdgeIt e=G.template first<OutEdgeIt>(w) ; e.valid(); ++e) {
    461           NodeIt v=G.head(e);
    462           if (!M.get(v) && flow.get(e) < capacity.get(e) ) {
     448        OutEdgeIt e;
     449        for(G.first(e,w) ; G.valid(e); G.next(e)) {
     450          Node v=G.head(e);
     451          if (!M[v] && flow[e] < capacity[e] ) {
    463452            queue.push(v);
    464453            M.set(v, true);
     
    466455        }
    467456
    468         for(InEdgeIt e=G.template first<InEdgeIt>(w) ; e.valid(); ++e) {
    469           NodeIt v=G.tail(e);
    470           if (!M.get(v) && flow.get(e) > 0 ) {
     457        InEdgeIt f;
     458        for(G.first(f,w) ; G.valid(f); G.next(f)) {
     459          Node v=G.tail(f);
     460          if (!M[v] && flow[f] > 0 ) {
    471461            queue.push(v);
    472462            M.set(v, true);
     
    486476    void maxMinCut(_CutMap& M) {
    487477   
    488       std::queue<NodeIt> queue;
     478      std::queue<Node> queue;
    489479     
    490480      M.set(t,true);       
     
    492482
    493483      while (!queue.empty()) {
    494         NodeIt w=queue.front();
     484        Node w=queue.front();
    495485        queue.pop();
    496486
    497         for(InEdgeIt e=G.template first<InEdgeIt>(w) ; e.valid(); ++e) {
    498           NodeIt v=G.tail(e);
    499           if (!M.get(v) && flow.get(e) < capacity.get(e) ) {
     487
     488        InEdgeIt e;
     489        for(G.first(e,w) ; G.valid(e); G.next(e)) {
     490          Node v=G.tail(e);
     491          if (!M[v] && flow[e] < capacity[e] ) {
    500492            queue.push(v);
    501493            M.set(v, true);
    502494          }
    503495        }
    504 
    505         for(OutEdgeIt e=G.template first<OutEdgeIt>(w) ; e.valid(); ++e) {
    506           NodeIt v=G.head(e);
    507           if (!M.get(v) && flow.get(e) > 0 ) {
     496       
     497        OutEdgeIt f;
     498        for(G.first(f,w) ; G.valid(f); G.next(f)) {
     499          Node v=G.head(f);
     500          if (!M[v] && flow[f] > 0 ) {
    508501            queue.push(v);
    509502            M.set(v, true);
     
    512505      }
    513506
    514       for(EachNodeIt v=G.template first<EachNodeIt>() ; v.valid(); ++v) {
    515         M.set(v, !M.get(v));
     507      NodeIt v;
     508      for(G.first(v) ; G.valid(v); G.next(v)) {
     509        M.set(v, !M[v]);
    516510      }
    517511
Note: See TracChangeset for help on using the changeset viewer.