COIN-OR::LEMON - Graph Library

Changeset 615:b6b31b75b522 in lemon-0.x


Ignore:
Timestamp:
05/11/04 21:50:21 (20 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@800
Message:

docs, max_flow improvments

Location:
src/work
Files:
1 added
6 edited

Legend:

Unmodified
Added
Removed
  • src/work/Doxyfile

    r613 r615  
    395395                         ../hugo/skeletons \
    396396                         ../test/test_tools.h \
    397                          athos/minlengthpaths.h \
    398397                         klao/path.h \
    399398                         jacint/max_flow.h \
  • src/work/jacint/max_flow.h

    r602 r615  
    22
    33/*
    4   Heuristics: 
     4  Heuristics:
    55  2 phase
    66  gap
     
    99  runs heuristic 'highest label' for H1*n relabels
    1010  runs heuristic 'bound decrease' for H0*n relabels, starts with 'highest label'
    11  
     11
    1212  Parameters H0 and H1 are initialized to 20 and 1.
    1313
    1414  Constructors:
    1515
    16   Preflow(Graph, Node, Node, CapMap, FlowMap, bool) : bool must be false if 
     16  Preflow(Graph, Node, Node, CapMap, FlowMap, bool) : bool must be false if
    1717  FlowMap is not constant zero, and should be true if it is
    1818
     
    2323  Num flowValue() : returns the value of a maximum flow
    2424
    25   void minMinCut(CutMap& M) : sets M to the characteristic vector of the 
     25  void minMinCut(CutMap& M) : sets M to the characteristic vector of the
    2626  minimum min cut. M should be a map of bools initialized to false. ??Is it OK?
    2727
    28   void maxMinCut(CutMap& M) : sets M to the characteristic vector of the 
     28  void maxMinCut(CutMap& M) : sets M to the characteristic vector of the
    2929  maximum min cut. M should be a map of bools initialized to false.
    3030
    31   void minCut(CutMap& M) : sets M to the characteristic vector of 
     31  void minCut(CutMap& M) : sets M to the characteristic vector of
    3232  a min cut. M should be a map of bools initialized to false.
    3333
     
    3636#ifndef HUGO_MAX_FLOW_H
    3737#define HUGO_MAX_FLOW_H
    38 
    39 #define H0 20
    40 #define H1 1
    4138
    4239#include <vector>
     
    5148
    5249/// \file
    53 /// \brief Dimacs file format reader.
     50/// \brief Maximum flows.
     51/// \ingroup galgs
    5452
    5553namespace hugo {
     
    5856  //  ///\author Marton Makai, Jacint Szabo
    5957  /// A class for computing max flows and related quantities.
    60   template <typename Graph, typename Num,
    61             typename CapMap=typename Graph::template EdgeMap<Num>,
     58  /// \ingroup galgs
     59  template <typename Graph, typename Num,
     60            typename CapMap=typename Graph::template EdgeMap<Num>,
    6261            typename FlowMap=typename Graph::template EdgeMap<Num> >
    6362  class MaxFlow {
    64    
     63  protected:
    6564    typedef typename Graph::Node Node;
    6665    typedef typename Graph::NodeIt NodeIt;
     
    7574    Node s;
    7675    Node t;
    77     const CapMap* capacity; 
     76    const CapMap* capacity;
    7877    FlowMap* flow;
    7978    int n;      //the number of nodes of G
     
    8483    typedef typename Graph::template NodeMap<int> ReachedMap;
    8584    ReachedMap level;
    86     //level works as a bool map in augmenting path algorithms 
     85    //level works as a bool map in augmenting path algorithms
    8786    //and is used by bfs for storing reached information.
    8887    //In preflow, it shows levels of nodes.
    89     //typename Graph::template NodeMap<int> level;   
    90     typename Graph::template NodeMap<Num> excess; 
     88    //typename Graph::template NodeMap<int> level;
     89    typename Graph::template NodeMap<Num> excess;
    9190    //   protected:
    9291    //     MaxFlow() { }
    93     //     void set(const Graph& _G, Node _s, Node _t, const CapMap& _capacity, 
    94     //       FlowMap& _flow) 
     92    //     void set(const Graph& _G, Node _s, Node _t, const CapMap& _capacity,
     93    //       FlowMap& _flow)
    9594    //       {
    96     //  g=&_G; 
    97     //  s=_s; 
    98     //  t=_t; 
     95    //  g=&_G;
     96    //  s=_s;
     97    //  t=_t;
    9998    //  capacity=&_capacity;
    10099    //  flow=&_flow;
    101100    //  n=_G.nodeNum;
    102     //  level.set (_G); //kellene vmi ilyesmi fv 
     101    //  level.set (_G); //kellene vmi ilyesmi fv
    103102    //  excess(_G,0); //itt is
    104103    //       }
    105104
     105    // constants used for heuristics
     106    static const int H0=20;
     107    static const int H1=1;
     108
    106109  public:
    107  
     110
    108111    ///\todo Document this.
    109112    ///\todo Maybe, it should be PRE_FLOW instead.
     113    ///- \c NO_FLOW means nothing,
    110114    ///- \c ZERO_FLOW means something,
    111115    ///- \c GEN_FLOW means something else,
    112     ///- \c PREFLOW is something different.
     116    ///- \c PRE_FLOW is something different.
    113117    enum flowEnum{
    114       ZERO_FLOW=0,
    115       GEN_FLOW=1,
    116       PREFLOW=2
     118      ZERO_FLOW,
     119      GEN_FLOW,
     120      PRE_FLOW,
     121      NO_FLOW
    117122    };
    118123
    119     MaxFlow(const Graph& _G, Node _s, Node _t, const CapMap& _capacity, 
     124    MaxFlow(const Graph& _G, Node _s, Node _t, const CapMap& _capacity,
    120125            FlowMap& _flow) :
    121       g(&_G), s(_s), t(_t), capacity(&_capacity), 
     126      g(&_G), s(_s), t(_t), capacity(&_capacity),
    122127      flow(&_flow), n(_G.nodeNum()), level(_G), excess(_G,0) {}
    123128
    124129    /// A max flow algorithm is run.
    125     ///\pre the flow have to be 0 at the beginning.
    126     void run() {
    127       preflow(ZERO_FLOW);
    128     }
    129    
    130     /// A preflow algorithm is run.
    131     ///\pre The initial edge-map have to be a
     130    /// \pre The flow have to satisfy the requirements
     131    /// stated in fe.
     132    void run(flowEnum fe=ZERO_FLOW) {
     133      preflow(fe);
     134    }
     135
     136    /// A preflow algorithm is run.
     137    /// \pre The initial edge-map have to be a
    132138    /// zero flow if \c fe is \c ZERO_FLOW,
    133     /// a flow if \c fe is \c GEN_FLOW,
    134     /// and a pre-flow it is \c PREFLOW.
     139    /// a flow if \c fe is \c GEN_FLOW,
     140    /// a pre-flow if fe is \c PRE_FLOW and
     141    /// anything if fe is NO_FLOW.
    135142    void preflow(flowEnum fe) {
    136143      preflowPhase0(fe);
     
    138145    }
    139146
    140     /// Run the first phase of preflow, starting from a 0 flow, from a flow, 
    141     /// or from a preflow, according to \c fe.
    142     void preflowPhase0( flowEnum fe );
     147    /// Run the first phase of preflow, starting from a 0 flow, from a flow,
     148    /// or from a preflow, of from undefined value according to \c fe.
     149    void preflowPhase0(flowEnum fe);
    143150
    144151    /// Second phase of preflow.
    145152    void preflowPhase1();
    146153
    147     /// Starting from a flow, this method searches for an augmenting path 
    148     /// according to the Edmonds-Karp algorithm 
    149     /// and augments the flow on if any. 
     154    /// Starting from a flow, this method searches for an augmenting path
     155    /// according to the Edmonds-Karp algorithm
     156    /// and augments the flow on if any.
    150157    /// The return value shows if the augmentation was succesful.
    151158    bool augmentOnShortestPath();
    152159
    153     /// Starting from a flow, this method searches for an augmenting blockin 
    154     /// flow according to Dinits' algorithm and augments the flow on if any. 
    155     /// The blocking flow is computed in a physically constructed 
     160    /// Starting from a flow, this method searches for an augmenting blocking
     161    /// flow according to Dinits' algorithm and augments the flow on if any.
     162    /// The blocking flow is computed in a physically constructed
    156163    /// residual graph of type \c Mutablegraph.
    157164    /// The return value show sif the augmentation was succesful.
    158165    template<typename MutableGraph> bool augmentOnBlockingFlow();
    159166
    160     /// The same as \c augmentOnBlockingFlow<MutableGraph> but the 
     167    /// The same as \c augmentOnBlockingFlow<MutableGraph> but the
    161168    /// residual graph is not constructed physically.
    162169    /// The return value shows if the augmentation was succesful.
     
    164171
    165172    /// Returns the actual flow value.
    166     /// More precisely, it returns the negative excess of s, thus 
     173    /// More precisely, it returns the negative excess of s, thus
    167174    /// this works also for preflows.
    168     Num flowValue() { 
     175    Num flowValue() {
    169176      Num a=0;
    170       FOR_EACH_INC_LOC(OutEdgeIt, e, *g, s) a+=(*flow)[e];
    171       FOR_EACH_INC_LOC(InEdgeIt, e, *g, s) a-=(*flow)[e];
     177      FOR_EACH_INC_LOC(InEdgeIt, e, *g, t) a+=(*flow)[e];
     178      FOR_EACH_INC_LOC(OutEdgeIt, e, *g, t) a-=(*flow)[e];
    172179      return a;
    173180    }
    174181
    175182    /// Should be used between preflowPhase0 and preflowPhase1.
    176     ///\todo We have to make some status variable which shows the actual state
    177     /// of the class. This enables us to determine which methods are valid
     183    /// \todo We have to make some status variable which shows the
     184    /// actual state
     185    /// of the class. This enables us to determine which methods are valid
    178186    /// for MinCut computation
    179187    template<typename _CutMap>
     
    189197    }
    190198
    191     /// The unique inclusionwise minimum cut is computed by 
     199    /// The unique inclusionwise minimum cut is computed by
    192200    /// processing a bfs from s in the residual graph.
    193     ///\pre flow have to be a max flow otherwise it will the whole node-set.
     201    /// \pre flow have to be a max flow otherwise it will the whole node-set.
    194202    template<typename _CutMap>
    195203    void minMinCut(_CutMap& M) {
    196    
     204
    197205      std::queue<Node> queue;
    198      
    199       M.set(s,true);     
     206
     207      M.set(s,true);
    200208      queue.push(s);
    201209
     
    211219            M.set(v, true);
    212220          }
    213         } 
     221        }
    214222
    215223        InEdgeIt f;
     
    220228            M.set(v, true);
    221229          }
    222         } 
    223       }
    224     }
    225 
    226 
    227     /// The unique inclusionwise maximum cut is computed by 
     230        }
     231      }
     232    }
     233
     234
     235    /// The unique inclusionwise maximum cut is computed by
    228236    /// processing a reverse bfs from t in the residual graph.
    229     ///\pre flow have to be a max flow otherwise it will be empty.
     237    /// \pre flow have to be a max flow otherwise it will be empty.
    230238    template<typename _CutMap>
    231239    void maxMinCut(_CutMap& M) {
     
    237245
    238246      std::queue<Node> queue;
    239      
    240       M.set(t,false);       
     247
     248      M.set(t,false);
    241249      queue.push(t);
    242250
     
    244252        Node w=queue.front();
    245253        queue.pop();
    246 
    247254
    248255        InEdgeIt e;
     
    254261          }
    255262        }
    256        
     263
    257264        OutEdgeIt f;
    258265        for(g->first(f,w) ; g->valid(f); g->next(f)) {
     
    275282    ///
    276283    void resetTarget(Node _t) { t=_t; }
    277    
     284
    278285    /// capacity-map is changed.
    279286    void resetCap(const CapMap& _cap) { capacity=&_cap; }
    280    
    281     /// flow-map is changed. 
     287
     288    /// flow-map is changed.
    282289    void resetFlow(FlowMap& _flow) { flow=&_flow; }
    283290
     
    286293
    287294    int push(Node w, VecStack& active) {
    288      
     295
    289296      int lev=level[w];
    290297      Num exc=excess[w];
    291298      int newlevel=n;       //bound on the next level of w
    292          
     299
    293300      OutEdgeIt e;
    294301      for(g->first(e,w); g->valid(e); g->next(e)) {
    295            
    296         if ( (*flow)[e] >= (*capacity)[e] ) continue; 
    297         Node v=g->head(e);           
    298            
     302
     303        if ( (*flow)[e] >= (*capacity)[e] ) continue;
     304        Node v=g->head(e);
     305
    299306        if( lev > level[v] ) { //Push is allowed now
    300          
     307
    301308          if ( excess[v]<=0 && v!=t && v!=s ) {
    302309            int lev_v=level[v];
    303310            active[lev_v].push(v);
    304311          }
    305          
     312
    306313          Num cap=(*capacity)[e];
    307314          Num flo=(*flow)[e];
    308315          Num remcap=cap-flo;
    309          
     316
    310317          if ( remcap >= exc ) { //A nonsaturating push.
    311            
     318
    312319            flow->set(e, flo+exc);
    313320            excess.set(v, excess[v]+exc);
    314321            exc=0;
    315             break; 
    316            
     322            break;
     323
    317324          } else { //A saturating push.
    318325            flow->set(e, cap);
     
    321328          }
    322329        } else if ( newlevel > level[v] ) newlevel = level[v];
    323       } //for out edges wv 
    324      
    325       if ( exc > 0 ) { 
     330      } //for out edges wv
     331
     332      if ( exc > 0 ) {
    326333        InEdgeIt e;
    327334        for(g->first(e,w); g->valid(e); g->next(e)) {
    328          
    329           if( (*flow)[e] <= 0 ) continue; 
    330           Node v=g->tail(e); 
    331          
     335
     336          if( (*flow)[e] <= 0 ) continue;
     337          Node v=g->tail(e);
     338
    332339          if( lev > level[v] ) { //Push is allowed now
    333            
     340
    334341            if ( excess[v]<=0 && v!=t && v!=s ) {
    335342              int lev_v=level[v];
    336343              active[lev_v].push(v);
    337344            }
    338            
     345
    339346            Num flo=(*flow)[e];
    340            
     347
    341348            if ( flo >= exc ) { //A nonsaturating push.
    342              
     349
    343350              flow->set(e, flo-exc);
    344351              excess.set(v, excess[v]+exc);
    345352              exc=0;
    346               break; 
     353              break;
    347354            } else {  //A saturating push.
    348              
     355
    349356              excess.set(v, excess[v]+flo);
    350357              exc-=flo;
    351358              flow->set(e,0);
    352             } 
     359            }
    353360          } else if ( newlevel > level[v] ) newlevel = level[v];
    354361        } //for in edges vw
    355        
     362
    356363      } // if w still has excess after the out edge for cycle
    357      
     364
    358365      excess.set(w, exc);
    359      
     366
    360367      return newlevel;
    361368    }
    362369
    363370
    364     void preflowPreproc ( flowEnum fe, VecStack& active,
    365                           VecNode& level_list, NNMap& left, NNMap& right )
     371    void preflowPreproc(flowEnum fe, VecStack& active,
     372                        VecNode& level_list, NNMap& left, NNMap& right)
    366373    {
    367 
    368374      std::queue<Node> bfs_queue;
    369      
    370       switch ( fe ) {
    371       case ZERO_FLOW: 
     375
     376      switch (fe) {
     377      case ZERO_FLOW:
    372378        {
    373379          //Reverse_bfs from t, to find the starting level.
    374380          level.set(t,0);
    375381          bfs_queue.push(t);
    376        
     382
    377383          while (!bfs_queue.empty()) {
    378            
    379             Node v=bfs_queue.front();   
     384
     385            Node v=bfs_queue.front();
    380386            bfs_queue.pop();
    381387            int l=level[v]+1;
    382            
     388
    383389            InEdgeIt e;
    384390            for(g->first(e,v); g->valid(e); g->next(e)) {
     
    394400            }
    395401          }
    396          
     402
    397403          //the starting flow
    398404          OutEdgeIt e;
    399           for(g->first(e,s); g->valid(e); g->next(e)) 
     405          for(g->first(e,s); g->valid(e); g->next(e))
    400406            {
    401407              Num c=(*capacity)[e];
    402408              if ( c <= 0 ) continue;
    403409              Node w=g->head(e);
    404               if ( level[w] < n ) {       
     410              if ( level[w] < n ) {
    405411                if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w);
    406                 flow->set(e, c); 
     412                flow->set(e, c);
    407413                excess.set(w, excess[w]+c);
    408414              }
     
    410416          break;
    411417        }
    412        
     418
    413419      case GEN_FLOW:
    414       case PREFLOW:
     420      case PRE_FLOW:
    415421        {
    416           //Reverse_bfs from t in the residual graph, 
     422          //Reverse_bfs from t in the residual graph,
    417423          //to find the starting level.
    418424          level.set(t,0);
    419425          bfs_queue.push(t);
    420          
     426
    421427          while (!bfs_queue.empty()) {
    422            
    423             Node v=bfs_queue.front();   
     428
     429            Node v=bfs_queue.front();
    424430            bfs_queue.pop();
    425431            int l=level[v]+1;
    426            
     432
    427433            InEdgeIt e;
    428434            for(g->first(e,v); g->valid(e); g->next(e)) {
     
    438444              }
    439445            }
    440            
     446
    441447            OutEdgeIt f;
    442448            for(g->first(f,v); g->valid(f); g->next(f)) {
     
    453459            }
    454460          }
    455          
    456          
     461
     462
    457463          //the starting flow
    458464          OutEdgeIt e;
    459           for(g->first(e,s); g->valid(e); g->next(e)) 
     465          for(g->first(e,s); g->valid(e); g->next(e))
    460466            {
    461467              Num rem=(*capacity)[e]-(*flow)[e];
    462468              if ( rem <= 0 ) continue;
    463469              Node w=g->head(e);
    464               if ( level[w] < n ) {       
     470              if ( level[w] < n ) {
    465471                if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w);
    466                 flow->set(e, (*capacity)[e]); 
     472                flow->set(e, (*capacity)[e]);
    467473                excess.set(w, excess[w]+rem);
    468474              }
    469475            }
    470          
     476
    471477          InEdgeIt f;
    472           for(g->first(f,s); g->valid(f); g->next(f)) 
     478          for(g->first(f,s); g->valid(f); g->next(f))
    473479            {
    474480              if ( (*flow)[f] <= 0 ) continue;
    475481              Node w=g->tail(f);
    476               if ( level[w] < n ) {       
     482              if ( level[w] < n ) {
    477483                if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w);
    478484                excess.set(w, excess[w]+(*flow)[f]);
    479                 flow->set(f, 0); 
     485                flow->set(f, 0);
    480486              }
    481             } 
     487            }
    482488          break;
    483         } //case PREFLOW
     489        } //case PRE_FLOW
    484490      }
    485491    } //preflowPreproc
     
    487493
    488494
    489     void relabel(Node w, int newlevel, VecStack& active, 
    490                  VecNode& level_list, NNMap& left, 
    491                  NNMap& right, int& b, int& k, bool what_heur ) 
     495    void relabel(Node w, int newlevel, VecStack& active,
     496                 VecNode& level_list, NNMap& left,
     497                 NNMap& right, int& b, int& k, bool what_heur )
    492498    {
    493499
    494       Num lev=level[w]; 
    495      
     500      Num lev=level[w];
     501
    496502      Node right_n=right[w];
    497503      Node left_n=left[w];
    498      
     504
    499505      //unlacing starts
    500506      if ( g->valid(right_n) ) {
     
    503509          left.set(right_n, left_n);
    504510        } else {
    505           level_list[lev]=right_n;   
     511          level_list[lev]=right_n;
    506512          left.set(right_n, INVALID);
    507         } 
     513        }
    508514      } else {
    509515        if ( g->valid(left_n) ) {
    510516          right.set(left_n, INVALID);
    511         } else { 
    512           level_list[lev]=INVALID;   
    513         } 
    514       } 
     517        } else {
     518          level_list[lev]=INVALID;
     519        }
     520      }
    515521      //unlacing ends
    516                
     522
    517523      if ( !g->valid(level_list[lev]) ) {
    518              
     524
    519525        //gapping starts
    520526        for (int i=lev; i!=k ; ) {
     
    529535              active[i].pop();    //FIXME: ezt szebben kene
    530536            }
    531           }         
    532         }
    533        
     537          }
     538        }
     539
    534540        level.set(w,n);
    535541        b=lev-1;
    536542        k=b;
    537543        //gapping ends
    538        
     544
    539545      } else {
    540        
    541         if ( newlevel == n ) level.set(w,n); 
     546
     547        if ( newlevel == n ) level.set(w,n);
    542548        else {
    543549          level.set(w,++newlevel);
     
    552558        }
    553559      }
    554      
     560
    555561    } //relabel
    556562
    557563
    558     template<typename MapGraphWrapper> 
     564    template<typename MapGraphWrapper>
    559565    class DistanceMap {
    560566    protected:
    561567      const MapGraphWrapper* g;
    562       typename MapGraphWrapper::template NodeMap<int> dist; 
     568      typename MapGraphWrapper::template NodeMap<int> dist;
    563569    public:
    564570      DistanceMap(MapGraphWrapper& _g) : g(&_g), dist(*g, g->nodeNum()) { }
    565       void set(const typename MapGraphWrapper::Node& n, int a) { 
    566         dist.set(n, a); 
    567       }
    568       int operator[](const typename MapGraphWrapper::Node& n) 
     571      void set(const typename MapGraphWrapper::Node& n, int a) {
     572        dist.set(n, a);
     573      }
     574      int operator[](const typename MapGraphWrapper::Node& n)
    569575      { return dist[n]; }
    570       //       int get(const typename MapGraphWrapper::Node& n) const { 
     576      //       int get(const typename MapGraphWrapper::Node& n) const {
    571577      //        return dist[n]; }
    572       //       bool get(const typename MapGraphWrapper::Edge& e) const { 
     578      //       bool get(const typename MapGraphWrapper::Edge& e) const {
    573579      //        return (dist.get(g->tail(e))<dist.get(g->head(e))); }
    574       bool operator[](const typename MapGraphWrapper::Edge& e) const { 
    575         return (dist[g->tail(e)]<dist[g->head(e)]); 
     580      bool operator[](const typename MapGraphWrapper::Edge& e) const {
     581        return (dist[g->tail(e)]<dist[g->head(e)]);
    576582      }
    577583    };
    578    
     584
    579585  };
    580586
    581587
    582588  template <typename Graph, typename Num, typename CapMap, typename FlowMap>
    583   void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase0( flowEnum fe ) 
     589  void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase0( flowEnum fe )
    584590  {
    585      
    586     int heur0=(int)(H0*n);  //time while running 'bound decrease' 
     591
     592    int heur0=(int)(H0*n);  //time while running 'bound decrease'
    587593    int heur1=(int)(H1*n);  //time while running 'highest label'
    588594    int heur=heur1;         //starting time interval (#of relabels)
    589595    int numrelabel=0;
    590      
    591     bool what_heur=1;       
     596
     597    bool what_heur=1;
    592598    //It is 0 in case 'bound decrease' and 1 in case 'highest label'
    593599
    594     bool end=false;     
    595     //Needed for 'bound decrease', true means no active nodes are above bound b.
     600    bool end=false;
     601    //Needed for 'bound decrease', true means no active nodes are above bound
     602    //b.
    596603
    597604    int k=n-2;  //bound on the highest level under n containing a node
    598605    int b=k;    //bound on the highest level under n of an active node
    599      
     606
    600607    VecStack active(n);
    601      
     608
    602609    NNMap left(*g, INVALID);
    603610    NNMap right(*g, INVALID);
     
    608615    for(g->first(v); g->valid(v); g->next(v)) level.set(v,n);
    609616    //setting each node to level n
    610      
    611     switch ( fe ) {
    612     case PREFLOW:
     617
     618    switch (fe) {
     619    case PRE_FLOW:
    613620      {
    614         //counting the excess
     621        //computing the excess
    615622        NodeIt v;
    616623        for(g->first(v); g->valid(v); g->next(v)) {
    617624          Num exc=0;
    618          
     625
    619626          InEdgeIt e;
    620627          for(g->first(e,v); g->valid(e); g->next(e)) exc+=(*flow)[e];
    621628          OutEdgeIt f;
    622629          for(g->first(f,v); g->valid(f); g->next(f)) exc-=(*flow)[f];
    623            
    624           excess.set(v,exc);     
    625            
     630
     631          excess.set(v,exc);
     632
    626633          //putting the active nodes into the stack
    627634          int lev=level[v];
     
    632639    case GEN_FLOW:
    633640      {
    634         //Counting the excess of t
     641        //computing the excess of t
    635642        Num exc=0;
    636          
     643
    637644        InEdgeIt e;
    638645        for(g->first(e,t); g->valid(e); g->next(e)) exc+=(*flow)[e];
    639646        OutEdgeIt f;
    640647        for(g->first(f,t); g->valid(f); g->next(f)) exc-=(*flow)[f];
    641          
    642         excess.set(t,exc);     
    643          
     648
     649        excess.set(t,exc);
     650
    644651        break;
    645652      }
    646     default:
    647       break;
    648     }
    649      
    650     preflowPreproc( fe, active, level_list, left, right );
    651     //End of preprocessing
    652      
    653      
     653    default:;
     654    }
     655
     656    preflowPreproc(fe, active, level_list, left, right);
     657    //End of preprocessing
     658
     659
    654660    //Push/relabel on the highest level active nodes.
    655661    while ( true ) {
     
    660666        } else break;
    661667      }
    662        
    663       if ( active[b].empty() ) --b; 
     668
     669      if ( active[b].empty() ) --b;
    664670      else {
    665         end=false; 
     671        end=false;
    666672        Node w=active[b].top();
    667673        active[b].pop();
    668674        int newlevel=push(w,active);
    669         if ( excess[w] > 0 ) relabel(w, newlevel, active, level_list, 
     675        if ( excess[w] > 0 ) relabel(w, newlevel, active, level_list,
    670676                                     left, right, b, k, what_heur);
    671          
    672         ++numrelabel; 
     677
     678        ++numrelabel;
    673679        if ( numrelabel >= heur ) {
    674680          numrelabel=0;
     
    680686            what_heur=1;
    681687            heur=heur1;
    682             b=k; 
    683           }
    684         }
    685       } 
    686     } 
     688            b=k;
     689          }
     690        }
     691      }
     692    }
    687693  }
    688694
     
    690696
    691697  template <typename Graph, typename Num, typename CapMap, typename FlowMap>
    692   void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase1() 
     698  void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase1()
    693699  {
    694      
     700
    695701    int k=n-2;  //bound on the highest level under n containing a node
    696702    int b=k;    //bound on the highest level under n of an active node
    697      
     703
    698704    VecStack active(n);
    699705    level.set(s,0);
    700706    std::queue<Node> bfs_queue;
    701707    bfs_queue.push(s);
    702            
     708
    703709    while (!bfs_queue.empty()) {
    704        
    705       Node v=bfs_queue.front(); 
     710
     711      Node v=bfs_queue.front();
    706712      bfs_queue.pop();
    707713      int l=level[v]+1;
    708              
     714
    709715      InEdgeIt e;
    710716      for(g->first(e,v); g->valid(e); g->next(e)) {
    711717        if ( (*capacity)[e] <= (*flow)[e] ) continue;
    712718        Node u=g->tail(e);
    713         if ( level[u] >= n ) { 
     719        if ( level[u] >= n ) {
    714720          bfs_queue.push(u);
    715721          level.set(u, l);
     
    717723        }
    718724      }
    719        
     725
    720726      OutEdgeIt f;
    721727      for(g->first(f,v); g->valid(f); g->next(f)) {
    722728        if ( 0 >= (*flow)[f] ) continue;
    723729        Node u=g->head(f);
    724         if ( level[u] >= n ) { 
     730        if ( level[u] >= n ) {
    725731          bfs_queue.push(u);
    726732          level.set(u, l);
     
    732738
    733739    while ( true ) {
    734        
     740
    735741      if ( b == 0 ) break;
    736742
    737       if ( active[b].empty() ) --b; 
     743      if ( active[b].empty() ) --b;
    738744      else {
    739745        Node w=active[b].top();
    740746        active[b].pop();
    741         int newlevel=push(w,active);     
     747        int newlevel=push(w,active);
    742748
    743749        //relabel
     
    754760
    755761  template <typename Graph, typename Num, typename CapMap, typename FlowMap>
    756   bool MaxFlow<Graph, Num, CapMap, FlowMap>::augmentOnShortestPath() 
     762  bool MaxFlow<Graph, Num, CapMap, FlowMap>::augmentOnShortestPath()
    757763  {
    758764    ResGW res_graph(*g, *capacity, *flow);
    759765    bool _augment=false;
    760      
     766
    761767    //ReachedMap level(res_graph);
    762768    FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
    763769    BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
    764770    bfs.pushAndSetReached(s);
    765        
    766     typename ResGW::template NodeMap<ResGWEdge> pred(res_graph); 
     771
     772    typename ResGW::template NodeMap<ResGWEdge> pred(res_graph);
    767773    pred.set(s, INVALID);
    768      
     774
    769775    typename ResGW::template NodeMap<Num> free(res_graph);
    770        
     776
    771777    //searching for augmenting path
    772     while ( !bfs.finished() ) { 
     778    while ( !bfs.finished() ) {
    773779      ResGWOutEdgeIt e=bfs;
    774780      if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
     
    779785          free.set(w, std::min(free[v], res_graph.resCap(e)));
    780786        } else {
    781           free.set(w, res_graph.resCap(e)); 
     787          free.set(w, res_graph.resCap(e));
    782788        }
    783789        if (res_graph.head(e)==t) { _augment=true; break; }
    784790      }
    785        
     791
    786792      ++bfs;
    787793    } //end of searching augmenting path
     
    790796      Node n=t;
    791797      Num augment_value=free[t];
    792       while (res_graph.valid(pred[n])) { 
     798      while (res_graph.valid(pred[n])) {
    793799        ResGWEdge e=pred[n];
    794         res_graph.augment(e, augment_value); 
     800        res_graph.augment(e, augment_value);
    795801        n=res_graph.tail(e);
    796802      }
     
    806812
    807813
    808 
    809 
    810814  template <typename Graph, typename Num, typename CapMap, typename FlowMap>
    811   template<typename MutableGraph> 
    812   bool MaxFlow<Graph, Num, CapMap, FlowMap>::augmentOnBlockingFlow() 
    813   {     
     815  template<typename MutableGraph>
     816  bool MaxFlow<Graph, Num, CapMap, FlowMap>::augmentOnBlockingFlow()
     817  {
    814818    typedef MutableGraph MG;
    815819    bool _augment=false;
     
    822826    BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
    823827    bfs.pushAndSetReached(s);
    824     typename ResGW::template NodeMap<int> 
     828    typename ResGW::template NodeMap<int>
    825829      dist(res_graph); //filled up with 0's
    826830
     
    828832    //with the set of edges which are on shortest paths
    829833    MG F;
    830     typename ResGW::template NodeMap<typename MG::Node> 
     834    typename ResGW::template NodeMap<typename MG::Node>
    831835      res_graph_to_F(res_graph);
    832836    {
     
    842846    typename MG::template EdgeMap<Num> residual_capacity(F);
    843847
    844     while ( !bfs.finished() ) { 
     848    while ( !bfs.finished() ) {
    845849      ResGWOutEdgeIt e=bfs;
    846850      if (res_graph.valid(e)) {
    847851        if (bfs.isBNodeNewlyReached()) {
    848852          dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
    849           typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]);
     853          typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)],
     854                                        res_graph_to_F[res_graph.head(e)]);
    850855          original_edge.update();
    851856          original_edge.set(f, e);
     
    854859        } else {
    855860          if (dist[res_graph.head(e)]==(dist[res_graph.tail(e)]+1)) {
    856             typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]);
     861            typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)],
     862                                          res_graph_to_F[res_graph.head(e)]);
    857863            original_edge.update();
    858864            original_edge.set(f, e);
     
    877883      typename MG::template NodeMap<Num> free(F);
    878884
    879       dfs.pushAndSetReached(sF);     
     885      dfs.pushAndSetReached(sF);
    880886      while (!dfs.finished()) {
    881887        ++dfs;
     
    888894              free.set(w, std::min(free[v], residual_capacity[dfs]));
    889895            } else {
    890               free.set(w, residual_capacity[dfs]); 
    891             }
    892             if (w==tF) { 
    893               __augment=true; 
     896              free.set(w, residual_capacity[dfs]);
     897            }
     898            if (w==tF) {
     899              __augment=true;
    894900              _augment=true;
    895               break; 
    896             }
    897              
     901              break;
     902            }
     903
    898904          } else {
    899905            F.erase(/*typename MG::OutEdgeIt*/(dfs));
    900906          }
    901         } 
     907        }
    902908      }
    903909
     
    905911        typename MG::Node n=tF;
    906912        Num augment_value=free[tF];
    907         while (F.valid(pred[n])) { 
     913        while (F.valid(pred[n])) {
    908914          typename MG::Edge e=pred[n];
    909           res_graph.augment(original_edge[e], augment_value); 
     915          res_graph.augment(original_edge[e], augment_value);
    910916          n=F.tail(e);
    911           if (residual_capacity[e]==augment_value) 
    912             F.erase(e); 
    913           else 
     917          if (residual_capacity[e]==augment_value)
     918            F.erase(e);
     919          else
    914920            residual_capacity.set(e, residual_capacity[e]-augment_value);
    915921        }
    916922      }
    917        
    918     }
    919            
     923
     924    }
     925
    920926    return _augment;
    921927  }
     
    924930
    925931
    926 
    927 
    928932  template <typename Graph, typename Num, typename CapMap, typename FlowMap>
    929   bool MaxFlow<Graph, Num, CapMap, FlowMap>::augmentOnBlockingFlow2() 
     933  bool MaxFlow<Graph, Num, CapMap, FlowMap>::augmentOnBlockingFlow2()
    930934  {
    931935    bool _augment=false;
    932936
    933937    ResGW res_graph(*g, *capacity, *flow);
    934      
     938
    935939    //ReachedMap level(res_graph);
    936940    FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
     
    939943    bfs.pushAndSetReached(s);
    940944    DistanceMap<ResGW> dist(res_graph);
    941     while ( !bfs.finished() ) { 
     945    while ( !bfs.finished() ) {
    942946      ResGWOutEdgeIt e=bfs;
    943947      if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
     
    949953      //Subgraph containing the edges on some shortest paths
    950954    ConstMap<typename ResGW::Node, bool> true_map(true);
    951     typedef SubGraphWrapper<ResGW, ConstMap<typename ResGW::Node, bool>, 
     955    typedef SubGraphWrapper<ResGW, ConstMap<typename ResGW::Node, bool>,
    952956      DistanceMap<ResGW> > FilterResGW;
    953957    FilterResGW filter_res_graph(res_graph, true_map, dist);
    954958
    955     //Subgraph, which is able to delete edges which are already 
     959    //Subgraph, which is able to delete edges which are already
    956960    //met by the dfs
    957     typename FilterResGW::template NodeMap<typename FilterResGW::OutEdgeIt> 
     961    typename FilterResGW::template NodeMap<typename FilterResGW::OutEdgeIt>
    958962      first_out_edges(filter_res_graph);
    959963    typename FilterResGW::NodeIt v;
    960     for(filter_res_graph.first(v); filter_res_graph.valid(v); 
    961         filter_res_graph.next(v)) 
     964    for(filter_res_graph.first(v); filter_res_graph.valid(v);
     965        filter_res_graph.next(v))
    962966      {
    963967        typename FilterResGW::OutEdgeIt e;
     
    975979      __augment=false;
    976980      //computing blocking flow with dfs
    977       DfsIterator< ErasingResGW, 
    978         typename ErasingResGW::template NodeMap<bool> > 
     981      DfsIterator< ErasingResGW,
     982        typename ErasingResGW::template NodeMap<bool> >
    979983        dfs(erasing_res_graph);
    980984      typename ErasingResGW::
    981         template NodeMap<typename ErasingResGW::OutEdgeIt> 
    982         pred(erasing_res_graph); 
     985        template NodeMap<typename ErasingResGW::OutEdgeIt>
     986        pred(erasing_res_graph);
    983987      pred.set(s, INVALID);
    984988      //invalid iterators for sources
    985989
    986       typename ErasingResGW::template NodeMap<Num> 
     990      typename ErasingResGW::template NodeMap<Num>
    987991        free1(erasing_res_graph);
    988992
    989       dfs.pushAndSetReached(
    990                             typename ErasingResGW::Node(
    991                                                         typename FilterResGW::Node(
    992                                                                                    typename ResGW::Node(s)
    993                                                                                    )
    994                                                         )
    995                             );
     993      dfs.pushAndSetReached
     994        ///\bug hugo 0.2
     995        (typename ErasingResGW::Node
     996         (typename FilterResGW::Node
     997          (typename ResGW::Node(s)
     998           )
     999          )
     1000         );
    9961001      while (!dfs.finished()) {
    9971002        ++dfs;
    998         if (erasing_res_graph.valid(
    999                                     typename ErasingResGW::OutEdgeIt(dfs)))
    1000           {
     1003        if (erasing_res_graph.valid(typename ErasingResGW::OutEdgeIt(dfs)))
     1004          {
    10011005            if (dfs.isBNodeNewlyReached()) {
    1002          
     1006
    10031007              typename ErasingResGW::Node v=erasing_res_graph.aNode(dfs);
    10041008              typename ErasingResGW::Node w=erasing_res_graph.bNode(dfs);
     
    10061010              pred.set(w, /*typename ErasingResGW::OutEdgeIt*/(dfs));
    10071011              if (erasing_res_graph.valid(pred[v])) {
    1008                 free1.set(w, std::min(free1[v], res_graph.resCap(
    1009                                                                  typename ErasingResGW::OutEdgeIt(dfs))));
     1012                free1.set
     1013                  (w, std::min(free1[v], res_graph.resCap
     1014                               (typename ErasingResGW::OutEdgeIt(dfs))));
    10101015              } else {
    1011                 free1.set(w, res_graph.resCap(
    1012                                               typename ErasingResGW::OutEdgeIt(dfs)));
     1016                free1.set
     1017                  (w, res_graph.resCap
     1018                   (typename ErasingResGW::OutEdgeIt(dfs)));
    10131019              }
    1014              
    1015               if (w==t) { 
    1016                 __augment=true; 
     1020
     1021              if (w==t) {
     1022                __augment=true;
    10171023                _augment=true;
    1018                 break; 
     1024                break;
    10191025              }
    10201026            } else {
     
    10221028            }
    10231029          }
    1024       } 
     1030      }
    10251031
    10261032      if (__augment) {
    1027         typename ErasingResGW::Node n=typename FilterResGW::Node(typename ResGW::Node(t));
     1033        typename ErasingResGW::Node
     1034          n=typename FilterResGW::Node(typename ResGW::Node(t));
    10281035        //        typename ResGW::NodeMap<Num> a(res_graph);
    10291036        //        typename ResGW::Node b;
     
    10361043        //        Num j2=a2[b2];
    10371044        Num augment_value=free1[n];
    1038         while (erasing_res_graph.valid(pred[n])) { 
     1045        while (erasing_res_graph.valid(pred[n])) {
    10391046          typename ErasingResGW::OutEdgeIt e=pred[n];
    10401047          res_graph.augment(e, augment_value);
     
    10441051        }
    10451052      }
    1046      
    1047     } //while (__augment) 
    1048            
     1053
     1054    } //while (__augment)
     1055
    10491056    return _augment;
    10501057  }
    10511058
    10521059
    1053 
    1054 
    10551060} //namespace hugo
    10561061
  • src/work/marci/bfs_dfs.h

    r604 r615  
    33#define HUGO_BFS_DFS_H
    44
    5 // ///\ingroup gwrappers
    6 ///\file
    7 ///\brief Bfs and dfs iterators.
     5/// \ingroup galgs
     6/// \file
     7/// \brief Bfs and dfs iterators.
    88///
    9 ///This file contains bfs and dfs iterator classes.
     9/// This file contains bfs and dfs iterator classes.
    1010///
    11 // ///\author Marton Makai
     11// /// \author Marton Makai
    1212
    1313#include <queue>
     
    2222  /// \c reached_map
    2323  /// Reached have to work as read-write bool Node-map.
     24  /// \ingroup galgs
    2425  template <typename Graph, /*typename OutEdgeIt,*/
    2526            typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
     
    106107      return *this;
    107108    }
    108     ///
     109    /// Guess what?
    109110    bool finished() const { return bfs_queue.empty(); }
    110111    /// The conversion operator makes for converting the bfs-iterator
     
    112113    ///\bug Edge have to be in HUGO 0.2
    113114    operator OutEdgeIt() const { return actual_edge; }
    114     ///
     115    /// Guess what?
    115116    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
    116     ///
     117    /// Guess what?
    117118    bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
    118     ///
     119    /// Guess what?
    119120    Node aNode() const { return bfs_queue.front(); }
    120     ///
     121    /// Guess what?
    121122    Node bNode() const { return graph->bNode(actual_edge); }
    122     ///
     123    /// Guess what?
    123124    const ReachedMap& getReachedMap() const { return reached; }
    124     ///
     125    /// Guess what?
    125126    const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
    126   }; 
     127  };
    127128
    128129  /// Bfs searches for the nodes wich are not marked in
     
    130131  /// Reached have to work as a read-write bool Node-map,
    131132  /// Pred is a write Edge Node-map and
    132   /// Dist is a read-write int Node-map, have to be.
    133   ///\todo In fact onsly simple operations requirement are needed for
    134   /// Dist::Value.
     133  /// Dist is a read-write Node-map of integral value, have to be.
     134  /// \ingroup galgs
    135135  template <typename Graph,
    136136            typename ReachedMap=typename Graph::template NodeMap<bool>,
     
    179179      return *this;
    180180    }
    181     ///
     181    /// Guess what?
    182182    const PredMap& getPredMap() const { return pred; }
    183     ///
     183    /// Guess what?
    184184    const DistMap& getDistMap() const { return dist; }
    185185  };
     
    188188  /// \c reached_map
    189189  /// Reached have to be a read-write bool Node-map.
     190  /// \ingroup galgs
    190191  template <typename Graph, /*typename OutEdgeIt,*/
    191192            typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
     
    249250      return *this;
    250251    }
    251     ///
     252    /// Guess what?
    252253    bool finished() const { return dfs_stack.empty(); }
    253     ///
     254    /// Guess what?
    254255    operator OutEdgeIt() const { return actual_edge; }
    255     ///
     256    /// Guess what?
    256257    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
    257     ///
     258    /// Guess what?
    258259    bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
    259     ///
     260    /// Guess what?
    260261    Node aNode() const { return actual_node; /*FIXME*/}
    261     ///
     262    /// Guess what?
    262263    Node bNode() const { return graph->bNode(actual_edge); }
    263     ///
     264    /// Guess what?
    264265    const ReachedMap& getReachedMap() const { return reached; }
    265     ///
     266    /// Guess what?
    266267    const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
    267268  };
     
    271272  /// Reached is a read-write bool Node-map,
    272273  /// Pred is a write Node-map, have to be.
     274  /// \ingroup galgs
    273275  template <typename Graph,
    274276            typename ReachedMap=typename Graph::template NodeMap<bool>,
     
    313315      return *this;
    314316    }
    315     ///
     317    /// Guess what?
    316318    const PredMap& getPredMap() const { return pred; }
    317319  };
  • src/work/marci/bfs_dfs_misc.h

    r604 r615  
    33#define HUGO_BFS_DFS_MISC_H
    44
    5 // ///\ingroup gwrappers
    6 ///\file
    7 ///\brief Miscellaneous algorithms using bfs and dfs.
     5/// \ingroup galgs
     6/// \file
     7/// \brief Miscellaneous algorithms using bfs and dfs.
    88///
    9 ///This file contains several algorithms using bfs and dfs.
     9/// This file contains several algorithms using bfs and dfs.
    1010///
    1111// ///\author Marton Makai
     
    1616namespace hugo {
    1717
    18   /// This function eat a read-write \c BoolMap& bool_map,
     18  /// This function eats a read-write \c BoolMap& bool_map,
    1919  /// which have to work well up
    2020  /// to its \c set and \c operator[]() method. Thus we have to deal
    2121  /// very carefully with an uninitialized \c IterableBoolMap.
     22  /// \ingroup galgs
    2223  template<typename Graph, typename BoolMap>
    2324  bool isBipartite(const Graph& g, BoolMap& bool_map) {
     
    5354  /// then going back from the returned node via the pred information, a
    5455  /// cycle is obtained.
     56  /// \ingroup galgs
    5557  template<typename Graph, typename PredMap>
    5658  typename Graph::Node
     
    9092    return INVALID;
    9193  }
     94
    9295} //namespace hugo
    9396
  • src/work/marci/makefile

    r613 r615  
    55
    66LEDABINARIES = leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo
    7 BINARIES = max_flow_demo iterator_bfs_demo macro_test lg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_try bipartite_matching_try_3 top_sort_test
     7BINARIES = max_flow_demo iterator_bfs_demo macro_test lg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_try bipartite_matching_try_3 top_sort_test max_flow_1
    88#gw_vs_not preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos edmonds_karp_demo_alpar preflow_demo_leda
    99
  • src/work/marci/max_bipartite_matching.h

    r613 r615  
    22#ifndef HUGO_MAX_BIPARTITE_MATCHING_H
    33#define HUGO_MAX_BIPARTITE_MATCHING_H
     4
     5/// \ingroup galgs
     6/// \file
     7/// \brief Maximum bipartite matchings, b-matchings and
     8/// capacitated b-matchings.
     9///
     10/// This file contains a class for bipartite maximum matching, b-matchings
     11/// and capacitated b-matching computations.
     12///
     13// /// \author Marton Makai
    414
    515//#include <for_each_macros.h>
Note: See TracChangeset for help on using the changeset viewer.