COIN-OR::LEMON - Graph Library

Changeset 596:293551ad254f in lemon-1.2 for lemon/gomory_hu.h


Ignore:
Timestamp:
04/15/09 09:37:51 (11 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Improvements and fixes for the minimum cut algorithms (#264)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/gomory_hu.h

    r581 r596  
    4343  /// between these nodes. Moreover the components obtained by removing
    4444  /// this edge from the tree determine the corresponding minimum cut.
    45   ///
    4645  /// Therefore once this tree is computed, the minimum cut between any pair
    4746  /// of nodes can easily be obtained.
    4847  ///
    4948  /// The algorithm calculates \e n-1 distinct minimum cuts (currently with
    50   /// the \ref Preflow algorithm), therefore the algorithm has
    51   /// \f$(O(n^3\sqrt{e})\f$ overall time complexity. It calculates a
    52   /// rooted Gomory-Hu tree, its structure and the weights can be obtained
    53   /// by \c predNode(), \c predValue() and \c rootDist().
    54   ///
    55   /// The members \c minCutMap() and \c minCutValue() calculate
     49  /// the \ref Preflow algorithm), thus it has \f$O(n^3\sqrt{e})\f$ overall
     50  /// time complexity. It calculates a rooted Gomory-Hu tree.
     51  /// The structure of the tree and the edge weights can be
     52  /// obtained using \c predNode(), \c predValue() and \c rootDist().
     53  /// The functions \c minCutMap() and \c minCutValue() calculate
    5654  /// the minimum cut and the minimum cut value between any two nodes
    5755  /// in the graph. You can also list (iterate on) the nodes and the
     
    5957  ///
    6058  /// \tparam GR The type of the undirected graph the algorithm runs on.
    61   /// \tparam CAP The type of the edge map describing the edge capacities.
    62   /// It is \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>" by default.
     59  /// \tparam CAP The type of the edge map containing the capacities.
     60  /// The default map type is \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>".
    6361#ifdef DOXYGEN
    6462  template <typename GR,
     
    7169  public:
    7270
    73     /// The graph type
     71    /// The graph type of the algorithm
    7472    typedef GR Graph;
    75     /// The type of the edge capacity map
     73    /// The capacity map type of the algorithm
    7674    typedef CAP Capacity;
    7775    /// The value type of capacities
     
    118116    /// \brief Constructor
    119117    ///
    120     /// Constructor
     118    /// Constructor.
    121119    /// \param graph The undirected graph the algorithm runs on.
    122120    /// \param capacity The edge capacity map.
     
    131129    /// \brief Destructor
    132130    ///
    133     /// Destructor
     131    /// Destructor.
    134132    ~GomoryHu() {
    135133      destroyStructures();
     
    216214    ///The results of the algorithm can be obtained using these
    217215    ///functions.\n
    218     ///\ref run() "run()" should be called before using them.\n
     216    ///\ref run() should be called before using them.\n
    219217    ///See also \ref MinCutNodeIt and \ref MinCutEdgeIt.
    220218
     
    223221    /// \brief Return the predecessor node in the Gomory-Hu tree.
    224222    ///
    225     /// This function returns the predecessor node in the Gomory-Hu tree.
    226     /// If the node is
    227     /// the root of the Gomory-Hu tree, then it returns \c INVALID.
    228     Node predNode(const Node& node) {
     223    /// This function returns the predecessor node of the given node
     224    /// in the Gomory-Hu tree.
     225    /// If \c node is the root of the tree, then it returns \c INVALID.
     226    ///
     227    /// \pre \ref run() must be called before using this function.
     228    Node predNode(const Node& node) const {
    229229      return (*_pred)[node];
    230     }
    231 
    232     /// \brief Return the distance from the root node in the Gomory-Hu tree.
    233     ///
    234     /// This function returns the distance of \c node from the root node
    235     /// in the Gomory-Hu tree.
    236     int rootDist(const Node& node) {
    237       return (*_order)[node];
    238230    }
    239231
     
    241233    /// Gomory-Hu tree.
    242234    ///
    243     /// This function returns the weight of the predecessor edge in the
    244     /// Gomory-Hu tree.  If the node is the root, the result is undefined.
    245     Value predValue(const Node& node) {
     235    /// This function returns the weight of the predecessor edge of the
     236    /// given node in the Gomory-Hu tree.
     237    /// If \c node is the root of the tree, the result is undefined.
     238    ///
     239    /// \pre \ref run() must be called before using this function.
     240    Value predValue(const Node& node) const {
    246241      return (*_weight)[node];
    247242    }
    248243
     244    /// \brief Return the distance from the root node in the Gomory-Hu tree.
     245    ///
     246    /// This function returns the distance of the given node from the root
     247    /// node in the Gomory-Hu tree.
     248    ///
     249    /// \pre \ref run() must be called before using this function.
     250    int rootDist(const Node& node) const {
     251      return (*_order)[node];
     252    }
     253
    249254    /// \brief Return the minimum cut value between two nodes
    250255    ///
    251     /// This function returns the minimum cut value between two nodes. The
    252     /// algorithm finds the nearest common ancestor in the Gomory-Hu
    253     /// tree and calculates the minimum weight edge on the paths to
    254     /// the ancestor.
     256    /// This function returns the minimum cut value between the nodes
     257    /// \c s and \c t.
     258    /// It finds the nearest common ancestor of the given nodes in the
     259    /// Gomory-Hu tree and calculates the minimum weight edge on the
     260    /// paths to the ancestor.
     261    ///
     262    /// \pre \ref run() must be called before using this function.
    255263    Value minCutValue(const Node& s, const Node& t) const {
    256264      Node sn = s, tn = t;
     
    275283    /// \c s to \c true and the other nodes to \c false.
    276284    ///
    277     /// For higher level interfaces, see MinCutNodeIt and MinCutEdgeIt.
     285    /// For higher level interfaces see MinCutNodeIt and MinCutEdgeIt.
     286    ///
     287    /// \param s The base node.
     288    /// \param t The node you want to separate from node \c s.
     289    /// \param cutMap The cut will be returned in this map.
     290    /// It must be a \c bool (or convertible) \ref concepts::ReadWriteMap
     291    /// "ReadWriteMap" on the graph nodes.
     292    ///
     293    /// \return The value of the minimum cut between \c s and \c t.
     294    ///
     295    /// \pre \ref run() must be called before using this function.
    278296    template <typename CutMap>
    279     Value minCutMap(const Node& s, ///< The base node.
     297    Value minCutMap(const Node& s, ///<
    280298                    const Node& t,
    281                     ///< The node you want to separate from node \c s.
     299                    ///<
    282300                    CutMap& cutMap
    283                     ///< The cut will be returned in this map.
    284                     /// It must be a \c bool (or convertible)
    285                     /// \ref concepts::ReadWriteMap "ReadWriteMap"
    286                     /// on the graph nodes.
     301                    ///<
    287302                    ) const {
    288303      Node sn = s, tn = t;
     
    339354   
    340355    /// This iterator class lists the nodes of a minimum cut found by
    341     /// GomoryHu. Before using it, you must allocate a GomoryHu class,
     356    /// GomoryHu. Before using it, you must allocate a GomoryHu class
    342357    /// and call its \ref GomoryHu::run() "run()" method.
    343358    ///
     
    436451   
    437452    /// This iterator class lists the edges of a minimum cut found by
    438     /// GomoryHu. Before using it, you must allocate a GomoryHu class,
     453    /// GomoryHu. Before using it, you must allocate a GomoryHu class
    439454    /// and call its \ref GomoryHu::run() "run()" method.
    440455    ///
     
    448463    ///   value+=capacities[e];
    449464    /// \endcode
    450     /// the result will be the same as it is returned by
    451     /// \ref GomoryHu::minCutValue() "gom.minCutValue(s,t)"
     465    /// The result will be the same as the value returned by
     466    /// \ref GomoryHu::minCutValue() "gom.minCutValue(s,t)".
    452467    class MinCutEdgeIt
    453468    {
     
    469484     
    470485    public:
     486      /// Constructor
     487
     488      /// Constructor.
     489      ///
    471490      MinCutEdgeIt(GomoryHu const &gomory,
    472491                   ///< The GomoryHu class. You must call its
     
    479498                   ///< If it is \c true (default) then the listed arcs
    480499                   ///  will be oriented from the
    481                    ///  the nodes of the component containing \c s,
     500                   ///  nodes of the component containing \c s,
    482501                   ///  otherwise they will be oriented in the opposite
    483502                   ///  direction.
Note: See TracChangeset for help on using the changeset viewer.