COIN-OR::LEMON - Graph Library

Changeset 593:d6b40ebb2617 in lemon


Ignore:
Timestamp:
03/04/09 14:56:09 (9 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Message:

Doc improvements in GomoryHu? (#66)
And make init() and start() private + bug fix in the test file.

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/gomory_hu.h

    r592 r593  
    3737  /// \brief Gomory-Hu cut tree algorithm 
    3838  /// 
    39   /// The Gomory-Hu tree is a tree on the node set of the graph, but it 
    40   /// may contain edges which are not in the original digraph. It has the 
     39  /// The Gomory-Hu tree is a tree on the node set of a given graph, but it 
     40  /// may contain edges which are not in the original graph. It has the 
    4141  /// property that the minimum capacity edge of the path between two nodes  
    42   /// in this tree has the same weight as the minimum cut in the digraph 
     42  /// in this tree has the same weight as the minimum cut in the graph 
    4343  /// between these nodes. Moreover the components obtained by removing 
    4444  /// this edge from the tree determine the corresponding minimum cut. 
     
    5454  ///  
    5555  /// The members \c minCutMap() and \c minCutValue() calculate 
    56   /// the minimum cut and the minimum cut value between any two node 
    57   /// in the digraph. You can also list (iterate on) the nodes and the 
    58   /// edges of the cuts using MinCutNodeIt and MinCutEdgeIt. 
     56  /// the minimum cut and the minimum cut value between any two nodes 
     57  /// in the graph. You can also list (iterate on) the nodes and the 
     58  /// edges of the cuts using \c MinCutNodeIt and \c MinCutEdgeIt. 
    5959  /// 
    60   /// \tparam GR The undirected graph data structure the algorithm will run on 
    61   /// \tparam CAP type of the EdgeMap describing the Edge capacities. 
    62   /// it is typename GR::template EdgeMap<int> by default. 
     60  /// \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. 
     63#ifdef DOXYGEN 
    6364  template <typename GR, 
    64             typename CAP = typename GR::template EdgeMap<int> 
    65             > 
     65            typename CAP> 
     66#else 
     67  template <typename GR, 
     68            typename CAP = typename GR::template EdgeMap<int> > 
     69#endif 
    6670  class GomoryHu { 
    6771  public: 
     
    6973    /// The graph type 
    7074    typedef GR Graph; 
    71     /// The type if the edge capacity map 
     75    /// The type of the edge capacity map 
    7276    typedef CAP Capacity; 
    7377    /// The value type of capacities 
     
    115119    /// 
    116120    /// Constructor 
    117     /// \param graph The graph the algorithm will run on. 
    118     /// \param capacity The capacity map. 
     121    /// \param graph The undirected graph the algorithm runs on. 
     122    /// \param capacity The edge capacity map. 
    119123    GomoryHu(const Graph& graph, const Capacity& capacity)  
    120124      : _graph(graph), _capacity(capacity), 
     
    132136    } 
    133137 
    134     // \brief Initialize the internal data structures. 
    135     // 
    136     // This function initializes the internal data structures. 
    137     // 
     138  private: 
     139   
     140    // Initialize the internal data structures 
    138141    void init() { 
    139142      createStructures(); 
     
    149152 
    150153 
    151     // \brief Start the algorithm 
    152     // 
    153     // This function starts the algorithm. 
    154     // 
    155     // \pre \ref init() must be called before using this function. 
    156     // 
     154    // Start the algorithm 
    157155    void start() { 
    158156      Preflow<Graph, Capacity> fa(_graph, _capacity, _root, INVALID); 
     
    199197    } 
    200198 
     199  public: 
     200 
    201201    ///\name Execution Control 
    202202  
     
    216216    ///The results of the algorithm can be obtained using these 
    217217    ///functions.\n 
    218     ///The \ref run() "run()" should be called before using them.\n 
    219     ///See also MinCutNodeIt and MinCutEdgeIt 
     218    ///\ref run() "run()" should be called before using them.\n 
     219    ///See also \ref MinCutNodeIt and \ref MinCutEdgeIt. 
    220220 
    221221    ///@{ 
     
    251251    /// This function returns the minimum cut value between two nodes. The 
    252252    /// algorithm finds the nearest common ancestor in the Gomory-Hu 
    253     /// tree and calculates the minimum weight arc on the paths to 
     253    /// tree and calculates the minimum weight edge on the paths to 
    254254    /// the ancestor. 
    255255    Value minCutValue(const Node& s, const Node& t) const { 
     
    272272    /// 
    273273    /// This function returns the minimum cut between the nodes \c s and \c t 
    274     /// the \r cutMap parameter by setting the nodes in the component of 
    275     /// \c \s to true and the other nodes to false. 
    276     /// 
    277     /// The \c cutMap should be \ref concepts::ReadWriteMap 
    278     /// "ReadWriteMap". 
    279     /// 
    280     /// For higher level interfaces, see MinCutNodeIt and MinCutEdgeIt 
     274    /// in the \c cutMap parameter by setting the nodes in the component of 
     275    /// \c s to \c true and the other nodes to \c false. 
     276    /// 
     277    /// For higher level interfaces, see MinCutNodeIt and MinCutEdgeIt. 
    281278    template <typename CutMap> 
    282     Value minCutMap(const Node& s, ///< Base node 
     279    Value minCutMap(const Node& s, ///< The base node. 
    283280                    const Node& t, 
    284                     ///< The node you want to separate from Node s. 
     281                    ///< The node you want to separate from node \c s. 
    285282                    CutMap& cutMap 
    286                     ///< The cut will be return in this map. 
    287                     /// It must be a \c bool \ref concepts::ReadWriteMap 
    288                     /// "ReadWriteMap" on the graph nodes. 
     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. 
    289287                    ) const { 
    290288      Node sn = s, tn = t; 
     
    349347    /// GomoruHu<Graph> gom(g, capacities); 
    350348    /// gom.run(); 
    351     /// int sum=0; 
    352     /// for(GomoruHu<Graph>::MinCutNodeIt n(gom,s,t);n!=INVALID;++n) ++sum; 
     349    /// int cnt=0; 
     350    /// for(GomoruHu<Graph>::MinCutNodeIt n(gom,s,t); n!=INVALID; ++n) ++cnt; 
    353351    /// \endcode 
    354352    class MinCutNodeIt 
     
    360358      /// Constructor 
    361359 
    362       /// Constructor 
     360      /// Constructor. 
    363361      /// 
    364362      MinCutNodeIt(GomoryHu const &gomory, 
    365363                   ///< The GomoryHu class. You must call its 
    366364                   ///  run() method 
    367                    ///  before initializing this iterator 
    368                    const Node& s, ///< Base node 
     365                   ///  before initializing this iterator. 
     366                   const Node& s, ///< The base node. 
    369367                   const Node& t, 
    370                    ///< The node you want to separate from Node s. 
     368                   ///< The node you want to separate from node \c s. 
    371369                   bool side=true 
    372370                   ///< If it is \c true (default) then the iterator lists 
     
    399397            ++_node_it) {} 
    400398      } 
    401       /// Conversion to Node 
    402  
    403       /// Conversion to Node 
     399      /// Conversion to \c Node 
     400 
     401      /// Conversion to \c Node. 
    404402      /// 
    405403      operator typename Graph::Node() const 
     
    411409      /// Next node 
    412410 
    413       /// Next node 
     411      /// Next node. 
    414412      /// 
    415413      MinCutNodeIt &operator++() 
     
    420418      /// Postfix incrementation 
    421419 
    422       /// Postfix incrementation 
     420      /// Postfix incrementation. 
    423421      /// 
    424422      /// \warning This incrementation 
    425       /// returns a \c Node, not a \ref MinCutNodeIt, as one may 
     423      /// returns a \c Node, not a \c MinCutNodeIt, as one may 
    426424      /// expect. 
    427425      typename Graph::Node operator++(int) 
     
    447445    /// gom.run(); 
    448446    /// int value=0; 
    449     /// for(GomoruHu<Graph>::MinCutEdgeIt e(gom,s,t);e!=INVALID;++e) 
     447    /// for(GomoruHu<Graph>::MinCutEdgeIt e(gom,s,t); e!=INVALID; ++e) 
    450448    ///   value+=capacities[e]; 
    451449    /// \endcode 
    452450    /// the result will be the same as it is returned by 
    453     /// \ref GomoryHu::minCostValue() "gom.minCostValue(s,t)" 
     451    /// \ref GomoryHu::minCutValue() "gom.minCutValue(s,t)" 
    454452    class MinCutEdgeIt 
    455453    { 
     
    474472                   ///< The GomoryHu class. You must call its 
    475473                   ///  run() method 
    476                    ///  before initializing this iterator 
    477                    const Node& s,  ///< Base node 
     474                   ///  before initializing this iterator. 
     475                   const Node& s,  ///< The base node. 
    478476                   const Node& t, 
    479                    ///< The node you want to separate from Node s. 
     477                   ///< The node you want to separate from node \c s. 
    480478                   bool side=true 
    481479                   ///< If it is \c true (default) then the listed arcs 
     
    505503        while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step(); 
    506504      } 
    507       /// Conversion to Arc 
    508  
    509       /// Conversion to Arc 
     505      /// Conversion to \c Arc 
     506 
     507      /// Conversion to \c Arc. 
    510508      /// 
    511509      operator typename Graph::Arc() const 
     
    513511        return _arc_it; 
    514512      } 
    515       /// Conversion to Edge 
    516  
    517       /// Conversion to Edge 
     513      /// Conversion to \c Edge 
     514 
     515      /// Conversion to \c Edge. 
    518516      /// 
    519517      operator typename Graph::Edge() const 
     
    525523      /// Next edge 
    526524 
    527       /// Next edge 
     525      /// Next edge. 
    528526      /// 
    529527      MinCutEdgeIt &operator++() 
     
    535533      /// Postfix incrementation 
    536534       
    537       /// Postfix incrementation 
     535      /// Postfix incrementation. 
    538536      /// 
    539537      /// \warning This incrementation 
    540       /// returns a \c Arc, not a \ref MinCutEdgeIt, as one may 
    541       /// expect. 
     538      /// returns an \c Arc, not a \c MinCutEdgeIt, as one may expect. 
    542539      typename Graph::Arc operator++(int) 
    543540      { 
  • test/gomory_hu_test.cc

    r592 r593  
    6262 
    6363  GomoryHu<Graph> ght(graph, capacity); 
    64   ght.init(); 
    6564  ght.run(); 
    6665 
Note: See TracChangeset for help on using the changeset viewer.