# HG changeset patch
# User Alpar Juttner <alpar@cs.elte.hu>
# Date 1235560252 0
# Node ID ccd2d3a3001ebc80a67dd8d4de56486d82eec773
# Parent 924887566bf2e375c896f7b955bea6b6adb9ac2e
Cut iterators for GomoryHuTree + doc cleanup + bug fixes (#66)
diff -r 924887566bf2 -r ccd2d3a3001e lemon/gomory_hu_tree.h
--- a/lemon/gomory_hu_tree.h Fri Feb 20 17:17:17 2009 +0100
+++ b/lemon/gomory_hu_tree.h Wed Feb 25 11:10:52 2009 +0000
@@ -21,6 +21,7 @@
#include <limits>
+#include <lemon/core.h>
#include <lemon/preflow.h>
#include <lemon/concept_check.h>
#include <lemon/concepts/maps.h>
@@ -35,31 +36,40 @@
///
/// \brief Gomory-Hu cut tree algorithm
///
- /// The Gomory-Hu tree is a tree on the nodeset of the digraph, but it
- /// may contain arcs which are not in the original digraph. It helps
- /// to calculate the minimum cut between all pairs of nodes, because
- /// the minimum capacity arc on the tree path between two nodes has
- /// the same weight as the minimum cut in the digraph between these
- /// nodes. Moreover this arc separates the nodes to two parts which
- /// determine this minimum cut.
+ /// The Gomory-Hu tree is a tree on the node set of the graph, but it
+ /// may contain edges which are not in the original digraph. It has the
+ /// property that the minimum capacity edge of the path between two nodes
+ /// in this tree has the same weight as the minimum cut in the digraph
+ /// between these nodes. Moreover the components obtained by removing
+ /// this edge from the tree determine the corresponding minimum cut.
+ ///
+ /// Therefore once this tree is computed, the minimum cut between any pair
+ /// of nodes can easily be obtained.
///
- /// The algorithm calculates \e n-1 distinict minimum cuts with
- /// preflow algorithm, therefore the algorithm has
+ /// The algorithm calculates \e n-1 distinct minimum cuts (currently with
+ /// the \ref Preflow algorithm), therefore the algorithm has
/// \f$(O(n^3\sqrt{e})\f$ overall time complexity. It calculates a
- /// rooted Gomory-Hu tree, the structure of the tree and the weights
- /// can be obtained with \c predNode() and \c predValue()
- /// functions. The \c minCutValue() and \c minCutMap() calculates
+ /// rooted Gomory-Hu tree, its structure and the weights can be obtained
+ /// by \c predNode(), \c predValue() and \c rootDist().
+ ///
+ /// The members \c minCutMap() and \c minCutValue() calculate
/// the minimum cut and the minimum cut value between any two node
- /// in the digraph.
- template <typename _Graph,
- typename _Capacity = typename _Graph::template EdgeMap<int> >
+ /// in the digraph. You can also list (iterate on) the nodes and the
+ /// edges of the cuts using MinCutNodeIt and MinCutEdgeIt.
+ ///
+ /// \tparam GR The undirected graph data structure the algorithm will run on
+ /// \tparam CAP type of the EdgeMap describing the Edge capacities.
+ /// it is typename GR::template EdgeMap<int> by default.
+ template <typename GR,
+ typename CAP = typename GR::template EdgeMap<int>
+ >
class GomoryHuTree {
public:
/// The graph type
- typedef _Graph Graph;
- /// The capacity on edges
- typedef _Capacity Capacity;
+ typedef GR Graph;
+ /// The type if the edge capacity map
+ typedef CAP Capacity;
/// The value type of capacities
typedef typename Capacity::Value Value;
@@ -104,7 +114,7 @@
/// \brief Constructor
///
/// Constructor
- /// \param graph The graph type.
+ /// \param graph The graph the algorithm will run on.
/// \param capacity The capacity map.
GomoryHuTree(const Graph& graph, const Capacity& capacity)
: _graph(graph), _capacity(capacity),
@@ -121,10 +131,10 @@
destroyStructures();
}
- /// \brief Initializes the internal data structures.
- ///
- /// Initializes the internal data structures.
- ///
+ // \brief Initialize the internal data structures.
+ //
+ // This function initializes the internal data structures.
+ //
void init() {
createStructures();
@@ -138,9 +148,12 @@
}
- /// \brief Starts the algorithm
- ///
- /// Starts the algorithm.
+ // \brief Start the algorithm
+ //
+ // This function starts the algorithm.
+ //
+ // \pre \ref init() must be called before using this function.
+ //
void start() {
Preflow<Graph, Capacity> fa(_graph, _capacity, _root, INVALID);
@@ -185,40 +198,57 @@
}
}
- /// \brief Runs the Gomory-Hu algorithm.
+ ///\name Execution Control
+
+ ///@{
+
+ /// \brief Run the Gomory-Hu algorithm.
///
- /// Runs the Gomory-Hu algorithm.
- /// \note gh.run() is just a shortcut of the following code.
- /// \code
- /// ght.init();
- /// ght.start();
- /// \endcode
+ /// This function runs the Gomory-Hu algorithm.
void run() {
init();
start();
}
+
+ /// @}
- /// \brief Returns the predecessor node in the Gomory-Hu tree.
+ ///\name Query Functions
+ ///The results of the algorithm can be obtained using these
+ ///functions.\n
+ ///The \ref run() "run()" should be called before using them.\n
+ ///See also MinCutNodeIt and MinCutEdgeIt
+
+ ///@{
+
+ /// \brief Return the predecessor node in the Gomory-Hu tree.
///
- /// Returns the predecessor node in the Gomory-Hu tree. If the node is
+ /// This function returns the predecessor node in the Gomory-Hu tree.
+ /// If the node is
/// the root of the Gomory-Hu tree, then it returns \c INVALID.
Node predNode(const Node& node) {
return (*_pred)[node];
}
- /// \brief Returns the weight of the predecessor arc in the
+ /// \brief Return the distance from the root node in the Gomory-Hu tree.
+ ///
+ /// This function returns the distance of \c node from the root node
+ /// in the Gomory-Hu tree.
+ int rootDist(const Node& node) {
+ return (*_order)[node];
+ }
+
+ /// \brief Return the weight of the predecessor edge in the
/// Gomory-Hu tree.
///
- /// Returns the weight of the predecessor arc in the Gomory-Hu
- /// tree. If the node is the root of the Gomory-Hu tree, the
- /// result is undefined.
+ /// This function returns the weight of the predecessor edge in the
+ /// Gomory-Hu tree. If the node is the root, the result is undefined.
Value predValue(const Node& node) {
return (*_weight)[node];
}
- /// \brief Returns the minimum cut value between two nodes
+ /// \brief Return the minimum cut value between two nodes
///
- /// Returns the minimum cut value between two nodes. The
+ /// This function returns the minimum cut value between two nodes. The
/// algorithm finds the nearest common ancestor in the Gomory-Hu
/// tree and calculates the minimum weight arc on the paths to
/// the ancestor.
@@ -228,41 +258,52 @@
while (sn != tn) {
if ((*_order)[sn] < (*_order)[tn]) {
- if ((*_weight)[tn] < value) value = (*_weight)[tn];
+ if ((*_weight)[tn] <= value) value = (*_weight)[tn];
tn = (*_pred)[tn];
} else {
- if ((*_weight)[sn] < value) value = (*_weight)[sn];
+ if ((*_weight)[sn] <= value) value = (*_weight)[sn];
sn = (*_pred)[sn];
}
}
return value;
}
- /// \brief Returns the minimum cut between two nodes
+ /// \brief Return the minimum cut between two nodes
///
- /// Returns the minimum cut value between two nodes. The
- /// algorithm finds the nearest common ancestor in the Gomory-Hu
- /// tree and calculates the minimum weight arc on the paths to
- /// the ancestor. Then it sets all nodes to the cut determined by
- /// this arc. The \c cutMap should be \ref concepts::ReadWriteMap
+ /// This function returns the minimum cut between the nodes \c s and \c t
+ /// the \r cutMap parameter by setting the nodes in the component of
+ /// \c \s to true and the other nodes to false.
+ ///
+ /// The \c cutMap should be \ref concepts::ReadWriteMap
/// "ReadWriteMap".
+ ///
+ /// For higher level interfaces, see MinCutNodeIt and MinCutEdgeIt
template <typename CutMap>
- Value minCutMap(const Node& s, const Node& t, CutMap& cutMap) const {
+ Value minCutMap(const Node& s, ///< Base node
+ const Node& t,
+ ///< The node you want to separate from Node s.
+ CutMap& cutMap
+ ///< The cut will be return in this map.
+ /// It must be a \c bool \ref concepts::ReadWriteMap
+ /// "ReadWriteMap" on the graph nodes.
+ ) const {
Node sn = s, tn = t;
-
+ bool s_root=false;
Node rn = INVALID;
Value value = std::numeric_limits<Value>::max();
while (sn != tn) {
if ((*_order)[sn] < (*_order)[tn]) {
- if ((*_weight)[tn] < value) {
+ if ((*_weight)[tn] <= value) {
rn = tn;
+ s_root = false;
value = (*_weight)[tn];
}
tn = (*_pred)[tn];
} else {
- if ((*_weight)[sn] < value) {
+ if ((*_weight)[sn] <= value) {
rn = sn;
+ s_root = true;
value = (*_weight)[sn];
}
sn = (*_pred)[sn];
@@ -271,13 +312,14 @@
typename Graph::template NodeMap<bool> reached(_graph, false);
reached.set(_root, true);
- cutMap.set(_root, false);
+ cutMap.set(_root, !s_root);
reached.set(rn, true);
- cutMap.set(rn, true);
+ cutMap.set(rn, s_root);
+ std::vector<Node> st;
for (NodeIt n(_graph); n != INVALID; ++n) {
- std::vector<Node> st;
- Node nn = n;
+ st.clear();
+ Node nn = n;
while (!reached[nn]) {
st.push_back(nn);
nn = (*_pred)[nn];
@@ -291,6 +333,220 @@
return value;
}
+ ///@}
+
+ friend class MinCutNodeIt;
+
+ /// Iterate on the nodes of a minimum cut
+
+ /// This iterator class lists the nodes of a minimum cut found by
+ /// GomoryHuTree. Before using it, you must allocate a GomoryHuTree class,
+ /// and call its \ref GomoryHuTree::run() "run()" method.
+ ///
+ /// This example counts the nodes in the minimum cut separating \c s from
+ /// \c t.
+ /// \code
+ /// GomoruHuTree<Graph> gom(g, capacities);
+ /// gom.run();
+ /// int sum=0;
+ /// for(GomoruHuTree<Graph>::MinCutNodeIt n(gom,s,t);n!=INVALID;++n) ++sum;
+ /// \endcode
+ class MinCutNodeIt
+ {
+ bool _side;
+ typename Graph::NodeIt _node_it;
+ typename Graph::template NodeMap<bool> _cut;
+ public:
+ /// Constructor
+
+ /// Constructor
+ ///
+ MinCutNodeIt(GomoryHuTree const &gomory,
+ ///< The GomoryHuTree class. You must call its
+ /// run() method
+ /// before initializing this iterator
+ const Node& s, ///< Base node
+ const Node& t,
+ ///< The node you want to separate from Node s.
+ bool side=true
+ ///< If it is \c true (default) then the iterator lists
+ /// the nodes of the component containing \c s,
+ /// otherwise it lists the other component.
+ /// \note As the minimum cut is not always unique,
+ /// \code
+ /// MinCutNodeIt(gomory, s, t, true);
+ /// \endcode
+ /// and
+ /// \code
+ /// MinCutNodeIt(gomory, t, s, false);
+ /// \endcode
+ /// does not necessarily give the same set of nodes.
+ /// However it is ensured that
+ /// \code
+ /// MinCutNodeIt(gomory, s, t, true);
+ /// \endcode
+ /// and
+ /// \code
+ /// MinCutNodeIt(gomory, s, t, false);
+ /// \endcode
+ /// together list each node exactly once.
+ )
+ : _side(side), _cut(gomory._graph)
+ {
+ gomory.minCutMap(s,t,_cut);
+ for(_node_it=typename Graph::NodeIt(gomory._graph);
+ _node_it!=INVALID && _cut[_node_it]!=_side;
+ ++_node_it) {}
+ }
+ /// Conversion to Node
+
+ /// Conversion to Node
+ ///
+ operator typename Graph::Node() const
+ {
+ return _node_it;
+ }
+ bool operator==(Invalid) { return _node_it==INVALID; }
+ bool operator!=(Invalid) { return _node_it!=INVALID; }
+ /// Next node
+
+ /// Next node
+ ///
+ MinCutNodeIt &operator++()
+ {
+ for(++_node_it;_node_it!=INVALID&&_cut[_node_it]!=_side;++_node_it) {}
+ return *this;
+ }
+ /// Postfix incrementation
+
+ /// Postfix incrementation
+ ///
+ /// \warning This incrementation
+ /// returns a \c Node, not a \ref MinCutNodeIt, as one may
+ /// expect.
+ typename Graph::Node operator++(int)
+ {
+ typename Graph::Node n=*this;
+ ++(*this);
+ return n;
+ }
+ };
+
+ friend class MinCutEdgeIt;
+
+ /// Iterate on the edges of a minimum cut
+
+ /// This iterator class lists the edges of a minimum cut found by
+ /// GomoryHuTree. Before using it, you must allocate a GomoryHuTree class,
+ /// and call its \ref GomoryHuTree::run() "run()" method.
+ ///
+ /// This example computes the value of the minimum cut separating \c s from
+ /// \c t.
+ /// \code
+ /// GomoruHuTree<Graph> gom(g, capacities);
+ /// gom.run();
+ /// int value=0;
+ /// for(GomoruHuTree<Graph>::MinCutEdgeIt e(gom,s,t);e!=INVALID;++e)
+ /// value+=capacities[e];
+ /// \endcode
+ /// the result will be the same as it is returned by
+ /// \ref GomoryHuTree::minCostValue() "gom.minCostValue(s,t)"
+ class MinCutEdgeIt
+ {
+ bool _side;
+ const Graph &_graph;
+ typename Graph::NodeIt _node_it;
+ typename Graph::OutArcIt _arc_it;
+ typename Graph::template NodeMap<bool> _cut;
+ void step()
+ {
+ ++_arc_it;
+ while(_node_it!=INVALID && _arc_it==INVALID)
+ {
+ for(++_node_it;_node_it!=INVALID&&!_cut[_node_it];++_node_it) {}
+ if(_node_it!=INVALID)
+ _arc_it=typename Graph::OutArcIt(_graph,_node_it);
+ }
+ }
+
+ public:
+ MinCutEdgeIt(GomoryHuTree const &gomory,
+ ///< The GomoryHuTree class. You must call its
+ /// run() method
+ /// before initializing this iterator
+ const Node& s, ///< Base node
+ const Node& t,
+ ///< The node you want to separate from Node s.
+ bool side=true
+ ///< If it is \c true (default) then the listed arcs
+ /// will be oriented from the
+ /// the nodes of the component containing \c s,
+ /// otherwise they will be oriented in the opposite
+ /// direction.
+ )
+ : _graph(gomory._graph), _cut(_graph)
+ {
+ gomory.minCutMap(s,t,_cut);
+ if(!side)
+ for(typename Graph::NodeIt n(_graph);n!=INVALID;++n)
+ _cut[n]=!_cut[n];
+
+ for(_node_it=typename Graph::NodeIt(_graph);
+ _node_it!=INVALID && !_cut[_node_it];
+ ++_node_it) {}
+ _arc_it = _node_it!=INVALID ?
+ typename Graph::OutArcIt(_graph,_node_it) : INVALID;
+ while(_node_it!=INVALID && _arc_it == INVALID)
+ {
+ for(++_node_it; _node_it!=INVALID&&!_cut[_node_it]; ++_node_it) {}
+ if(_node_it!=INVALID)
+ _arc_it= typename Graph::OutArcIt(_graph,_node_it);
+ }
+ while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step();
+ }
+ /// Conversion to Arc
+
+ /// Conversion to Arc
+ ///
+ operator typename Graph::Arc() const
+ {
+ return _arc_it;
+ }
+ /// Conversion to Edge
+
+ /// Conversion to Edge
+ ///
+ operator typename Graph::Edge() const
+ {
+ return _arc_it;
+ }
+ bool operator==(Invalid) { return _node_it==INVALID; }
+ bool operator!=(Invalid) { return _node_it!=INVALID; }
+ /// Next edge
+
+ /// Next edge
+ ///
+ MinCutEdgeIt &operator++()
+ {
+ step();
+ while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step();
+ return *this;
+ }
+ /// Postfix incrementation
+
+ /// Postfix incrementation
+ ///
+ /// \warning This incrementation
+ /// returns a \c Arc, not a \ref MinCutEdgeIt, as one may
+ /// expect.
+ typename Graph::Arc operator++(int)
+ {
+ typename Graph::Arc e=*this;
+ ++(*this);
+ return e;
+ }
+ };
+
};
}
diff -r 924887566bf2 -r ccd2d3a3001e test/gomory_hu_test.cc
--- a/test/gomory_hu_test.cc Fri Feb 20 17:17:17 2009 +0100
+++ b/test/gomory_hu_test.cc Wed Feb 25 11:10:52 2009 +0000
@@ -2,11 +2,7 @@
#include "test_tools.h"
#include <lemon/smart_graph.h>
-#include <lemon/adaptors.h>
#include <lemon/lgf_reader.h>
-#include <lemon/lgf_writer.h>
-#include <lemon/dimacs.h>
-#include <lemon/time_measure.h>
#include <lemon/gomory_hu_tree.h>
#include <cstdlib>
@@ -77,6 +73,18 @@
check(pf.flowValue() == ght.minCutValue(u, v), "Wrong cut 1");
check(cm[u] != cm[v], "Wrong cut 3");
check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 2");
+
+ int sum=0;
+ for(GomoryHuTree<Graph>::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a)
+ sum+=capacity[a];
+ check(sum == ght.minCutValue(u, v), "Problem with MinCutEdgeIt");
+
+ sum=0;
+ for(GomoryHuTree<Graph>::MinCutNodeIt n(ght, u, v,true);n!=INVALID;++n)
+ sum++;
+ for(GomoryHuTree<Graph>::MinCutNodeIt n(ght, u, v,false);n!=INVALID;++n)
+ sum++;
+ check(sum == countNodes(graph), "Problem with MinCutNodeIt");
}
}