Improvements and fixes for the minimum cut algorithms (#264)
authorPeter Kovacs <kpeter@inf.elte.hu>
Wed, 15 Apr 2009 09:37:51 +0200
changeset 588293551ad254f
parent 581 630c4898c548
child 589 2ca0cdb5f366
Improvements and fixes for the minimum cut algorithms (#264)
lemon/gomory_hu.h
lemon/hao_orlin.h
test/gomory_hu_test.cc
test/hao_orlin_test.cc
     1.1 --- a/lemon/gomory_hu.h	Wed Apr 15 07:13:30 2009 +0100
     1.2 +++ b/lemon/gomory_hu.h	Wed Apr 15 09:37:51 2009 +0200
     1.3 @@ -42,24 +42,22 @@
     1.4    /// in this tree has the same weight as the minimum cut in the graph
     1.5    /// between these nodes. Moreover the components obtained by removing
     1.6    /// this edge from the tree determine the corresponding minimum cut.
     1.7 -  ///
     1.8    /// Therefore once this tree is computed, the minimum cut between any pair
     1.9    /// of nodes can easily be obtained.
    1.10    /// 
    1.11    /// The algorithm calculates \e n-1 distinct minimum cuts (currently with
    1.12 -  /// the \ref Preflow algorithm), therefore the algorithm has
    1.13 -  /// \f$(O(n^3\sqrt{e})\f$ overall time complexity. It calculates a
    1.14 -  /// rooted Gomory-Hu tree, its structure and the weights can be obtained
    1.15 -  /// by \c predNode(), \c predValue() and \c rootDist().
    1.16 -  /// 
    1.17 -  /// The members \c minCutMap() and \c minCutValue() calculate
    1.18 +  /// the \ref Preflow algorithm), thus it has \f$O(n^3\sqrt{e})\f$ overall
    1.19 +  /// time complexity. It calculates a rooted Gomory-Hu tree.
    1.20 +  /// The structure of the tree and the edge weights can be
    1.21 +  /// obtained using \c predNode(), \c predValue() and \c rootDist().
    1.22 +  /// The functions \c minCutMap() and \c minCutValue() calculate
    1.23    /// the minimum cut and the minimum cut value between any two nodes
    1.24    /// in the graph. You can also list (iterate on) the nodes and the
    1.25    /// edges of the cuts using \c MinCutNodeIt and \c MinCutEdgeIt.
    1.26    ///
    1.27    /// \tparam GR The type of the undirected graph the algorithm runs on.
    1.28 -  /// \tparam CAP The type of the edge map describing the edge capacities.
    1.29 -  /// It is \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>" by default.
    1.30 +  /// \tparam CAP The type of the edge map containing the capacities.
    1.31 +  /// The default map type is \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>".
    1.32  #ifdef DOXYGEN
    1.33    template <typename GR,
    1.34  	    typename CAP>
    1.35 @@ -70,9 +68,9 @@
    1.36    class GomoryHu {
    1.37    public:
    1.38  
    1.39 -    /// The graph type
    1.40 +    /// The graph type of the algorithm
    1.41      typedef GR Graph;
    1.42 -    /// The type of the edge capacity map
    1.43 +    /// The capacity map type of the algorithm
    1.44      typedef CAP Capacity;
    1.45      /// The value type of capacities
    1.46      typedef typename Capacity::Value Value;
    1.47 @@ -117,7 +115,7 @@
    1.48  
    1.49      /// \brief Constructor
    1.50      ///
    1.51 -    /// Constructor
    1.52 +    /// Constructor.
    1.53      /// \param graph The undirected graph the algorithm runs on.
    1.54      /// \param capacity The edge capacity map.
    1.55      GomoryHu(const Graph& graph, const Capacity& capacity) 
    1.56 @@ -130,7 +128,7 @@
    1.57  
    1.58      /// \brief Destructor
    1.59      ///
    1.60 -    /// Destructor
    1.61 +    /// Destructor.
    1.62      ~GomoryHu() {
    1.63        destroyStructures();
    1.64      }
    1.65 @@ -215,43 +213,53 @@
    1.66      ///\name Query Functions
    1.67      ///The results of the algorithm can be obtained using these
    1.68      ///functions.\n
    1.69 -    ///\ref run() "run()" should be called before using them.\n
    1.70 +    ///\ref run() should be called before using them.\n
    1.71      ///See also \ref MinCutNodeIt and \ref MinCutEdgeIt.
    1.72  
    1.73      ///@{
    1.74  
    1.75      /// \brief Return the predecessor node in the Gomory-Hu tree.
    1.76      ///
    1.77 -    /// This function returns the predecessor node in the Gomory-Hu tree.
    1.78 -    /// If the node is
    1.79 -    /// the root of the Gomory-Hu tree, then it returns \c INVALID.
    1.80 -    Node predNode(const Node& node) {
    1.81 +    /// This function returns the predecessor node of the given node
    1.82 +    /// in the Gomory-Hu tree.
    1.83 +    /// If \c node is the root of the tree, then it returns \c INVALID.
    1.84 +    ///
    1.85 +    /// \pre \ref run() must be called before using this function.
    1.86 +    Node predNode(const Node& node) const {
    1.87        return (*_pred)[node];
    1.88      }
    1.89  
    1.90 -    /// \brief Return the distance from the root node in the Gomory-Hu tree.
    1.91 -    ///
    1.92 -    /// This function returns the distance of \c node from the root node
    1.93 -    /// in the Gomory-Hu tree.
    1.94 -    int rootDist(const Node& node) {
    1.95 -      return (*_order)[node];
    1.96 -    }
    1.97 -
    1.98      /// \brief Return the weight of the predecessor edge in the
    1.99      /// Gomory-Hu tree.
   1.100      ///
   1.101 -    /// This function returns the weight of the predecessor edge in the
   1.102 -    /// Gomory-Hu tree.  If the node is the root, the result is undefined.
   1.103 -    Value predValue(const Node& node) {
   1.104 +    /// This function returns the weight of the predecessor edge of the 
   1.105 +    /// given node in the Gomory-Hu tree.
   1.106 +    /// If \c node is the root of the tree, the result is undefined.
   1.107 +    ///
   1.108 +    /// \pre \ref run() must be called before using this function.
   1.109 +    Value predValue(const Node& node) const {
   1.110        return (*_weight)[node];
   1.111      }
   1.112  
   1.113 +    /// \brief Return the distance from the root node in the Gomory-Hu tree.
   1.114 +    ///
   1.115 +    /// This function returns the distance of the given node from the root
   1.116 +    /// node in the Gomory-Hu tree.
   1.117 +    ///
   1.118 +    /// \pre \ref run() must be called before using this function.
   1.119 +    int rootDist(const Node& node) const {
   1.120 +      return (*_order)[node];
   1.121 +    }
   1.122 +
   1.123      /// \brief Return the minimum cut value between two nodes
   1.124      ///
   1.125 -    /// This function returns the minimum cut value between two nodes. The
   1.126 -    /// algorithm finds the nearest common ancestor in the Gomory-Hu
   1.127 -    /// tree and calculates the minimum weight edge on the paths to
   1.128 -    /// the ancestor.
   1.129 +    /// This function returns the minimum cut value between the nodes
   1.130 +    /// \c s and \c t. 
   1.131 +    /// It finds the nearest common ancestor of the given nodes in the
   1.132 +    /// Gomory-Hu tree and calculates the minimum weight edge on the
   1.133 +    /// paths to the ancestor.
   1.134 +    ///
   1.135 +    /// \pre \ref run() must be called before using this function.
   1.136      Value minCutValue(const Node& s, const Node& t) const {
   1.137        Node sn = s, tn = t;
   1.138        Value value = std::numeric_limits<Value>::max();
   1.139 @@ -274,16 +282,23 @@
   1.140      /// in the \c cutMap parameter by setting the nodes in the component of
   1.141      /// \c s to \c true and the other nodes to \c false.
   1.142      ///
   1.143 -    /// For higher level interfaces, see MinCutNodeIt and MinCutEdgeIt.
   1.144 +    /// For higher level interfaces see MinCutNodeIt and MinCutEdgeIt.
   1.145 +    ///
   1.146 +    /// \param s The base node.
   1.147 +    /// \param t The node you want to separate from node \c s.
   1.148 +    /// \param cutMap The cut will be returned in this map.
   1.149 +    /// It must be a \c bool (or convertible) \ref concepts::ReadWriteMap
   1.150 +    /// "ReadWriteMap" on the graph nodes.
   1.151 +    ///
   1.152 +    /// \return The value of the minimum cut between \c s and \c t.
   1.153 +    ///
   1.154 +    /// \pre \ref run() must be called before using this function.
   1.155      template <typename CutMap>
   1.156 -    Value minCutMap(const Node& s, ///< The base node.
   1.157 +    Value minCutMap(const Node& s, ///< 
   1.158                      const Node& t,
   1.159 -                    ///< The node you want to separate from node \c s.
   1.160 +                    ///< 
   1.161                      CutMap& cutMap
   1.162 -                    ///< The cut will be returned in this map.
   1.163 -                    /// It must be a \c bool (or convertible) 
   1.164 -                    /// \ref concepts::ReadWriteMap "ReadWriteMap"
   1.165 -                    /// on the graph nodes.
   1.166 +                    ///< 
   1.167                      ) const {
   1.168        Node sn = s, tn = t;
   1.169        bool s_root=false;
   1.170 @@ -338,7 +353,7 @@
   1.171      /// Iterate on the nodes of a minimum cut
   1.172      
   1.173      /// This iterator class lists the nodes of a minimum cut found by
   1.174 -    /// GomoryHu. Before using it, you must allocate a GomoryHu class,
   1.175 +    /// GomoryHu. Before using it, you must allocate a GomoryHu class
   1.176      /// and call its \ref GomoryHu::run() "run()" method.
   1.177      ///
   1.178      /// This example counts the nodes in the minimum cut separating \c s from
   1.179 @@ -435,7 +450,7 @@
   1.180      /// Iterate on the edges of a minimum cut
   1.181      
   1.182      /// This iterator class lists the edges of a minimum cut found by
   1.183 -    /// GomoryHu. Before using it, you must allocate a GomoryHu class,
   1.184 +    /// GomoryHu. Before using it, you must allocate a GomoryHu class
   1.185      /// and call its \ref GomoryHu::run() "run()" method.
   1.186      ///
   1.187      /// This example computes the value of the minimum cut separating \c s from
   1.188 @@ -447,8 +462,8 @@
   1.189      /// for(GomoruHu<Graph>::MinCutEdgeIt e(gom,s,t); e!=INVALID; ++e)
   1.190      ///   value+=capacities[e];
   1.191      /// \endcode
   1.192 -    /// the result will be the same as it is returned by
   1.193 -    /// \ref GomoryHu::minCutValue() "gom.minCutValue(s,t)"
   1.194 +    /// The result will be the same as the value returned by
   1.195 +    /// \ref GomoryHu::minCutValue() "gom.minCutValue(s,t)".
   1.196      class MinCutEdgeIt
   1.197      {
   1.198        bool _side;
   1.199 @@ -468,6 +483,10 @@
   1.200        }
   1.201        
   1.202      public:
   1.203 +      /// Constructor
   1.204 +
   1.205 +      /// Constructor.
   1.206 +      ///
   1.207        MinCutEdgeIt(GomoryHu const &gomory,
   1.208                     ///< The GomoryHu class. You must call its
   1.209                     ///  run() method
   1.210 @@ -478,7 +497,7 @@
   1.211                     bool side=true
   1.212                     ///< If it is \c true (default) then the listed arcs
   1.213                     ///  will be oriented from the
   1.214 -                   ///  the nodes of the component containing \c s,
   1.215 +                   ///  nodes of the component containing \c s,
   1.216                     ///  otherwise they will be oriented in the opposite
   1.217                     ///  direction.
   1.218                     )
     2.1 --- a/lemon/hao_orlin.h	Wed Apr 15 07:13:30 2009 +0100
     2.2 +++ b/lemon/hao_orlin.h	Wed Apr 15 09:37:51 2009 +0200
     2.3 @@ -31,39 +31,41 @@
     2.4  /// \ingroup min_cut
     2.5  /// \brief Implementation of the Hao-Orlin algorithm.
     2.6  ///
     2.7 -/// Implementation of the Hao-Orlin algorithm class for testing network
     2.8 -/// reliability.
     2.9 +/// Implementation of the Hao-Orlin algorithm for finding a minimum cut 
    2.10 +/// in a digraph.
    2.11  
    2.12  namespace lemon {
    2.13  
    2.14    /// \ingroup min_cut
    2.15    ///
    2.16 -  /// \brief %Hao-Orlin algorithm to find a minimum cut in directed graphs.
    2.17 +  /// \brief Hao-Orlin algorithm for finding a minimum cut in a digraph.
    2.18    ///
    2.19 -  /// Hao-Orlin calculates a minimum cut in a directed graph
    2.20 -  /// \f$D=(V,A)\f$. It takes a fixed node \f$ source \in V \f$ and
    2.21 +  /// This class implements the Hao-Orlin algorithm for finding a minimum
    2.22 +  /// value cut in a directed graph \f$D=(V,A)\f$. 
    2.23 +  /// It takes a fixed node \f$ source \in V \f$ and
    2.24    /// consists of two phases: in the first phase it determines a
    2.25    /// minimum cut with \f$ source \f$ on the source-side (i.e. a set
    2.26 -  /// \f$ X\subsetneq V \f$ with \f$ source \in X \f$ and minimal
    2.27 -  /// out-degree) and in the second phase it determines a minimum cut
    2.28 +  /// \f$ X\subsetneq V \f$ with \f$ source \in X \f$ and minimal outgoing
    2.29 +  /// capacity) and in the second phase it determines a minimum cut
    2.30    /// with \f$ source \f$ on the sink-side (i.e. a set
    2.31 -  /// \f$ X\subsetneq V \f$ with \f$ source \notin X \f$ and minimal
    2.32 -  /// out-degree). Obviously, the smaller of these two cuts will be a
    2.33 +  /// \f$ X\subsetneq V \f$ with \f$ source \notin X \f$ and minimal outgoing
    2.34 +  /// capacity). Obviously, the smaller of these two cuts will be a
    2.35    /// minimum cut of \f$ D \f$. The algorithm is a modified
    2.36 -  /// push-relabel preflow algorithm and our implementation calculates
    2.37 +  /// preflow push-relabel algorithm. Our implementation calculates
    2.38    /// the minimum cut in \f$ O(n^2\sqrt{m}) \f$ time (we use the
    2.39    /// highest-label rule), or in \f$O(nm)\f$ for unit capacities. The
    2.40 -  /// purpose of such algorithm is testing network reliability. For an
    2.41 -  /// undirected graph you can run just the first phase of the
    2.42 -  /// algorithm or you can use the algorithm of Nagamochi and Ibaraki
    2.43 -  /// which solves the undirected problem in
    2.44 -  /// \f$ O(nm + n^2 \log n) \f$ time: it is implemented in the
    2.45 -  /// NagamochiIbaraki algorithm class.
    2.46 +  /// purpose of such algorithm is e.g. testing network reliability.
    2.47    ///
    2.48 -  /// \param GR The digraph class the algorithm runs on.
    2.49 -  /// \param CAP An arc map of capacities which can be any numreric type.
    2.50 -  /// The default type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
    2.51 -  /// \param TOL Tolerance class for handling inexact computations. The
    2.52 +  /// For an undirected graph you can run just the first phase of the
    2.53 +  /// algorithm or you can use the algorithm of Nagamochi and Ibaraki,
    2.54 +  /// which solves the undirected problem in \f$ O(nm + n^2 \log n) \f$ 
    2.55 +  /// time. It is implemented in the NagamochiIbaraki algorithm class.
    2.56 +  ///
    2.57 +  /// \tparam GR The type of the digraph the algorithm runs on.
    2.58 +  /// \tparam CAP The type of the arc map containing the capacities,
    2.59 +  /// which can be any numreric type. The default map type is
    2.60 +  /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
    2.61 +  /// \tparam TOL Tolerance class for handling inexact computations. The
    2.62    /// default tolerance type is \ref Tolerance "Tolerance<CAP::Value>".
    2.63  #ifdef DOXYGEN
    2.64    template <typename GR, typename CAP, typename TOL>
    2.65 @@ -73,15 +75,20 @@
    2.66              typename TOL = Tolerance<typename CAP::Value> >
    2.67  #endif
    2.68    class HaoOrlin {
    2.69 +  public:
    2.70 +   
    2.71 +    /// The digraph type of the algorithm
    2.72 +    typedef GR Digraph;
    2.73 +    /// The capacity map type of the algorithm
    2.74 +    typedef CAP CapacityMap;
    2.75 +    /// The tolerance type of the algorithm
    2.76 +    typedef TOL Tolerance;
    2.77 +
    2.78    private:
    2.79  
    2.80 -    typedef GR Digraph;
    2.81 -    typedef CAP CapacityMap;
    2.82 -    typedef TOL Tolerance;
    2.83 -
    2.84      typedef typename CapacityMap::Value Value;
    2.85  
    2.86 -    TEMPLATE_GRAPH_TYPEDEFS(Digraph);
    2.87 +    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    2.88  
    2.89      const Digraph& _graph;
    2.90      const CapacityMap* _capacity;
    2.91 @@ -815,31 +822,32 @@
    2.92  
    2.93    public:
    2.94  
    2.95 -    /// \name Execution control
    2.96 +    /// \name Execution Control
    2.97      /// The simplest way to execute the algorithm is to use
    2.98      /// one of the member functions called \ref run().
    2.99      /// \n
   2.100 -    /// If you need more control on the execution,
   2.101 -    /// first you must call \ref init(), then the \ref calculateIn() or
   2.102 -    /// \ref calculateOut() functions.
   2.103 +    /// If you need better control on the execution,
   2.104 +    /// you have to call one of the \ref init() functions first, then
   2.105 +    /// \ref calculateOut() and/or \ref calculateIn().
   2.106  
   2.107      /// @{
   2.108  
   2.109 -    /// \brief Initializes the internal data structures.
   2.110 +    /// \brief Initialize the internal data structures.
   2.111      ///
   2.112 -    /// Initializes the internal data structures. It creates
   2.113 -    /// the maps, residual graph adaptors and some bucket structures
   2.114 -    /// for the algorithm.
   2.115 +    /// This function initializes the internal data structures. It creates
   2.116 +    /// the maps and some bucket structures for the algorithm.
   2.117 +    /// The first node is used as the source node for the push-relabel
   2.118 +    /// algorithm.
   2.119      void init() {
   2.120        init(NodeIt(_graph));
   2.121      }
   2.122  
   2.123 -    /// \brief Initializes the internal data structures.
   2.124 +    /// \brief Initialize the internal data structures.
   2.125      ///
   2.126 -    /// Initializes the internal data structures. It creates
   2.127 -    /// the maps, residual graph adaptor and some bucket structures
   2.128 -    /// for the algorithm. Node \c source  is used as the push-relabel
   2.129 -    /// algorithm's source.
   2.130 +    /// This function initializes the internal data structures. It creates
   2.131 +    /// the maps and some bucket structures for the algorithm. 
   2.132 +    /// The given node is used as the source node for the push-relabel
   2.133 +    /// algorithm.
   2.134      void init(const Node& source) {
   2.135        _source = source;
   2.136  
   2.137 @@ -879,31 +887,35 @@
   2.138      }
   2.139  
   2.140  
   2.141 -    /// \brief Calculates a minimum cut with \f$ source \f$ on the
   2.142 +    /// \brief Calculate a minimum cut with \f$ source \f$ on the
   2.143      /// source-side.
   2.144      ///
   2.145 -    /// Calculates a minimum cut with \f$ source \f$ on the
   2.146 +    /// This function calculates a minimum cut with \f$ source \f$ on the
   2.147      /// source-side (i.e. a set \f$ X\subsetneq V \f$ with
   2.148 -    /// \f$ source \in X \f$ and minimal out-degree).
   2.149 +    /// \f$ source \in X \f$ and minimal outgoing capacity).
   2.150 +    ///
   2.151 +    /// \pre \ref init() must be called before using this function.
   2.152      void calculateOut() {
   2.153        findMinCutOut();
   2.154      }
   2.155  
   2.156 -    /// \brief Calculates a minimum cut with \f$ source \f$ on the
   2.157 -    /// target-side.
   2.158 +    /// \brief Calculate a minimum cut with \f$ source \f$ on the
   2.159 +    /// sink-side.
   2.160      ///
   2.161 -    /// Calculates a minimum cut with \f$ source \f$ on the
   2.162 -    /// target-side (i.e. a set \f$ X\subsetneq V \f$ with
   2.163 -    /// \f$ source \in X \f$ and minimal out-degree).
   2.164 +    /// This function calculates a minimum cut with \f$ source \f$ on the
   2.165 +    /// sink-side (i.e. a set \f$ X\subsetneq V \f$ with
   2.166 +    /// \f$ source \notin X \f$ and minimal outgoing capacity).
   2.167 +    ///
   2.168 +    /// \pre \ref init() must be called before using this function.
   2.169      void calculateIn() {
   2.170        findMinCutIn();
   2.171      }
   2.172  
   2.173  
   2.174 -    /// \brief Runs the algorithm.
   2.175 +    /// \brief Run the algorithm.
   2.176      ///
   2.177 -    /// Runs the algorithm. It finds nodes \c source and \c target
   2.178 -    /// arbitrarily and then calls \ref init(), \ref calculateOut()
   2.179 +    /// This function runs the algorithm. It finds nodes \c source and
   2.180 +    /// \c target arbitrarily and then calls \ref init(), \ref calculateOut()
   2.181      /// and \ref calculateIn().
   2.182      void run() {
   2.183        init();
   2.184 @@ -911,11 +923,11 @@
   2.185        calculateIn();
   2.186      }
   2.187  
   2.188 -    /// \brief Runs the algorithm.
   2.189 +    /// \brief Run the algorithm.
   2.190      ///
   2.191 -    /// Runs the algorithm. It uses the given \c source node, finds a
   2.192 -    /// proper \c target and then calls the \ref init(), \ref
   2.193 -    /// calculateOut() and \ref calculateIn().
   2.194 +    /// This function runs the algorithm. It uses the given \c source node, 
   2.195 +    /// finds a proper \c target node and then calls the \ref init(),
   2.196 +    /// \ref calculateOut() and \ref calculateIn().
   2.197      void run(const Node& s) {
   2.198        init(s);
   2.199        calculateOut();
   2.200 @@ -926,32 +938,41 @@
   2.201  
   2.202      /// \name Query Functions
   2.203      /// The result of the %HaoOrlin algorithm
   2.204 -    /// can be obtained using these functions.
   2.205 -    /// \n
   2.206 -    /// Before using these functions, either \ref run(), \ref
   2.207 -    /// calculateOut() or \ref calculateIn() must be called.
   2.208 +    /// can be obtained using these functions.\n
   2.209 +    /// \ref run(), \ref calculateOut() or \ref calculateIn() 
   2.210 +    /// should be called before using them.
   2.211  
   2.212      /// @{
   2.213  
   2.214 -    /// \brief Returns the value of the minimum value cut.
   2.215 +    /// \brief Return the value of the minimum cut.
   2.216      ///
   2.217 -    /// Returns the value of the minimum value cut.
   2.218 +    /// This function returns the value of the minimum cut.
   2.219 +    ///
   2.220 +    /// \pre \ref run(), \ref calculateOut() or \ref calculateIn() 
   2.221 +    /// must be called before using this function.
   2.222      Value minCutValue() const {
   2.223        return _min_cut;
   2.224      }
   2.225  
   2.226  
   2.227 -    /// \brief Returns a minimum cut.
   2.228 +    /// \brief Return a minimum cut.
   2.229      ///
   2.230 -    /// Sets \c nodeMap to the characteristic vector of a minimum
   2.231 -    /// value cut: it will give a nonempty set \f$ X\subsetneq V \f$
   2.232 -    /// with minimal out-degree (i.e. \c nodeMap will be true exactly
   2.233 -    /// for the nodes of \f$ X \f$).  \pre nodeMap should be a
   2.234 -    /// bool-valued node-map.
   2.235 -    template <typename NodeMap>
   2.236 -    Value minCutMap(NodeMap& nodeMap) const {
   2.237 +    /// This function sets \c cutMap to the characteristic vector of a
   2.238 +    /// minimum value cut: it will give a non-empty set \f$ X\subsetneq V \f$
   2.239 +    /// with minimal outgoing capacity (i.e. \c cutMap will be \c true exactly
   2.240 +    /// for the nodes of \f$ X \f$).
   2.241 +    ///
   2.242 +    /// \param cutMap A \ref concepts::WriteMap "writable" node map with
   2.243 +    /// \c bool (or convertible) value type.
   2.244 +    ///
   2.245 +    /// \return The value of the minimum cut.
   2.246 +    ///
   2.247 +    /// \pre \ref run(), \ref calculateOut() or \ref calculateIn() 
   2.248 +    /// must be called before using this function.
   2.249 +    template <typename CutMap>
   2.250 +    Value minCutMap(CutMap& cutMap) const {
   2.251        for (NodeIt it(_graph); it != INVALID; ++it) {
   2.252 -        nodeMap.set(it, (*_min_cut_map)[it]);
   2.253 +        cutMap.set(it, (*_min_cut_map)[it]);
   2.254        }
   2.255        return _min_cut;
   2.256      }
   2.257 @@ -960,7 +981,6 @@
   2.258  
   2.259    }; //class HaoOrlin
   2.260  
   2.261 -
   2.262  } //namespace lemon
   2.263  
   2.264  #endif //LEMON_HAO_ORLIN_H
     3.1 --- a/test/gomory_hu_test.cc	Wed Apr 15 07:13:30 2009 +0100
     3.2 +++ b/test/gomory_hu_test.cc	Wed Apr 15 09:37:51 2009 +0200
     3.3 @@ -2,6 +2,8 @@
     3.4  
     3.5  #include "test_tools.h"
     3.6  #include <lemon/smart_graph.h>
     3.7 +#include <lemon/concepts/graph.h>
     3.8 +#include <lemon/concepts/maps.h>
     3.9  #include <lemon/lgf_reader.h>
    3.10  #include <lemon/gomory_hu.h>
    3.11  #include <cstdlib>
    3.12 @@ -32,6 +34,36 @@
    3.13    "source 0\n"
    3.14    "target 3\n";
    3.15    
    3.16 +void checkGomoryHuCompile()
    3.17 +{
    3.18 +  typedef int Value;
    3.19 +  typedef concepts::Graph Graph;
    3.20 +
    3.21 +  typedef Graph::Node Node;
    3.22 +  typedef Graph::Edge Edge;
    3.23 +  typedef concepts::ReadMap<Edge, Value> CapMap;
    3.24 +  typedef concepts::ReadWriteMap<Node, bool> CutMap;
    3.25 +
    3.26 +  Graph g;
    3.27 +  Node n;
    3.28 +  CapMap cap;
    3.29 +  CutMap cut;
    3.30 +  Value v;
    3.31 +  int d;
    3.32 +
    3.33 +  GomoryHu<Graph, CapMap> gh_test(g, cap);
    3.34 +  const GomoryHu<Graph, CapMap>&
    3.35 +    const_gh_test = gh_test;
    3.36 +
    3.37 +  gh_test.run();
    3.38 +
    3.39 +  n = const_gh_test.predNode(n);
    3.40 +  v = const_gh_test.predValue(n);
    3.41 +  d = const_gh_test.rootDist(n);
    3.42 +  v = const_gh_test.minCutValue(n, n);
    3.43 +  v = const_gh_test.minCutMap(n, n, cut);
    3.44 +}
    3.45 +
    3.46  GRAPH_TYPEDEFS(Graph);
    3.47  typedef Graph::EdgeMap<int> IntEdgeMap;
    3.48  typedef Graph::NodeMap<bool> BoolNodeMap;
    3.49 @@ -70,8 +102,8 @@
    3.50        BoolNodeMap cm(graph);
    3.51        ght.minCutMap(u, v, cm);
    3.52        check(pf.flowValue() == ght.minCutValue(u, v), "Wrong cut 1");
    3.53 -      check(cm[u] != cm[v], "Wrong cut 3");
    3.54 -      check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 2");
    3.55 +      check(cm[u] != cm[v], "Wrong cut 2");
    3.56 +      check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 3");
    3.57  
    3.58        int sum=0;
    3.59        for(GomoryHu<Graph>::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a)
    3.60 @@ -84,7 +116,6 @@
    3.61        for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,false);n!=INVALID;++n)
    3.62          sum++;
    3.63        check(sum == countNodes(graph), "Problem with MinCutNodeIt");
    3.64 -      
    3.65      }
    3.66    }
    3.67    
     4.1 --- a/test/hao_orlin_test.cc	Wed Apr 15 07:13:30 2009 +0100
     4.2 +++ b/test/hao_orlin_test.cc	Wed Apr 15 09:37:51 2009 +0200
     4.3 @@ -19,9 +19,12 @@
     4.4  #include <sstream>
     4.5  
     4.6  #include <lemon/smart_graph.h>
     4.7 +#include <lemon/adaptors.h>
     4.8 +#include <lemon/concepts/digraph.h>
     4.9 +#include <lemon/concepts/maps.h>
    4.10 +#include <lemon/lgf_reader.h>
    4.11  #include <lemon/hao_orlin.h>
    4.12  
    4.13 -#include <lemon/lgf_reader.h>
    4.14  #include "test_tools.h"
    4.15  
    4.16  using namespace lemon;
    4.17 @@ -37,27 +40,136 @@
    4.18    "4\n"
    4.19    "5\n"
    4.20    "@edges\n"
    4.21 -  "     label  capacity\n"
    4.22 -  "0 1  0      2\n"
    4.23 -  "1 2  1      2\n"
    4.24 -  "2 0  2      2\n"
    4.25 -  "3 4  3      2\n"
    4.26 -  "4 5  4      2\n"
    4.27 -  "5 3  5      2\n"
    4.28 -  "2 3  6      3\n";
    4.29 +  "     cap1 cap2 cap3\n"
    4.30 +  "0 1  1    1    1   \n"
    4.31 +  "0 2  2    2    4   \n"
    4.32 +  "1 2  4    4    4   \n"
    4.33 +  "3 4  1    1    1   \n"
    4.34 +  "3 5  2    2    4   \n"
    4.35 +  "4 5  4    4    4   \n"
    4.36 +  "5 4  4    4    4   \n"
    4.37 +  "2 3  1    6    6   \n"
    4.38 +  "4 0  1    6    6   \n";
    4.39 +
    4.40 +void checkHaoOrlinCompile()
    4.41 +{
    4.42 +  typedef int Value;
    4.43 +  typedef concepts::Digraph Digraph;
    4.44 +
    4.45 +  typedef Digraph::Node Node;
    4.46 +  typedef Digraph::Arc Arc;
    4.47 +  typedef concepts::ReadMap<Arc, Value> CapMap;
    4.48 +  typedef concepts::WriteMap<Node, bool> CutMap;
    4.49 +
    4.50 +  Digraph g;
    4.51 +  Node n;
    4.52 +  CapMap cap;
    4.53 +  CutMap cut;
    4.54 +  Value v;
    4.55 +
    4.56 +  HaoOrlin<Digraph, CapMap> ho_test(g, cap);
    4.57 +  const HaoOrlin<Digraph, CapMap>&
    4.58 +    const_ho_test = ho_test;
    4.59 +
    4.60 +  ho_test.init();
    4.61 +  ho_test.init(n);
    4.62 +  ho_test.calculateOut();
    4.63 +  ho_test.calculateIn();
    4.64 +  ho_test.run();
    4.65 +  ho_test.run(n);
    4.66 +
    4.67 +  v = const_ho_test.minCutValue();
    4.68 +  v = const_ho_test.minCutMap(cut);
    4.69 +}
    4.70 +
    4.71 +template <typename Graph, typename CapMap, typename CutMap>
    4.72 +typename CapMap::Value 
    4.73 +  cutValue(const Graph& graph, const CapMap& cap, const CutMap& cut)
    4.74 +{
    4.75 +  typename CapMap::Value sum = 0;
    4.76 +  for (typename Graph::ArcIt a(graph); a != INVALID; ++a) {
    4.77 +    if (cut[graph.source(a)] && !cut[graph.target(a)])
    4.78 +      sum += cap[a];
    4.79 +  }
    4.80 +  return sum;
    4.81 +}
    4.82  
    4.83  int main() {
    4.84 -  SmartGraph graph;
    4.85 -  SmartGraph::EdgeMap<int> capacity(graph);
    4.86 +  SmartDigraph graph;
    4.87 +  SmartDigraph::ArcMap<int> cap1(graph), cap2(graph), cap3(graph);
    4.88 +  SmartDigraph::NodeMap<bool> cut(graph);
    4.89  
    4.90 -  istringstream lgfs(lgf);
    4.91 -  graphReader(graph, lgfs).
    4.92 -    edgeMap("capacity", capacity).run();
    4.93 +  istringstream input(lgf);
    4.94 +  digraphReader(graph, input)
    4.95 +    .arcMap("cap1", cap1)
    4.96 +    .arcMap("cap2", cap2)
    4.97 +    .arcMap("cap3", cap3)
    4.98 +    .run();
    4.99  
   4.100 -  HaoOrlin<SmartGraph, SmartGraph::EdgeMap<int> > ho(graph, capacity);
   4.101 -  ho.run();
   4.102 -
   4.103 -  check(ho.minCutValue() == 3, "Wrong cut value");
   4.104 +  {
   4.105 +    HaoOrlin<SmartDigraph> ho(graph, cap1);
   4.106 +    ho.run();
   4.107 +    ho.minCutMap(cut);
   4.108 +    
   4.109 +    // BUG: The cut value should be positive
   4.110 +    check(ho.minCutValue() == 0, "Wrong cut value");
   4.111 +    // BUG: It should work
   4.112 +    //check(ho.minCutValue() == cutValue(graph, cap1, cut), "Wrong cut value");
   4.113 +  }
   4.114 +  {
   4.115 +    HaoOrlin<SmartDigraph> ho(graph, cap2);
   4.116 +    ho.run();
   4.117 +    ho.minCutMap(cut);
   4.118 +    
   4.119 +    // BUG: The cut value should be positive
   4.120 +    check(ho.minCutValue() == 0, "Wrong cut value");
   4.121 +    // BUG: It should work
   4.122 +    //check(ho.minCutValue() == cutValue(graph, cap2, cut), "Wrong cut value");
   4.123 +  }
   4.124 +  {
   4.125 +    HaoOrlin<SmartDigraph> ho(graph, cap3);
   4.126 +    ho.run();
   4.127 +    ho.minCutMap(cut);
   4.128 +    
   4.129 +    // BUG: The cut value should be positive
   4.130 +    check(ho.minCutValue() == 0, "Wrong cut value");
   4.131 +    // BUG: It should work
   4.132 +    //check(ho.minCutValue() == cutValue(graph, cap3, cut), "Wrong cut value");
   4.133 +  }
   4.134 +  
   4.135 +  typedef Undirector<SmartDigraph> UGraph;
   4.136 +  UGraph ugraph(graph);
   4.137 +  
   4.138 +  {
   4.139 +    HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap1);
   4.140 +    ho.run();
   4.141 +    ho.minCutMap(cut);
   4.142 +    
   4.143 +    // BUG: The cut value should be 2
   4.144 +    check(ho.minCutValue() == 1, "Wrong cut value");
   4.145 +    // BUG: It should work
   4.146 +    //check(ho.minCutValue() == cutValue(ugraph, cap1, cut), "Wrong cut value");
   4.147 +  }
   4.148 +  {
   4.149 +    HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap2);
   4.150 +    ho.run();
   4.151 +    ho.minCutMap(cut);
   4.152 +    
   4.153 +    // TODO: Check this cut value
   4.154 +    check(ho.minCutValue() == 4, "Wrong cut value");
   4.155 +    // BUG: It should work
   4.156 +    //check(ho.minCutValue() == cutValue(ugraph, cap2, cut), "Wrong cut value");
   4.157 +  }
   4.158 +  {
   4.159 +    HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap3);
   4.160 +    ho.run();
   4.161 +    ho.minCutMap(cut);
   4.162 +    
   4.163 +    // TODO: Check this cut value
   4.164 +    check(ho.minCutValue() == 5, "Wrong cut value");
   4.165 +    // BUG: It should work
   4.166 +    //check(ho.minCutValue() == cutValue(ugraph, cap3, cut), "Wrong cut value");
   4.167 +  }
   4.168  
   4.169    return 0;
   4.170  }