COIN-OR::LEMON - Graph Library

Changeset 2514:57143c09dc20 in lemon-0.x for lemon/edmonds_karp.h


Ignore:
Timestamp:
11/17/07 21:58:11 (13 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3379
Message:

Redesign the maximum flow algorithms

Redesigned interface
Preflow changed to use elevator
Edmonds-Karp does not use the ResGraphAdaptor?
Goldberg-Tarjan algorithm (Preflow with Dynamic Trees)
Dinitz-Sleator-Tarjan (Blocking flow with Dynamic Tree)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/edmonds_karp.h

    r2391 r2514  
    2424/// \brief Implementation of the Edmonds-Karp algorithm.
    2525
    26 #include <lemon/graph_adaptor.h>
    2726#include <lemon/tolerance.h>
    28 #include <lemon/bfs.h>
     27#include <vector>
    2928
    3029namespace lemon {
    3130
     31  /// \brief Default traits class of EdmondsKarp class.
     32  ///
     33  /// Default traits class of EdmondsKarp class.
     34  /// \param _Graph Graph type.
     35  /// \param _CapacityMap Type of capacity map.
     36  template <typename _Graph, typename _CapacityMap>
     37  struct EdmondsKarpDefaultTraits {
     38
     39    /// \brief The graph type the algorithm runs on.
     40    typedef _Graph Graph;
     41
     42    /// \brief The type of the map that stores the edge capacities.
     43    ///
     44    /// The type of the map that stores the edge capacities.
     45    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
     46    typedef _CapacityMap CapacityMap;
     47
     48    /// \brief The type of the length of the edges.
     49    typedef typename CapacityMap::Value Value;
     50
     51    /// \brief The map type that stores the flow values.
     52    ///
     53    /// The map type that stores the flow values.
     54    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     55    typedef typename Graph::template EdgeMap<Value> FlowMap;
     56
     57    /// \brief Instantiates a FlowMap.
     58    ///
     59    /// This function instantiates a \ref FlowMap.
     60    /// \param graph The graph, to which we would like to define the flow map.
     61    static FlowMap* createFlowMap(const Graph& graph) {
     62      return new FlowMap(graph);
     63    }
     64
     65    /// \brief The tolerance used by the algorithm
     66    ///
     67    /// The tolerance used by the algorithm to handle inexact computation.
     68    typedef Tolerance<Value> Tolerance;
     69
     70  };
     71
    3272  /// \ingroup max_flow
     73  ///
    3374  /// \brief Edmonds-Karp algorithms class.
    3475  ///
    3576  /// This class provides an implementation of the \e Edmonds-Karp \e
    3677  /// algorithm producing a flow of maximum value in a directed
    37   /// graph. The Edmonds-Karp algorithm is slower than the Preflow algorithm
    38   /// but it has an advantage of the step-by-step execution control with
    39   /// feasible flow solutions. The \e source node, the \e target node, the \e
    40   /// capacity of the edges and the \e starting \e flow value of the
    41   /// edges should be passed to the algorithm through the
    42   /// constructor.
     78  /// graphs. The Edmonds-Karp algorithm is slower than the Preflow
     79  /// algorithm but it has an advantage of the step-by-step execution
     80  /// control with feasible flow solutions. The \e source node, the \e
     81  /// target node, the \e capacity of the edges and the \e starting \e
     82  /// flow value of the edges should be passed to the algorithm
     83  /// through the constructor.
    4384  ///
    44   /// The time complexity of the algorithm is \f$ O(n * e^2) \f$ in
     85  /// The time complexity of the algorithm is \f$ O(nm^2) \f$ in
    4586  /// worst case.  Always try the preflow algorithm instead of this if
    4687  /// you just want to compute the optimal flow.
    4788  ///
    4889  /// \param _Graph The directed graph type the algorithm runs on.
    49   /// \param _Number The number type of the capacities and the flow values.
    5090  /// \param _CapacityMap The capacity map type.
    51   /// \param _FlowMap The flow map type.
    52   /// \param _Tolerance The tolerance class to handle computation problems.
     91  /// \param _Traits Traits class to set various data types used by
     92  /// the algorithm.  The default traits class is \ref
     93  /// EdmondsKarpDefaultTraits.  See \ref EdmondsKarpDefaultTraits for the
     94  /// documentation of a Edmonds-Karp traits class.
    5395  ///
    5496  /// \author Balazs Dezso
    5597#ifdef DOXYGEN
    56   template <typename _Graph, typename _Number,
    57             typename _CapacityMap, typename _FlowMap, typename _Tolerance>
    58 #else
    59   template <typename _Graph, typename _Number,
    60             typename _CapacityMap = typename _Graph::template EdgeMap<_Number>,
    61             typename _FlowMap = typename _Graph::template EdgeMap<_Number>,
    62             typename _Tolerance = Tolerance<_Number> >
     98  template <typename _Graph, typename _CapacityMap, typename _Traits>
     99#else
     100  template <typename _Graph,
     101            typename _CapacityMap = typename _Graph::template EdgeMap<int>,
     102            typename _Traits = EdmondsKarpDefaultTraits<_Graph, _CapacityMap> >
    63103#endif
    64104  class EdmondsKarp {
    65105  public:
     106
     107    typedef _Traits Traits;
     108    typedef typename Traits::Graph Graph;
     109    typedef typename Traits::CapacityMap CapacityMap;
     110    typedef typename Traits::Value Value;
     111
     112    typedef typename Traits::FlowMap FlowMap;
     113    typedef typename Traits::Tolerance Tolerance;
    66114
    67115    /// \brief \ref Exception for the case when the source equals the target.
     
    77125
    78126
    79     /// \brief The graph type the algorithm runs on.
    80     typedef _Graph Graph;
    81     /// \brief The value type of the algorithms.
    82     typedef _Number Number;
    83     /// \brief The capacity map on the edges.
    84     typedef _CapacityMap CapacityMap;
    85     /// \brief The flow map on the edges.
    86     typedef _FlowMap FlowMap;
    87     /// \brief The tolerance used by the algorithm.
    88     typedef _Tolerance Tolerance;
    89 
    90     typedef ResGraphAdaptor<Graph, Number, CapacityMap,
    91                             FlowMap, Tolerance> ResGraph;
    92 
    93127  private:
    94128
    95     typedef typename Graph::Node Node;
    96     typedef typename Graph::Edge Edge;
     129    GRAPH_TYPEDEFS(typename Graph);
     130    typedef typename Graph::template NodeMap<Edge> PredMap;
    97131   
    98     typedef typename Graph::NodeIt NodeIt;
    99     typedef typename Graph::EdgeIt EdgeIt;
    100     typedef typename Graph::InEdgeIt InEdgeIt;
    101     typedef typename Graph::OutEdgeIt OutEdgeIt;
     132    const Graph& _graph;
     133    const CapacityMap* _capacity;
     134
     135    Node _source, _target;
     136
     137    FlowMap* _flow;
     138    bool _local_flow;
     139
     140    PredMap* _pred;
     141    std::vector<Node> _queue;
     142   
     143    Tolerance _tolerance;
     144    Value _flow_value;
     145
     146    void createStructures() {
     147      if (!_flow) {
     148        _flow = Traits::createFlowMap(_graph);
     149        _local_flow = true;
     150      }
     151      if (!_pred) {
     152        _pred = new PredMap(_graph);
     153      }
     154      _queue.resize(countNodes(_graph));
     155    }
     156
     157    void destroyStructures() {
     158      if (_local_flow) {
     159        delete _flow;
     160      }
     161      if (_pred) {
     162        delete _pred;
     163      }
     164    }
    102165   
    103166  public:
    104167
     168    ///\name Named template parameters
     169
     170    ///@{
     171
     172    template <typename _FlowMap>
     173    struct DefFlowMapTraits : public Traits {
     174      typedef _FlowMap FlowMap;
     175      static FlowMap *createFlowMap(const Graph&) {
     176        throw UninitializedParameter();
     177      }
     178    };
     179
     180    /// \brief \ref named-templ-param "Named parameter" for setting
     181    /// FlowMap type
     182    ///
     183    /// \ref named-templ-param "Named parameter" for setting FlowMap
     184    /// type
     185    template <typename _FlowMap>
     186    struct DefFlowMap
     187      : public EdmondsKarp<Graph, CapacityMap, DefFlowMapTraits<_FlowMap> > {
     188      typedef EdmondsKarp<Graph, CapacityMap, DefFlowMapTraits<_FlowMap> >
     189      Create;
     190    };
     191
     192
     193    /// @}
     194
    105195    /// \brief The constructor of the class.
    106196    ///
    107197    /// The constructor of the class.
    108198    /// \param graph The directed graph the algorithm runs on.
     199    /// \param capacity The capacity of the edges.
    109200    /// \param source The source node.
    110201    /// \param target The target node.
    111     /// \param capacity The capacity of the edges.
    112     /// \param flow The flow of the edges.
    113     /// \param tolerance Tolerance class.
    114     EdmondsKarp(const Graph& graph, Node source, Node target,
    115                 const CapacityMap& capacity, FlowMap& flow,
    116                 const Tolerance& tolerance = Tolerance())
    117       : _graph(graph), _capacity(capacity), _flow(flow),
    118         _tolerance(tolerance), _resgraph(graph, capacity, flow, tolerance),
    119         _source(source), _target(target)
     202    EdmondsKarp(const Graph& graph, const CapacityMap& capacity,
     203                Node source, Node target)
     204      : _graph(graph), _capacity(&capacity), _source(source), _target(target),
     205        _flow(0), _local_flow(false), _pred(0), _tolerance(), _flow_value()
    120206    {
    121207      if (_source == _target) {
     
    123209      }
    124210    }
     211
     212    /// \brief Destrcutor.
     213    ///
     214    /// Destructor.
     215    ~EdmondsKarp() {
     216      destroyStructures();
     217    }
     218
     219    /// \brief Sets the capacity map.
     220    ///
     221    /// Sets the capacity map.
     222    /// \return \c (*this)
     223    EdmondsKarp& capacityMap(const CapacityMap& map) {
     224      _capacity = &map;
     225      return *this;
     226    }
     227
     228    /// \brief Sets the flow map.
     229    ///
     230    /// Sets the flow map.
     231    /// \return \c (*this)
     232    EdmondsKarp& flowMap(FlowMap& map) {
     233      if (_local_flow) {
     234        delete _flow;
     235        _local_flow = false;
     236      }
     237      _flow = &map;
     238      return *this;
     239    }
     240
     241    /// \brief Returns the flow map.
     242    ///
     243    /// \return The flow map.
     244    const FlowMap& flowMap() {
     245      return *_flow;
     246    }
     247
     248    /// \brief Sets the source node.
     249    ///
     250    /// Sets the source node.
     251    /// \return \c (*this)
     252    EdmondsKarp& source(const Node& node) {
     253      _source = node;
     254      return *this;
     255    }
     256
     257    /// \brief Sets the target node.
     258    ///
     259    /// Sets the target node.
     260    /// \return \c (*this)
     261    EdmondsKarp& target(const Node& node) {
     262      _target = node;
     263      return *this;
     264    }
     265
     266    /// \brief Sets the tolerance used by algorithm.
     267    ///
     268    /// Sets the tolerance used by algorithm.
     269    EdmondsKarp& tolerance(const Tolerance& tolerance) const {
     270      _tolerance = tolerance;
     271      return *this;
     272    }
     273
     274    /// \brief Returns the tolerance used by algorithm.
     275    ///
     276    /// Returns the tolerance used by algorithm.
     277    const Tolerance& tolerance() const {
     278      return tolerance;
     279    }
     280
     281    /// \name Execution control The simplest way to execute the
     282    /// algorithm is to use the \c run() member functions.
     283    /// \n
     284    /// If you need more control on initial solution or
     285    /// execution then you have to call one \ref init() function and then
     286    /// the start() or multiple times the \c augment() member function. 
     287   
     288    ///@{
    125289
    126290    /// \brief Initializes the algorithm
     
    128292    /// It sets the flow to empty flow.
    129293    void init() {
     294      createStructures();
    130295      for (EdgeIt it(_graph); it != INVALID; ++it) {
    131         _flow.set(it, 0);
    132       }
    133       _value = 0;
     296        _flow->set(it, 0);
     297      }
     298      _flow_value = 0;
    134299    }
    135300   
    136301    /// \brief Initializes the algorithm
    137302    ///
    138     /// If the flow map initially flow this let the flow map
    139     /// unchanged but the flow value will be set by the flow
    140     /// on the outedges from the source.
    141     void flowInit() {
    142       _value = 0;
     303    /// Initializes the flow to the \c flowMap. The \c flowMap should
     304    /// contain a feasible flow, ie. in each node excluding the source
     305    /// and the target the incoming flow should be equal to the
     306    /// outgoing flow.
     307    template <typename FlowMap>
     308    void flowInit(const FlowMap& flowMap) {
     309      createStructures();
     310      for (EdgeIt e(_graph); e != INVALID; ++e) {
     311        _flow->set(e, flowMap[e]);
     312      }
     313      _flow_value = 0;
    143314      for (OutEdgeIt jt(_graph, _source); jt != INVALID; ++jt) {
    144         _value += _flow[jt];
     315        _flow_value += (*_flow)[jt];
    145316      }
    146317      for (InEdgeIt jt(_graph, _source); jt != INVALID; ++jt) {
    147         _value -= _flow[jt];
     318        _flow_value -= (*_flow)[jt];
    148319      }
    149320    }
     
    151322    /// \brief Initializes the algorithm
    152323    ///
    153     /// If the flow map initially flow this let the flow map
    154     /// unchanged but the flow value will be set by the flow
    155     /// on the outedges from the source. It also checks that
    156     /// the flow map really contains a flow.
    157     /// \return %True when the flow map really a flow.
    158     bool checkedFlowInit() {
    159       _value = 0;
    160       for (OutEdgeIt jt(_graph, _source); jt != INVALID; ++jt) {
    161         _value += _flow[jt];
    162       }
    163       for (InEdgeIt jt(_graph, _source); jt != INVALID; ++jt) {
    164         _value -= _flow[jt];
     324    /// Initializes the flow to the \c flowMap. The \c flowMap should
     325    /// contain a feasible flow, ie. in each node excluding the source
     326    /// and the target the incoming flow should be equal to the
     327    /// outgoing flow. 
     328    /// \return %False when the given flowMap does not contain
     329    /// feasible flow.
     330    template <typename FlowMap>
     331    bool checkedFlowInit(const FlowMap& flowMap) {
     332      createStructures();
     333      for (EdgeIt e(_graph); e != INVALID; ++e) {
     334        _flow->set(e, flowMap[e]);
    165335      }
    166336      for (NodeIt it(_graph); it != INVALID; ++it) {
    167337        if (it == _source || it == _target) continue;
    168         Number outFlow = 0;
     338        Value outFlow = 0;
    169339        for (OutEdgeIt jt(_graph, it); jt != INVALID; ++jt) {
    170           outFlow += _flow[jt];
     340          outFlow += (*_flow)[jt];
    171341        }
    172         Number inFlow = 0;
     342        Value inFlow = 0;
    173343        for (InEdgeIt jt(_graph, it); jt != INVALID; ++jt) {
    174           inFlow += _flow[jt];
     344          inFlow += (*_flow)[jt];
    175345        }
    176346        if (_tolerance.different(outFlow, inFlow)) {
     
    179349      }
    180350      for (EdgeIt it(_graph); it != INVALID; ++it) {
    181         if (_tolerance.less(_flow[it], 0)) return false;
    182         if (_tolerance.less(_capacity[it], _flow[it])) return false;
     351        if (_tolerance.less((*_flow)[it], 0)) return false;
     352        if (_tolerance.less((*_capacity)[it], (*_flow)[it])) return false;
     353      }
     354      _flow_value = 0;
     355      for (OutEdgeIt jt(_graph, _source); jt != INVALID; ++jt) {
     356        _flow_value += (*_flow)[jt];
     357      }
     358      for (InEdgeIt jt(_graph, _source); jt != INVALID; ++jt) {
     359        _flow_value -= (*_flow)[jt];
    183360      }
    184361      return true;
     
    196373    /// current flow is a feasible and optimal solution.
    197374    bool augment() {
    198       typename Bfs<ResGraph>
    199       ::template DefDistMap<NullMap<Node, int> >
    200       ::Create bfs(_resgraph);
    201 
    202       NullMap<Node, int> distMap;
    203       bfs.distMap(distMap);
     375      for (NodeIt n(_graph); n != INVALID; ++n) {
     376        _pred->set(n, INVALID);
     377      }
    204378     
    205       bfs.init();
    206       bfs.addSource(_source);
    207       bfs.start(_target);
    208 
    209       if (!bfs.reached(_target)) {
    210         return false;
    211       }
    212       Number min = _resgraph.rescap(bfs.predEdge(_target));
    213       for (Node it = bfs.predNode(_target); it != _source;
    214            it = bfs.predNode(it)) {
    215         if (min > _resgraph.rescap(bfs.predEdge(it))) {
    216           min = _resgraph.rescap(bfs.predEdge(it));
    217         }
    218       }
    219       for (Node it = _target; it != _source; it = bfs.predNode(it)) {
    220         _resgraph.augment(bfs.predEdge(it), min);
    221       }
    222       _value += min;
    223       return true;
     379      int first = 0, last = 1;
     380     
     381      _queue[0] = _source;
     382      _pred->set(_source, OutEdgeIt(_graph, _source));
     383
     384      while (first != last && (*_pred)[_target] == INVALID) {
     385        Node n = _queue[first++];
     386       
     387        for (OutEdgeIt e(_graph, n); e != INVALID; ++e) {
     388          Value rem = (*_capacity)[e] - (*_flow)[e];
     389          Node t = _graph.target(e);
     390          if (_tolerance.positive(rem) && (*_pred)[t] == INVALID) {
     391            _pred->set(t, e);
     392            _queue[last++] = t;
     393          }
     394        }
     395        for (InEdgeIt e(_graph, n); e != INVALID; ++e) {
     396          Value rem = (*_flow)[e];
     397          Node t = _graph.source(e);
     398          if (_tolerance.positive(rem) && (*_pred)[t] == INVALID) {
     399            _pred->set(t, e);
     400            _queue[last++] = t;
     401          }
     402        }
     403      }
     404
     405      if ((*_pred)[_target] != INVALID) {
     406        Node n = _target;
     407        Edge e = (*_pred)[n];
     408
     409        Value prem = (*_capacity)[e] - (*_flow)[e];
     410        n = _graph.source(e);
     411        while (n != _source) {
     412          e = (*_pred)[n];
     413          if (_graph.target(e) == n) {
     414            Value rem = (*_capacity)[e] - (*_flow)[e];
     415            if (rem < prem) prem = rem;
     416            n = _graph.source(e);
     417          } else {
     418            Value rem = (*_flow)[e];
     419            if (rem < prem) prem = rem;
     420            n = _graph.target(e);   
     421          }
     422        }
     423
     424        n = _target;
     425        e = (*_pred)[n];
     426
     427        _flow->set(e, (*_flow)[e] + prem);
     428        n = _graph.source(e);
     429        while (n != _source) {
     430          e = (*_pred)[n];
     431          if (_graph.target(e) == n) {
     432            _flow->set(e, (*_flow)[e] + prem);
     433            n = _graph.source(e);
     434          } else {
     435            _flow->set(e, (*_flow)[e] - prem);
     436            n = _graph.target(e);   
     437          }
     438        }
     439
     440        _flow_value += prem;   
     441        return true;
     442      } else {
     443        return false;
     444      }
    224445    }
    225446
     
    229450    void start() {
    230451      while (augment()) {}
    231     }
    232 
    233     /// \brief Gives back the current flow value.
    234     ///
    235     /// Gives back the current flow _value.
    236     Number flowValue() const {
    237       return _value;
    238452    }
    239453
     
    251465    }
    252466
     467    /// @}
     468
     469    /// \name Query Functions
     470    /// The result of the %Dijkstra algorithm can be obtained using these
     471    /// functions.\n
     472    /// Before the use of these functions,
     473    /// either run() or start() must be called.
     474   
     475    ///@{
     476
     477    /// \brief Returns the value of the maximum flow.
     478    ///
     479    /// Returns the value of the maximum flow by returning the excess
     480    /// of the target node \c t. This value equals to the value of
     481    /// the maximum flow already after the first phase.
     482    Value flowValue() const {
     483      return _flow_value;
     484    }
     485
     486
     487    /// \brief Returns the flow on the edge.
     488    ///
     489    /// Sets the \c flowMap to the flow on the edges. This method can
     490    /// be called after the second phase of algorithm.
     491    Value flow(const Edge& edge) const {
     492      return (*_flow)[edge];
     493    }
     494
     495    /// \brief Returns true when the node is on the source side of minimum cut.
     496    ///
     497
     498    /// Returns true when the node is on the source side of minimum
     499    /// cut. This method can be called both after running \ref
     500    /// startFirstPhase() and \ref startSecondPhase().
     501    bool minCut(const Node& node) const {
     502      return (*_pred)[node] != INVALID;
     503    }
     504
    253505    /// \brief Returns a minimum value cut.
    254506    ///
     
    257509    /// \retval cut Write node bool map.
    258510    template <typename CutMap>
    259     void minCut(CutMap& cut) const {
    260       minMinCut(cut);
    261     }
    262 
    263     /// \brief Returns the inclusionwise minimum of the minimum value cuts.
    264     ///
    265     /// Sets \c cut to the characteristic vector of the minimum value cut
    266     /// which is inclusionwise minimum. It is computed by processing a
    267     /// bfs from the source node \c source in the residual graph. 
    268     /// \retval cut Write node bool map.
    269     template <typename CutMap>
    270     void minMinCut(CutMap& cut) const {
    271 
    272       typename Bfs<ResGraph>
    273       ::template DefDistMap<NullMap<Node, int> >
    274       ::template DefProcessedMap<CutMap>
    275       ::Create bfs(_resgraph);
    276 
    277       NullMap<Node, int> distMap;
    278       bfs.distMap(distMap);
    279 
    280       bfs.processedMap(cut);
    281      
    282       bfs.run(_source);
    283     }
    284 
    285     /// \brief Returns the inclusionwise minimum of the minimum value cuts.
    286     ///
    287     /// Sets \c cut to the characteristic vector of the minimum value cut
    288     /// which is inclusionwise minimum. It is computed by processing a
    289     /// bfs from the source node \c source in the residual graph. 
    290     /// \retval cut Write node bool map.
    291     template <typename CutMap>
    292     void maxMinCut(CutMap& cut) const {
    293 
    294       typedef RevGraphAdaptor<const ResGraph> RevGraph;
    295 
    296       RevGraph revgraph(_resgraph);
    297 
    298       typename Bfs<RevGraph>
    299       ::template DefDistMap<NullMap<Node, int> >
    300       ::template DefPredMap<NullMap<Node, Edge> >
    301       ::template DefProcessedMap<NotWriteMap<CutMap> >
    302       ::Create bfs(revgraph);
    303 
    304       NullMap<Node, int> distMap;
    305       bfs.distMap(distMap);
    306 
    307       NullMap<Node, Edge> predMap;
    308       bfs.predMap(predMap);
    309 
    310       NotWriteMap<CutMap> notcut(cut);
    311       bfs.processedMap(notcut);
    312      
    313       bfs.run(_target);
    314     }
    315 
    316     /// \brief Returns the source node.
    317     ///
    318     /// Returns the source node.
    319     ///
    320     Node source() const {
    321       return _source;
    322     }
    323 
    324     /// \brief Returns the target node.
    325     ///
    326     /// Returns the target node.
    327     ///
    328     Node target() const {
    329       return _target;
    330     }
    331 
    332     /// \brief Returns a reference to capacity map.
    333     ///
    334     /// Returns a reference to capacity map.
    335     ///
    336     const CapacityMap &capacityMap() const {
    337       return *_capacity;
    338     }
    339      
    340     /// \brief Returns a reference to flow map.
    341     ///
    342     /// Returns a reference to flow map.
    343     ///
    344     const FlowMap &flowMap() const {
    345       return *_flow;
    346     }
    347 
    348     /// \brief Returns the tolerance used by algorithm.
    349     ///
    350     /// Returns the tolerance used by algorithm.
    351     const Tolerance& tolerance() const {
    352       return tolerance;
    353     }
    354    
    355   private:
    356    
    357     const Graph& _graph;
    358     const CapacityMap& _capacity;
    359     FlowMap& _flow;
    360     Tolerance _tolerance;
    361    
    362     ResGraph _resgraph;
    363     Node _source, _target;
    364     Number _value;
    365    
     511    void minCutMap(CutMap& cutMap) const {
     512      for (NodeIt n(_graph); n != INVALID; ++n) {
     513        cutMap.set(n, (*_pred)[n] != INVALID);
     514      }
     515      cutMap.set(_source, true);
     516    }   
     517
     518    /// @}
     519
    366520  };
    367521
Note: See TracChangeset for help on using the changeset viewer.