COIN-OR::LEMON - Graph Library

Changeset 631:26819ef1611f in lemon-0.x


Ignore:
Timestamp:
05/13/04 12:30:20 (17 years ago)
Author:
jacint
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@822
Message:

Almost full documentation added, NO_FLOW incorporated, Phase0(1) changed to Phase1(2)

File:
1 edited

Legend:

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

    r615 r631  
    11// -*- C++ -*-
    2 
    3 /*
    4   Heuristics:
    5   2 phase
    6   gap
    7   list 'level_list' on the nodes on level i implemented by hand
    8   stack 'active' on the active nodes on level i
    9   runs heuristic 'highest label' for H1*n relabels
    10   runs heuristic 'bound decrease' for H0*n relabels, starts with 'highest label'
    11 
    12   Parameters H0 and H1 are initialized to 20 and 1.
    13 
    14   Constructors:
    15 
    16   Preflow(Graph, Node, Node, CapMap, FlowMap, bool) : bool must be false if
    17   FlowMap is not constant zero, and should be true if it is
    18 
    19   Members:
    20 
    21   void run()
    22 
    23   Num flowValue() : returns the value of a maximum flow
    24 
    25   void minMinCut(CutMap& M) : sets M to the characteristic vector of the
    26   minimum min cut. M should be a map of bools initialized to false. ??Is it OK?
    27 
    28   void maxMinCut(CutMap& M) : sets M to the characteristic vector of the
    29   maximum min cut. M should be a map of bools initialized to false.
    30 
    31   void minCut(CutMap& M) : sets M to the characteristic vector of
    32   a min cut. M should be a map of bools initialized to false.
    33 
    34 */
    35 
    362#ifndef HUGO_MAX_FLOW_H
    373#define HUGO_MAX_FLOW_H
     
    4814
    4915/// \file
    50 /// \brief Maximum flows.
     16/// \brief Maximum flow algorithms.
    5117/// \ingroup galgs
    5218
    5319namespace hugo {
    5420
    55 
    56   //  ///\author Marton Makai, Jacint Szabo
    57   /// A class for computing max flows and related quantities.
    58   /// \ingroup galgs
     21  /// \addtogroup galgs
     22  /// @{                                                                                                                                       
     23  ///Maximum flow algorithms class.
     24
     25  ///This class provides various algorithms for finding a flow of
     26  ///maximum value in a directed graph. The \e source node, the \e
     27  ///target node, the \e capacity of the edges and the \e starting \e
     28  ///flow value of the edges can be passed to the algorithm through the
     29  ///constructor. It is possible to change these quantities using the
     30  ///functions \ref resetSource, \ref resetTarget, \ref resetCap and
     31  ///\ref resetFlow. Before any subsequent runs of any algorithm of
     32  ///the class \ref resetFlow should be called, otherwise it will
     33  ///start from a maximum flow.                                                                                                                 
     34  ///After running an algorithm of the class, the maximum value of a
     35  ///value can be obtained by calling \ref flowValue(). The minimum
     36  ///value cut can be written into a \c node map of \c bools by
     37  ///calling \ref minCut. (\ref minMinCut and \ref maxMinCut writes
     38  ///the inclusionwise minimum and maximum of the minimum value
     39  ///cuts, resp.)                                                                                                                               
     40  ///\param Graph The undirected graph type the algorithm runs on.
     41  ///\param Num The number type of the capacities and the flow values.
     42  ///\param CapMap The type of the capacity map.
     43  ///\param FlowMap The type of the flow map.                                                                                                           
     44  ///\author Marton Makai, Jacint Szabo
    5945  template <typename Graph, typename Num,
    6046            typename CapMap=typename Graph::template EdgeMap<Num>,
     
    6450    typedef typename Graph::Node Node;
    6551    typedef typename Graph::NodeIt NodeIt;
     52    typedef typename Graph::EdgeIt EdgeIt;
    6653    typedef typename Graph::OutEdgeIt OutEdgeIt;
    6754    typedef typename Graph::InEdgeIt InEdgeIt;
     
    8269    //typedef typename ResGW::template NodeMap<bool> ReachedMap;
    8370    typedef typename Graph::template NodeMap<int> ReachedMap;
     71
     72
     73    //level works as a bool map in augmenting path algorithms and is
     74    //used by bfs for storing reached information.  In preflow, it
     75    //shows the levels of nodes.     
    8476    ReachedMap level;
    85     //level works as a bool map in augmenting path algorithms
    86     //and is used by bfs for storing reached information.
    87     //In preflow, it shows levels of nodes.
    88     //typename Graph::template NodeMap<int> level;
     77
     78    //excess is needed only in preflow
    8979    typename Graph::template NodeMap<Num> excess;
    90     //   protected:
     80
     81    //fixme   
     82//   protected:
    9183    //     MaxFlow() { }
    9284    //     void set(const Graph& _G, Node _s, Node _t, const CapMap& _capacity,
     
    109101  public:
    110102
    111     ///\todo Document this.
    112     ///\todo Maybe, it should be PRE_FLOW instead.
    113     ///- \c NO_FLOW means nothing,
    114     ///- \c ZERO_FLOW means something,
    115     ///- \c GEN_FLOW means something else,
    116     ///- \c PRE_FLOW is something different.
     103    ///Indicates the property of the starting flow.
     104
     105    ///Indicates the property of the starting flow. The meanings are as follows:
     106    ///- \c ZERO_FLOW: constant zero flow
     107    ///- \c GEN_FLOW: any flow, i.e. the sum of the in-flows equals to
     108    ///the sum of the out-flows in every node except the \e source and
     109    ///the \e target.
     110    ///- \c PRE_FLOW: any preflow, i.e. the sum of the in-flows is at
     111    ///least the sum of the out-flows in every node except the \e source.
     112    ///- \c NO_FLOW: indicates an unspecified edge map. \ref flow will be
     113    ///set to the constant zero flow in the beginning of the algorithm in this case.
    117114    enum flowEnum{
    118115      ZERO_FLOW,
     
    127124      flow(&_flow), n(_G.nodeNum()), level(_G), excess(_G,0) {}
    128125
    129     /// A max flow algorithm is run.
    130     /// \pre The flow have to satisfy the requirements
    131     /// stated in fe.
     126    ///Runs a maximum flow algorithm.
     127
     128    ///Runs a preflow algorithm, which is the fastest maximum flow
     129    ///algorithm up-to-date. The default for \c fe is ZERO_FLOW.
     130    ///\pre The starting flow must be
     131    /// - a constant zero flow if \c fe is \c ZERO_FLOW,
     132    /// - an arbitary flow if \c fe is \c GEN_FLOW,
     133    /// - an arbitary preflow if \c fe is \c PRE_FLOW,
     134    /// - any map if \c fe is NO_FLOW.
    132135    void run(flowEnum fe=ZERO_FLOW) {
    133136      preflow(fe);
    134137    }
    135138
    136     /// A preflow algorithm is run.
    137     /// \pre The initial edge-map have to be a
    138     /// zero flow if \c fe is \c ZERO_FLOW,
    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.
     139                                                                                             
     140    ///Runs a preflow algorithm. 
     141
     142    ///Runs a preflow algorithm. The preflow algorithms provide the
     143    ///fastest way to compute a maximum flow in a directed graph.
     144    ///\pre The starting flow must be
     145    /// - a constant zero flow if \c fe is \c ZERO_FLOW,
     146    /// - an arbitary flow if \c fe is \c GEN_FLOW,
     147    /// - an arbitary preflow if \c fe is \c PRE_FLOW,
     148    /// - any map if \c fe is NO_FLOW.
    142149    void preflow(flowEnum fe) {
    143       preflowPhase0(fe);
    144       preflowPhase1();
    145     }
    146 
    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);
    150 
    151     /// Second phase of preflow.
    152     void preflowPhase1();
     150      preflowPhase1(fe);
     151      preflowPhase2();
     152    }
     153    // Heuristics:
     154    //   2 phase
     155    //   gap
     156    //   list 'level_list' on the nodes on level i implemented by hand
     157    //   stack 'active' on the active nodes on level i                                                                                   
     158    //   runs heuristic 'highest label' for H1*n relabels
     159    //   runs heuristic 'bound decrease' for H0*n relabels, starts with 'highest label'
     160    //   Parameters H0 and H1 are initialized to 20 and 1.
     161
     162    ///Runs the first phase of the preflow algorithm.
     163
     164    ///The preflow algorithm consists of two phases, this method runs the
     165    ///first phase. After the first phase the maximum flow value and a
     166    ///minimum value cut can already be computed, though a maximum flow
     167    ///is net yet obtained. So after calling this method \ref flowValue
     168    ///and \ref actMinCut gives proper results.
     169    ///\warning: \ref minCut, \ref minMinCut and \ref maxMinCut do not
     170    ///give minimum value cuts unless calling \ref preflowPhase2.
     171    ///\pre The starting flow must be
     172    /// - a constant zero flow if \c fe is \c ZERO_FLOW,
     173    /// - an arbitary flow if \c fe is \c GEN_FLOW,
     174    /// - an arbitary preflow if \c fe is \c PRE_FLOW,
     175    /// - any map if \c fe is NO_FLOW.
     176    void preflowPhase1( flowEnum fe );
     177
     178    ///Runs the second phase of the preflow algorithm.
     179
     180    ///The preflow algorithm consists of two phases, this method runs
     181    ///the second phase. After calling \ref preflowPhase1 and then
     182    ///\ref preflowPhase2 the methods \ref flowValue, \ref minCut,
     183    ///\ref minMinCut and \ref maxMinCut give proper results.
     184    ///\pre \ref preflowPhase1 must be called before.
     185    void preflowPhase2();
    153186
    154187    /// Starting from a flow, this method searches for an augmenting path
     
    170203    bool augmentOnBlockingFlow2();
    171204
    172     /// Returns the actual flow value.
    173     /// More precisely, it returns the negative excess of s, thus
    174     /// this works also for preflows.
     205    /// Returns the maximum value of a flow.
     206
     207    /// Returns the maximum value of a flow, by counting the
     208    /// over-flow of the target node \ref t.
     209    /// It can be called already after running \ref preflowPhase1.
    175210    Num flowValue() {
    176211      Num a=0;
     
    178213      FOR_EACH_INC_LOC(OutEdgeIt, e, *g, t) a-=(*flow)[e];
    179214      return a;
    180     }
    181 
    182     /// Should be used between preflowPhase0 and preflowPhase1.
     215      //marci figyu: excess[t] epp ezt adja preflow 1. fazisa utan   
     216    }
     217
     218    ///Returns a minimum value cut after calling \ref preflowPhase1.
     219
     220    ///After the first phase of the preflow algorithm the maximum flow
     221    ///value and a minimum value cut can already be computed. This
     222    ///method can be called after running \ref preflowPhase1 for
     223    ///obtaining a minimum value cut.
     224    /// \warning Gives proper result only right after calling \ref
     225    /// preflowPhase1.
    183226    /// \todo We have to make some status variable which shows the
    184227    /// actual state
     
    197240    }
    198241
    199     /// The unique inclusionwise minimum cut is computed by
    200     /// processing a bfs from s in the residual graph.
    201     /// \pre flow have to be a max flow otherwise it will the whole node-set.
     242    ///Returns the inclusionwise minimum of the minimum value cuts.
     243
     244    ///Sets \c M to the characteristic vector of the minimum value cut
     245    ///which is inclusionwise minimum. It is computed by processing
     246    ///a bfs from the source node \c s in the residual graph.
     247    ///\pre M should be a node map of bools initialized to false.
     248    ///\pre \c flow must be a maximum flow.
    202249    template<typename _CutMap>
    203250    void minMinCut(_CutMap& M) {
     
    232279    }
    233280
    234 
    235     /// The unique inclusionwise maximum cut is computed by
    236     /// processing a reverse bfs from t in the residual graph.
    237     /// \pre flow have to be a max flow otherwise it will be empty.
     281    ///Returns the inclusionwise maximum of the minimum value cuts.
     282
     283    ///Sets \c M to the characteristic vector of the minimum value cut
     284    ///which is inclusionwise maximum. It is computed by processing a
     285    ///backward bfs from the target node \c t in the residual graph.
     286    ///\pre M should be a node map of bools initialized to false.
     287    ///\pre \c flow must be a maximum flow.
    238288    template<typename _CutMap>
    239289    void maxMinCut(_CutMap& M) {
     
    273323    }
    274324
    275 
    276     /// A minimum cut is computed.
     325    ///Returns a minimum value cut.
     326
     327    ///Sets \c M to the characteristic vector of a minimum value cut.
     328    ///\pre M should be a node map of bools initialized to false.
     329    ///\pre \c flow must be a maximum flow.   
    277330    template<typename CutMap>
    278331    void minCut(CutMap& M) { minMinCut(M); }
    279332
    280     ///
     333    ///Resets the source node to \c _s.
     334
     335    ///Resets the source node to \c _s.
     336    ///
    281337    void resetSource(Node _s) { s=_s; }
     338
     339    ///Resets the target node to \c _t.
     340
     341    ///Resets the target node to \c _t.
    282342    ///
    283343    void resetTarget(Node _t) { t=_t; }
    284344
    285     /// capacity-map is changed.
     345    /// Resets the edge map of the capacities to _cap.
     346
     347    /// Resets the edge map of the capacities to _cap.
     348    ///
    286349    void resetCap(const CapMap& _cap) { capacity=&_cap; }
    287350
    288     /// flow-map is changed.
     351    /// Resets the edge map of the flows to _flow.
     352
     353    /// Resets the edge map of the flows to _flow.
     354    ///
    289355    void resetFlow(FlowMap& _flow) { flow=&_flow; }
    290356
     
    375441
    376442      switch (fe) {
     443      case NO_FLOW:   //flow is already set to const zero in this case
    377444      case ZERO_FLOW:
    378445        {
     
    587654
    588655  template <typename Graph, typename Num, typename CapMap, typename FlowMap>
    589   void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase0( flowEnum fe )
     656  void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase1( flowEnum fe )
    590657  {
    591658
     
    616683    //setting each node to level n
    617684
    618     switch (fe) {
     685    if ( fe == NO_FLOW ) {
     686      EdgeIt e;
     687      for(g->first(e); g->valid(e); g->next(e)) flow->set(e,0);
     688    }
     689
     690    switch (fe) { //computing the excess
    619691    case PRE_FLOW:
    620692      {
    621         //computing the excess
    622693        NodeIt v;
    623694        for(g->first(v); g->valid(v); g->next(v)) {
     
    639710    case GEN_FLOW:
    640711      {
    641         //computing the excess of t
     712        NodeIt v;
     713        for(g->first(v); g->valid(v); g->next(v)) excess.set(v,0);
     714
    642715        Num exc=0;
    643 
    644716        InEdgeIt e;
    645717        for(g->first(e,t); g->valid(e); g->next(e)) exc+=(*flow)[e];
    646718        OutEdgeIt f;
    647719        for(g->first(f,t); g->valid(f); g->next(f)) exc-=(*flow)[f];
    648 
    649720        excess.set(t,exc);
    650 
    651721        break;
    652722      }
    653     default:;
     723    case ZERO_FLOW:
     724    case NO_FLOW:
     725      {
     726        NodeIt v;
     727        for(g->first(v); g->valid(v); g->next(v)) excess.set(v,0);
     728        break;
     729      }
    654730    }
    655731
     
    696772
    697773  template <typename Graph, typename Num, typename CapMap, typename FlowMap>
    698   void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase1()
     774  void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase2()
    699775  {
    700776
Note: See TracChangeset for help on using the changeset viewer.