author Peter Kovacs Wed, 15 Apr 2009 09:37:51 +0200 changeset 596 293551ad254f parent 589 630c4898c548 child 597 2ca0cdb5f366
Improvements and fixes for the minimum cut algorithms (#264)
 lemon/gomory_hu.h file | annotate | diff | comparison | revisions lemon/hao_orlin.h file | annotate | diff | comparison | revisions test/gomory_hu_test.cc file | annotate | diff | comparison | revisions test/hao_orlin_test.cc file | annotate | diff | comparison | revisions
     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.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.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.8 +#include <lemon/concepts/digraph.h>
4.9 +#include <lemon/concepts/maps.h>
4.11  #include <lemon/hao_orlin.h>
4.12
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  }