lemon/gomory_hu.h
changeset 779 c160bf9f18ef
parent 581 aa1804409f29
child 713 4ac30454f1c1
equal deleted inserted replaced
2:72803c0e12f5 3:02c9547e1525
    40   /// may contain edges which are not in the original graph. It has the
    40   /// may contain edges which are not in the original graph. It has the
    41   /// property that the minimum capacity edge of the path between two nodes 
    41   /// 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 graph
    42   /// in this tree has the same weight as the minimum cut in the graph
    43   /// between these nodes. Moreover the components obtained by removing
    43   /// between these nodes. Moreover the components obtained by removing
    44   /// this edge from the tree determine the corresponding minimum cut.
    44   /// this edge from the tree determine the corresponding minimum cut.
    45   ///
       
    46   /// Therefore once this tree is computed, the minimum cut between any pair
    45   /// Therefore once this tree is computed, the minimum cut between any pair
    47   /// of nodes can easily be obtained.
    46   /// of nodes can easily be obtained.
    48   /// 
    47   /// 
    49   /// The algorithm calculates \e n-1 distinct minimum cuts (currently with
    48   /// The algorithm calculates \e n-1 distinct minimum cuts (currently with
    50   /// the \ref Preflow algorithm), therefore the algorithm has
    49   /// the \ref Preflow algorithm), thus it has \f$O(n^3\sqrt{e})\f$ overall
    51   /// \f$(O(n^3\sqrt{e})\f$ overall time complexity. It calculates a
    50   /// time complexity. It calculates a rooted Gomory-Hu tree.
    52   /// rooted Gomory-Hu tree, its structure and the weights can be obtained
    51   /// The structure of the tree and the edge weights can be
    53   /// by \c predNode(), \c predValue() and \c rootDist().
    52   /// obtained using \c predNode(), \c predValue() and \c rootDist().
    54   /// 
    53   /// The functions \c minCutMap() and \c minCutValue() calculate
    55   /// The members \c minCutMap() and \c minCutValue() calculate
       
    56   /// the minimum cut and the minimum cut value between any two nodes
    54   /// 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
    55   /// in the graph. You can also list (iterate on) the nodes and the
    58   /// edges of the cuts using \c MinCutNodeIt and \c MinCutEdgeIt.
    56   /// edges of the cuts using \c MinCutNodeIt and \c MinCutEdgeIt.
    59   ///
    57   ///
    60   /// \tparam GR The type of the undirected graph the algorithm runs on.
    58   /// \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.
    59   /// \tparam CAP The type of the edge map containing the capacities.
    62   /// It is \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>" by default.
    60   /// The default map type is \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>".
    63 #ifdef DOXYGEN
    61 #ifdef DOXYGEN
    64   template <typename GR,
    62   template <typename GR,
    65 	    typename CAP>
    63 	    typename CAP>
    66 #else
    64 #else
    67   template <typename GR,
    65   template <typename GR,
    68 	    typename CAP = typename GR::template EdgeMap<int> >
    66 	    typename CAP = typename GR::template EdgeMap<int> >
    69 #endif
    67 #endif
    70   class GomoryHu {
    68   class GomoryHu {
    71   public:
    69   public:
    72 
    70 
    73     /// The graph type
    71     /// The graph type of the algorithm
    74     typedef GR Graph;
    72     typedef GR Graph;
    75     /// The type of the edge capacity map
    73     /// The capacity map type of the algorithm
    76     typedef CAP Capacity;
    74     typedef CAP Capacity;
    77     /// The value type of capacities
    75     /// The value type of capacities
    78     typedef typename Capacity::Value Value;
    76     typedef typename Capacity::Value Value;
    79     
    77     
    80   private:
    78   private:
   115   
   113   
   116   public:
   114   public:
   117 
   115 
   118     /// \brief Constructor
   116     /// \brief Constructor
   119     ///
   117     ///
   120     /// Constructor
   118     /// Constructor.
   121     /// \param graph The undirected graph the algorithm runs on.
   119     /// \param graph The undirected graph the algorithm runs on.
   122     /// \param capacity The edge capacity map.
   120     /// \param capacity The edge capacity map.
   123     GomoryHu(const Graph& graph, const Capacity& capacity) 
   121     GomoryHu(const Graph& graph, const Capacity& capacity) 
   124       : _graph(graph), _capacity(capacity),
   122       : _graph(graph), _capacity(capacity),
   125 	_pred(0), _weight(0), _order(0) 
   123 	_pred(0), _weight(0), _order(0) 
   128     }
   126     }
   129 
   127 
   130 
   128 
   131     /// \brief Destructor
   129     /// \brief Destructor
   132     ///
   130     ///
   133     /// Destructor
   131     /// Destructor.
   134     ~GomoryHu() {
   132     ~GomoryHu() {
   135       destroyStructures();
   133       destroyStructures();
   136     }
   134     }
   137 
   135 
   138   private:
   136   private:
   213     /// @}
   211     /// @}
   214 
   212 
   215     ///\name Query Functions
   213     ///\name Query Functions
   216     ///The results of the algorithm can be obtained using these
   214     ///The results of the algorithm can be obtained using these
   217     ///functions.\n
   215     ///functions.\n
   218     ///\ref run() "run()" should be called before using them.\n
   216     ///\ref run() should be called before using them.\n
   219     ///See also \ref MinCutNodeIt and \ref MinCutEdgeIt.
   217     ///See also \ref MinCutNodeIt and \ref MinCutEdgeIt.
   220 
   218 
   221     ///@{
   219     ///@{
   222 
   220 
   223     /// \brief Return the predecessor node in the Gomory-Hu tree.
   221     /// \brief Return the predecessor node in the Gomory-Hu tree.
   224     ///
   222     ///
   225     /// This function returns the predecessor node in the Gomory-Hu tree.
   223     /// This function returns the predecessor node of the given node
   226     /// If the node is
   224     /// in the Gomory-Hu tree.
   227     /// the root of the Gomory-Hu tree, then it returns \c INVALID.
   225     /// If \c node is the root of the tree, then it returns \c INVALID.
   228     Node predNode(const Node& node) {
   226     ///
       
   227     /// \pre \ref run() must be called before using this function.
       
   228     Node predNode(const Node& node) const {
   229       return (*_pred)[node];
   229       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];
       
   238     }
   230     }
   239 
   231 
   240     /// \brief Return the weight of the predecessor edge in the
   232     /// \brief Return the weight of the predecessor edge in the
   241     /// Gomory-Hu tree.
   233     /// Gomory-Hu tree.
   242     ///
   234     ///
   243     /// This function returns the weight of the predecessor edge in the
   235     /// This function returns the weight of the predecessor edge of the 
   244     /// Gomory-Hu tree.  If the node is the root, the result is undefined.
   236     /// given node in the Gomory-Hu tree.
   245     Value predValue(const Node& node) {
   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 {
   246       return (*_weight)[node];
   241       return (*_weight)[node];
   247     }
   242     }
   248 
   243 
       
   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 
   249     /// \brief Return the minimum cut value between two nodes
   254     /// \brief Return the minimum cut value between two nodes
   250     ///
   255     ///
   251     /// This function returns the minimum cut value between two nodes. The
   256     /// This function returns the minimum cut value between the nodes
   252     /// algorithm finds the nearest common ancestor in the Gomory-Hu
   257     /// \c s and \c t. 
   253     /// tree and calculates the minimum weight edge on the paths to
   258     /// It finds the nearest common ancestor of the given nodes in the
   254     /// the ancestor.
   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.
   255     Value minCutValue(const Node& s, const Node& t) const {
   263     Value minCutValue(const Node& s, const Node& t) const {
   256       Node sn = s, tn = t;
   264       Node sn = s, tn = t;
   257       Value value = std::numeric_limits<Value>::max();
   265       Value value = std::numeric_limits<Value>::max();
   258       
   266       
   259       while (sn != tn) {
   267       while (sn != tn) {
   272     ///
   280     ///
   273     /// This function returns the minimum cut between the nodes \c s and \c t
   281     /// This function returns the minimum cut between the nodes \c s and \c t
   274     /// in the \c cutMap parameter by setting the nodes in the component of
   282     /// 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.
   283     /// \c s to \c true and the other nodes to \c false.
   276     ///
   284     ///
   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.
   278     template <typename CutMap>
   296     template <typename CutMap>
   279     Value minCutMap(const Node& s, ///< The base node.
   297     Value minCutMap(const Node& s, ///< 
   280                     const Node& t,
   298                     const Node& t,
   281                     ///< The node you want to separate from node \c s.
   299                     ///< 
   282                     CutMap& cutMap
   300                     CutMap& cutMap
   283                     ///< The cut will be returned in this map.
   301                     ///< 
   284                     /// It must be a \c bool (or convertible) 
       
   285                     /// \ref concepts::ReadWriteMap "ReadWriteMap"
       
   286                     /// on the graph nodes.
       
   287                     ) const {
   302                     ) const {
   288       Node sn = s, tn = t;
   303       Node sn = s, tn = t;
   289       bool s_root=false;
   304       bool s_root=false;
   290       Node rn = INVALID;
   305       Node rn = INVALID;
   291       Value value = std::numeric_limits<Value>::max();
   306       Value value = std::numeric_limits<Value>::max();
   336     friend class MinCutNodeIt;
   351     friend class MinCutNodeIt;
   337 
   352 
   338     /// Iterate on the nodes of a minimum cut
   353     /// Iterate on the nodes of a minimum cut
   339     
   354     
   340     /// This iterator class lists the nodes of a minimum cut found by
   355     /// 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
   342     /// and call its \ref GomoryHu::run() "run()" method.
   357     /// and call its \ref GomoryHu::run() "run()" method.
   343     ///
   358     ///
   344     /// This example counts the nodes in the minimum cut separating \c s from
   359     /// This example counts the nodes in the minimum cut separating \c s from
   345     /// \c t.
   360     /// \c t.
   346     /// \code
   361     /// \code
   433     friend class MinCutEdgeIt;
   448     friend class MinCutEdgeIt;
   434     
   449     
   435     /// Iterate on the edges of a minimum cut
   450     /// Iterate on the edges of a minimum cut
   436     
   451     
   437     /// This iterator class lists the edges of a minimum cut found by
   452     /// 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
   439     /// and call its \ref GomoryHu::run() "run()" method.
   454     /// and call its \ref GomoryHu::run() "run()" method.
   440     ///
   455     ///
   441     /// This example computes the value of the minimum cut separating \c s from
   456     /// This example computes the value of the minimum cut separating \c s from
   442     /// \c t.
   457     /// \c t.
   443     /// \code
   458     /// \code
   445     /// gom.run();
   460     /// gom.run();
   446     /// int value=0;
   461     /// int value=0;
   447     /// for(GomoruHu<Graph>::MinCutEdgeIt e(gom,s,t); e!=INVALID; ++e)
   462     /// for(GomoruHu<Graph>::MinCutEdgeIt e(gom,s,t); e!=INVALID; ++e)
   448     ///   value+=capacities[e];
   463     ///   value+=capacities[e];
   449     /// \endcode
   464     /// \endcode
   450     /// the result will be the same as it is returned by
   465     /// The result will be the same as the value returned by
   451     /// \ref GomoryHu::minCutValue() "gom.minCutValue(s,t)"
   466     /// \ref GomoryHu::minCutValue() "gom.minCutValue(s,t)".
   452     class MinCutEdgeIt
   467     class MinCutEdgeIt
   453     {
   468     {
   454       bool _side;
   469       bool _side;
   455       const Graph &_graph;
   470       const Graph &_graph;
   456       typename Graph::NodeIt _node_it;
   471       typename Graph::NodeIt _node_it;
   466               _arc_it=typename Graph::OutArcIt(_graph,_node_it);
   481               _arc_it=typename Graph::OutArcIt(_graph,_node_it);
   467           }
   482           }
   468       }
   483       }
   469       
   484       
   470     public:
   485     public:
       
   486       /// Constructor
       
   487 
       
   488       /// Constructor.
       
   489       ///
   471       MinCutEdgeIt(GomoryHu const &gomory,
   490       MinCutEdgeIt(GomoryHu const &gomory,
   472                    ///< The GomoryHu class. You must call its
   491                    ///< The GomoryHu class. You must call its
   473                    ///  run() method
   492                    ///  run() method
   474                    ///  before initializing this iterator.
   493                    ///  before initializing this iterator.
   475                    const Node& s,  ///< The base node.
   494                    const Node& s,  ///< The base node.
   476                    const Node& t,
   495                    const Node& t,
   477                    ///< The node you want to separate from node \c s.
   496                    ///< The node you want to separate from node \c s.
   478                    bool side=true
   497                    bool side=true
   479                    ///< If it is \c true (default) then the listed arcs
   498                    ///< If it is \c true (default) then the listed arcs
   480                    ///  will be oriented from the
   499                    ///  will be oriented from the
   481                    ///  the nodes of the component containing \c s,
   500                    ///  nodes of the component containing \c s,
   482                    ///  otherwise they will be oriented in the opposite
   501                    ///  otherwise they will be oriented in the opposite
   483                    ///  direction.
   502                    ///  direction.
   484                    )
   503                    )
   485         : _graph(gomory._graph), _cut(_graph)
   504         : _graph(gomory._graph), _cut(_graph)
   486       {
   505       {