lemon/gomory_hu.h
changeset 577 5563527bcc8d
parent 545 e72bacfea6b7
child 581 aa1804409f29
equal deleted inserted replaced
0:3d1f90a60bc6 1:25aa2f18c735
    34 
    34 
    35   /// \ingroup min_cut
    35   /// \ingroup min_cut
    36   ///
    36   ///
    37   /// \brief Gomory-Hu cut tree algorithm
    37   /// \brief Gomory-Hu cut tree algorithm
    38   ///
    38   ///
    39   /// The Gomory-Hu tree is a tree on the node set of the graph, but it
    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 digraph. 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 digraph
    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   ///
    45   ///
    46   /// Therefore once this tree is computed, the minimum cut between any pair
    46   /// Therefore once this tree is computed, the minimum cut between any pair
    47   /// of nodes can easily be obtained.
    47   /// of nodes can easily be obtained.
    51   /// \f$(O(n^3\sqrt{e})\f$ overall time complexity. It calculates a
    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
    52   /// rooted Gomory-Hu tree, its structure and the weights can be obtained
    53   /// by \c predNode(), \c predValue() and \c rootDist().
    53   /// by \c predNode(), \c predValue() and \c rootDist().
    54   /// 
    54   /// 
    55   /// The members \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 node
    56   /// the minimum cut and the minimum cut value between any two nodes
    57   /// in the digraph. You can also list (iterate on) the nodes and the
    57   /// in the graph. You can also list (iterate on) the nodes and the
    58   /// edges of the cuts using MinCutNodeIt and MinCutEdgeIt.
    58   /// edges of the cuts using \c MinCutNodeIt and \c MinCutEdgeIt.
    59   ///
    59   ///
    60   /// \tparam GR The undirected graph data structure the algorithm will run on
    60   /// \tparam GR The type of the undirected graph the algorithm runs on.
    61   /// \tparam CAP type of the EdgeMap describing the Edge capacities.
    61   /// \tparam CAP The type of the edge map describing the edge capacities.
    62   /// it is typename GR::template EdgeMap<int> by default.
    62   /// It is \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>" by default.
       
    63 #ifdef DOXYGEN
    63   template <typename GR,
    64   template <typename GR,
    64 	    typename CAP = typename GR::template EdgeMap<int>
    65 	    typename CAP>
    65             >
    66 #else
       
    67   template <typename GR,
       
    68 	    typename CAP = typename GR::template EdgeMap<int> >
       
    69 #endif
    66   class GomoryHu {
    70   class GomoryHu {
    67   public:
    71   public:
    68 
    72 
    69     /// The graph type
    73     /// The graph type
    70     typedef GR Graph;
    74     typedef GR Graph;
    71     /// The type if the edge capacity map
    75     /// The type of the edge capacity map
    72     typedef CAP Capacity;
    76     typedef CAP Capacity;
    73     /// The value type of capacities
    77     /// The value type of capacities
    74     typedef typename Capacity::Value Value;
    78     typedef typename Capacity::Value Value;
    75     
    79     
    76   private:
    80   private:
   112   public:
   116   public:
   113 
   117 
   114     /// \brief Constructor
   118     /// \brief Constructor
   115     ///
   119     ///
   116     /// Constructor
   120     /// Constructor
   117     /// \param graph The graph the algorithm will run on.
   121     /// \param graph The undirected graph the algorithm runs on.
   118     /// \param capacity The capacity map.
   122     /// \param capacity The edge capacity map.
   119     GomoryHu(const Graph& graph, const Capacity& capacity) 
   123     GomoryHu(const Graph& graph, const Capacity& capacity) 
   120       : _graph(graph), _capacity(capacity),
   124       : _graph(graph), _capacity(capacity),
   121 	_pred(0), _weight(0), _order(0) 
   125 	_pred(0), _weight(0), _order(0) 
   122     {
   126     {
   123       checkConcept<concepts::ReadMap<Edge, Value>, Capacity>();
   127       checkConcept<concepts::ReadMap<Edge, Value>, Capacity>();
   129     /// Destructor
   133     /// Destructor
   130     ~GomoryHu() {
   134     ~GomoryHu() {
   131       destroyStructures();
   135       destroyStructures();
   132     }
   136     }
   133 
   137 
   134     // \brief Initialize the internal data structures.
   138   private:
   135     //
   139   
   136     // This function initializes the internal data structures.
   140     // Initialize the internal data structures
   137     //
       
   138     void init() {
   141     void init() {
   139       createStructures();
   142       createStructures();
   140 
   143 
   141       _root = NodeIt(_graph);
   144       _root = NodeIt(_graph);
   142       for (NodeIt n(_graph); n != INVALID; ++n) {
   145       for (NodeIt n(_graph); n != INVALID; ++n) {
   146       _pred->set(_root, INVALID);
   149       _pred->set(_root, INVALID);
   147       _weight->set(_root, std::numeric_limits<Value>::max()); 
   150       _weight->set(_root, std::numeric_limits<Value>::max()); 
   148     }
   151     }
   149 
   152 
   150 
   153 
   151     // \brief Start the algorithm
   154     // Start the algorithm
   152     //
       
   153     // This function starts the algorithm.
       
   154     //
       
   155     // \pre \ref init() must be called before using this function.
       
   156     //
       
   157     void start() {
   155     void start() {
   158       Preflow<Graph, Capacity> fa(_graph, _capacity, _root, INVALID);
   156       Preflow<Graph, Capacity> fa(_graph, _capacity, _root, INVALID);
   159 
   157 
   160       for (NodeIt n(_graph); n != INVALID; ++n) {
   158       for (NodeIt n(_graph); n != INVALID; ++n) {
   161 	if (n == _root) continue;
   159 	if (n == _root) continue;
   196 	  st.pop_back();
   194 	  st.pop_back();
   197 	}
   195 	}
   198       }
   196       }
   199     }
   197     }
   200 
   198 
       
   199   public:
       
   200 
   201     ///\name Execution Control
   201     ///\name Execution Control
   202  
   202  
   203     ///@{
   203     ///@{
   204 
   204 
   205     /// \brief Run the Gomory-Hu algorithm.
   205     /// \brief Run the Gomory-Hu algorithm.
   213     /// @}
   213     /// @}
   214 
   214 
   215     ///\name Query Functions
   215     ///\name Query Functions
   216     ///The results of the algorithm can be obtained using these
   216     ///The results of the algorithm can be obtained using these
   217     ///functions.\n
   217     ///functions.\n
   218     ///The \ref run() "run()" should be called before using them.\n
   218     ///\ref run() "run()" should be called before using them.\n
   219     ///See also MinCutNodeIt and MinCutEdgeIt
   219     ///See also \ref MinCutNodeIt and \ref MinCutEdgeIt.
   220 
   220 
   221     ///@{
   221     ///@{
   222 
   222 
   223     /// \brief Return the predecessor node in the Gomory-Hu tree.
   223     /// \brief Return the predecessor node in the Gomory-Hu tree.
   224     ///
   224     ///
   248 
   248 
   249     /// \brief Return the minimum cut value between two nodes
   249     /// \brief Return the minimum cut value between two nodes
   250     ///
   250     ///
   251     /// This function returns the minimum cut value between two nodes. The
   251     /// This function returns the minimum cut value between two nodes. The
   252     /// algorithm finds the nearest common ancestor in the Gomory-Hu
   252     /// 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
   254     /// the ancestor.
   254     /// the ancestor.
   255     Value minCutValue(const Node& s, const Node& t) const {
   255     Value minCutValue(const Node& s, const Node& t) const {
   256       Node sn = s, tn = t;
   256       Node sn = s, tn = t;
   257       Value value = std::numeric_limits<Value>::max();
   257       Value value = std::numeric_limits<Value>::max();
   258       
   258       
   269     }
   269     }
   270 
   270 
   271     /// \brief Return the minimum cut between two nodes
   271     /// \brief Return the minimum cut between two nodes
   272     ///
   272     ///
   273     /// This function returns the minimum cut between the nodes \c s and \c t
   273     /// 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
   274     /// in the \c cutMap parameter by setting the nodes in the component of
   275     /// \c \s to true and the other nodes to false.
   275     /// \c s to \c true and the other nodes to \c false.
   276     ///
   276     ///
   277     /// The \c cutMap should be \ref concepts::ReadWriteMap
   277     /// For higher level interfaces, see MinCutNodeIt and MinCutEdgeIt.
   278     /// "ReadWriteMap".
       
   279     ///
       
   280     /// For higher level interfaces, see MinCutNodeIt and MinCutEdgeIt
       
   281     template <typename CutMap>
   278     template <typename CutMap>
   282     Value minCutMap(const Node& s, ///< Base node
   279     Value minCutMap(const Node& s, ///< The base node.
   283                     const Node& t,
   280                     const Node& t,
   284                     ///< The node you want to separate from Node s.
   281                     ///< The node you want to separate from node \c s.
   285                     CutMap& cutMap
   282                     CutMap& cutMap
   286                     ///< The cut will be return in this map.
   283                     ///< The cut will be returned in this map.
   287                     /// It must be a \c bool \ref concepts::ReadWriteMap
   284                     /// It must be a \c bool (or convertible) 
   288                     /// "ReadWriteMap" on the graph nodes.
   285                     /// \ref concepts::ReadWriteMap "ReadWriteMap"
       
   286                     /// on the graph nodes.
   289                     ) const {
   287                     ) const {
   290       Node sn = s, tn = t;
   288       Node sn = s, tn = t;
   291       bool s_root=false;
   289       bool s_root=false;
   292       Node rn = INVALID;
   290       Node rn = INVALID;
   293       Value value = std::numeric_limits<Value>::max();
   291       Value value = std::numeric_limits<Value>::max();
   346     /// This example counts the nodes in the minimum cut separating \c s from
   344     /// This example counts the nodes in the minimum cut separating \c s from
   347     /// \c t.
   345     /// \c t.
   348     /// \code
   346     /// \code
   349     /// GomoruHu<Graph> gom(g, capacities);
   347     /// GomoruHu<Graph> gom(g, capacities);
   350     /// gom.run();
   348     /// gom.run();
   351     /// int sum=0;
   349     /// int cnt=0;
   352     /// for(GomoruHu<Graph>::MinCutNodeIt n(gom,s,t);n!=INVALID;++n) ++sum;
   350     /// for(GomoruHu<Graph>::MinCutNodeIt n(gom,s,t); n!=INVALID; ++n) ++cnt;
   353     /// \endcode
   351     /// \endcode
   354     class MinCutNodeIt
   352     class MinCutNodeIt
   355     {
   353     {
   356       bool _side;
   354       bool _side;
   357       typename Graph::NodeIt _node_it;
   355       typename Graph::NodeIt _node_it;
   358       typename Graph::template NodeMap<bool> _cut;
   356       typename Graph::template NodeMap<bool> _cut;
   359     public:
   357     public:
   360       /// Constructor
   358       /// Constructor
   361 
   359 
   362       /// Constructor
   360       /// Constructor.
   363       ///
   361       ///
   364       MinCutNodeIt(GomoryHu const &gomory,
   362       MinCutNodeIt(GomoryHu const &gomory,
   365                    ///< The GomoryHu class. You must call its
   363                    ///< The GomoryHu class. You must call its
   366                    ///  run() method
   364                    ///  run() method
   367                    ///  before initializing this iterator
   365                    ///  before initializing this iterator.
   368                    const Node& s, ///< Base node
   366                    const Node& s, ///< The base node.
   369                    const Node& t,
   367                    const Node& t,
   370                    ///< The node you want to separate from Node s.
   368                    ///< The node you want to separate from node \c s.
   371                    bool side=true
   369                    bool side=true
   372                    ///< If it is \c true (default) then the iterator lists
   370                    ///< If it is \c true (default) then the iterator lists
   373                    ///  the nodes of the component containing \c s,
   371                    ///  the nodes of the component containing \c s,
   374                    ///  otherwise it lists the other component.
   372                    ///  otherwise it lists the other component.
   375                    /// \note As the minimum cut is not always unique,
   373                    /// \note As the minimum cut is not always unique,
   396         gomory.minCutMap(s,t,_cut);
   394         gomory.minCutMap(s,t,_cut);
   397         for(_node_it=typename Graph::NodeIt(gomory._graph);
   395         for(_node_it=typename Graph::NodeIt(gomory._graph);
   398             _node_it!=INVALID && _cut[_node_it]!=_side;
   396             _node_it!=INVALID && _cut[_node_it]!=_side;
   399             ++_node_it) {}
   397             ++_node_it) {}
   400       }
   398       }
   401       /// Conversion to Node
   399       /// Conversion to \c Node
   402 
   400 
   403       /// Conversion to Node
   401       /// Conversion to \c Node.
   404       ///
   402       ///
   405       operator typename Graph::Node() const
   403       operator typename Graph::Node() const
   406       {
   404       {
   407         return _node_it;
   405         return _node_it;
   408       }
   406       }
   409       bool operator==(Invalid) { return _node_it==INVALID; }
   407       bool operator==(Invalid) { return _node_it==INVALID; }
   410       bool operator!=(Invalid) { return _node_it!=INVALID; }
   408       bool operator!=(Invalid) { return _node_it!=INVALID; }
   411       /// Next node
   409       /// Next node
   412 
   410 
   413       /// Next node
   411       /// Next node.
   414       ///
   412       ///
   415       MinCutNodeIt &operator++()
   413       MinCutNodeIt &operator++()
   416       {
   414       {
   417         for(++_node_it;_node_it!=INVALID&&_cut[_node_it]!=_side;++_node_it) {}
   415         for(++_node_it;_node_it!=INVALID&&_cut[_node_it]!=_side;++_node_it) {}
   418         return *this;
   416         return *this;
   419       }
   417       }
   420       /// Postfix incrementation
   418       /// Postfix incrementation
   421 
   419 
   422       /// Postfix incrementation
   420       /// Postfix incrementation.
   423       ///
   421       ///
   424       /// \warning This incrementation
   422       /// \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
   426       /// expect.
   424       /// expect.
   427       typename Graph::Node operator++(int)
   425       typename Graph::Node operator++(int)
   428       {
   426       {
   429         typename Graph::Node n=*this;
   427         typename Graph::Node n=*this;
   430         ++(*this);
   428         ++(*this);
   444     /// \c t.
   442     /// \c t.
   445     /// \code
   443     /// \code
   446     /// GomoruHu<Graph> gom(g, capacities);
   444     /// GomoruHu<Graph> gom(g, capacities);
   447     /// gom.run();
   445     /// gom.run();
   448     /// int value=0;
   446     /// 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)
   450     ///   value+=capacities[e];
   448     ///   value+=capacities[e];
   451     /// \endcode
   449     /// \endcode
   452     /// the result will be the same as it is returned by
   450     /// 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)"
   454     class MinCutEdgeIt
   452     class MinCutEdgeIt
   455     {
   453     {
   456       bool _side;
   454       bool _side;
   457       const Graph &_graph;
   455       const Graph &_graph;
   458       typename Graph::NodeIt _node_it;
   456       typename Graph::NodeIt _node_it;
   471       
   469       
   472     public:
   470     public:
   473       MinCutEdgeIt(GomoryHu const &gomory,
   471       MinCutEdgeIt(GomoryHu const &gomory,
   474                    ///< The GomoryHu class. You must call its
   472                    ///< The GomoryHu class. You must call its
   475                    ///  run() method
   473                    ///  run() method
   476                    ///  before initializing this iterator
   474                    ///  before initializing this iterator.
   477                    const Node& s,  ///< Base node
   475                    const Node& s,  ///< The base node.
   478                    const Node& t,
   476                    const Node& t,
   479                    ///< The node you want to separate from Node s.
   477                    ///< The node you want to separate from node \c s.
   480                    bool side=true
   478                    bool side=true
   481                    ///< If it is \c true (default) then the listed arcs
   479                    ///< If it is \c true (default) then the listed arcs
   482                    ///  will be oriented from the
   480                    ///  will be oriented from the
   483                    ///  the nodes of the component containing \c s,
   481                    ///  the nodes of the component containing \c s,
   484                    ///  otherwise they will be oriented in the opposite
   482                    ///  otherwise they will be oriented in the opposite
   502             if(_node_it!=INVALID)
   500             if(_node_it!=INVALID)
   503               _arc_it= typename Graph::OutArcIt(_graph,_node_it);
   501               _arc_it= typename Graph::OutArcIt(_graph,_node_it);
   504           }
   502           }
   505         while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step();
   503         while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step();
   506       }
   504       }
   507       /// Conversion to Arc
   505       /// Conversion to \c Arc
   508 
   506 
   509       /// Conversion to Arc
   507       /// Conversion to \c Arc.
   510       ///
   508       ///
   511       operator typename Graph::Arc() const
   509       operator typename Graph::Arc() const
   512       {
   510       {
   513         return _arc_it;
   511         return _arc_it;
   514       }
   512       }
   515       /// Conversion to Edge
   513       /// Conversion to \c Edge
   516 
   514 
   517       /// Conversion to Edge
   515       /// Conversion to \c Edge.
   518       ///
   516       ///
   519       operator typename Graph::Edge() const
   517       operator typename Graph::Edge() const
   520       {
   518       {
   521         return _arc_it;
   519         return _arc_it;
   522       }
   520       }
   523       bool operator==(Invalid) { return _node_it==INVALID; }
   521       bool operator==(Invalid) { return _node_it==INVALID; }
   524       bool operator!=(Invalid) { return _node_it!=INVALID; }
   522       bool operator!=(Invalid) { return _node_it!=INVALID; }
   525       /// Next edge
   523       /// Next edge
   526 
   524 
   527       /// Next edge
   525       /// Next edge.
   528       ///
   526       ///
   529       MinCutEdgeIt &operator++()
   527       MinCutEdgeIt &operator++()
   530       {
   528       {
   531         step();
   529         step();
   532         while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step();
   530         while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step();
   533         return *this;
   531         return *this;
   534       }
   532       }
   535       /// Postfix incrementation
   533       /// Postfix incrementation
   536       
   534       
   537       /// Postfix incrementation
   535       /// Postfix incrementation.
   538       ///
   536       ///
   539       /// \warning This incrementation
   537       /// \warning This incrementation
   540       /// returns a \c Arc, not a \ref MinCutEdgeIt, as one may
   538       /// returns an \c Arc, not a \c MinCutEdgeIt, as one may expect.
   541       /// expect.
       
   542       typename Graph::Arc operator++(int)
   539       typename Graph::Arc operator++(int)
   543       {
   540       {
   544         typename Graph::Arc e=*this;
   541         typename Graph::Arc e=*this;
   545         ++(*this);
   542         ++(*this);
   546         return e;
   543         return e;