1.1 --- a/lemon/gomory_hu_tree.h Fri Feb 20 17:17:17 2009 +0100
1.2 +++ b/lemon/gomory_hu_tree.h Wed Feb 25 11:10:52 2009 +0000
1.3 @@ -21,6 +21,7 @@
1.4
1.5 #include <limits>
1.6
1.7 +#include <lemon/core.h>
1.8 #include <lemon/preflow.h>
1.9 #include <lemon/concept_check.h>
1.10 #include <lemon/concepts/maps.h>
1.11 @@ -35,31 +36,40 @@
1.12 ///
1.13 /// \brief Gomory-Hu cut tree algorithm
1.14 ///
1.15 - /// The Gomory-Hu tree is a tree on the nodeset of the digraph, but it
1.16 - /// may contain arcs which are not in the original digraph. It helps
1.17 - /// to calculate the minimum cut between all pairs of nodes, because
1.18 - /// the minimum capacity arc on the tree path between two nodes has
1.19 - /// the same weight as the minimum cut in the digraph between these
1.20 - /// nodes. Moreover this arc separates the nodes to two parts which
1.21 - /// determine this minimum cut.
1.22 + /// The Gomory-Hu tree is a tree on the node set of the graph, but it
1.23 + /// may contain edges which are not in the original digraph. It has the
1.24 + /// property that the minimum capacity edge of the path between two nodes
1.25 + /// in this tree has the same weight as the minimum cut in the digraph
1.26 + /// between these nodes. Moreover the components obtained by removing
1.27 + /// this edge from the tree determine the corresponding minimum cut.
1.28 + ///
1.29 + /// Therefore once this tree is computed, the minimum cut between any pair
1.30 + /// of nodes can easily be obtained.
1.31 ///
1.32 - /// The algorithm calculates \e n-1 distinict minimum cuts with
1.33 - /// preflow algorithm, therefore the algorithm has
1.34 + /// The algorithm calculates \e n-1 distinct minimum cuts (currently with
1.35 + /// the \ref Preflow algorithm), therefore the algorithm has
1.36 /// \f$(O(n^3\sqrt{e})\f$ overall time complexity. It calculates a
1.37 - /// rooted Gomory-Hu tree, the structure of the tree and the weights
1.38 - /// can be obtained with \c predNode() and \c predValue()
1.39 - /// functions. The \c minCutValue() and \c minCutMap() calculates
1.40 + /// rooted Gomory-Hu tree, its structure and the weights can be obtained
1.41 + /// by \c predNode(), \c predValue() and \c rootDist().
1.42 + ///
1.43 + /// The members \c minCutMap() and \c minCutValue() calculate
1.44 /// the minimum cut and the minimum cut value between any two node
1.45 - /// in the digraph.
1.46 - template <typename _Graph,
1.47 - typename _Capacity = typename _Graph::template EdgeMap<int> >
1.48 + /// in the digraph. You can also list (iterate on) the nodes and the
1.49 + /// edges of the cuts using MinCutNodeIt and MinCutEdgeIt.
1.50 + ///
1.51 + /// \tparam GR The undirected graph data structure the algorithm will run on
1.52 + /// \tparam CAP type of the EdgeMap describing the Edge capacities.
1.53 + /// it is typename GR::template EdgeMap<int> by default.
1.54 + template <typename GR,
1.55 + typename CAP = typename GR::template EdgeMap<int>
1.56 + >
1.57 class GomoryHuTree {
1.58 public:
1.59
1.60 /// The graph type
1.61 - typedef _Graph Graph;
1.62 - /// The capacity on edges
1.63 - typedef _Capacity Capacity;
1.64 + typedef GR Graph;
1.65 + /// The type if the edge capacity map
1.66 + typedef CAP Capacity;
1.67 /// The value type of capacities
1.68 typedef typename Capacity::Value Value;
1.69
1.70 @@ -104,7 +114,7 @@
1.71 /// \brief Constructor
1.72 ///
1.73 /// Constructor
1.74 - /// \param graph The graph type.
1.75 + /// \param graph The graph the algorithm will run on.
1.76 /// \param capacity The capacity map.
1.77 GomoryHuTree(const Graph& graph, const Capacity& capacity)
1.78 : _graph(graph), _capacity(capacity),
1.79 @@ -121,10 +131,10 @@
1.80 destroyStructures();
1.81 }
1.82
1.83 - /// \brief Initializes the internal data structures.
1.84 - ///
1.85 - /// Initializes the internal data structures.
1.86 - ///
1.87 + // \brief Initialize the internal data structures.
1.88 + //
1.89 + // This function initializes the internal data structures.
1.90 + //
1.91 void init() {
1.92 createStructures();
1.93
1.94 @@ -138,9 +148,12 @@
1.95 }
1.96
1.97
1.98 - /// \brief Starts the algorithm
1.99 - ///
1.100 - /// Starts the algorithm.
1.101 + // \brief Start the algorithm
1.102 + //
1.103 + // This function starts the algorithm.
1.104 + //
1.105 + // \pre \ref init() must be called before using this function.
1.106 + //
1.107 void start() {
1.108 Preflow<Graph, Capacity> fa(_graph, _capacity, _root, INVALID);
1.109
1.110 @@ -185,40 +198,57 @@
1.111 }
1.112 }
1.113
1.114 - /// \brief Runs the Gomory-Hu algorithm.
1.115 + ///\name Execution Control
1.116 +
1.117 + ///@{
1.118 +
1.119 + /// \brief Run the Gomory-Hu algorithm.
1.120 ///
1.121 - /// Runs the Gomory-Hu algorithm.
1.122 - /// \note gh.run() is just a shortcut of the following code.
1.123 - /// \code
1.124 - /// ght.init();
1.125 - /// ght.start();
1.126 - /// \endcode
1.127 + /// This function runs the Gomory-Hu algorithm.
1.128 void run() {
1.129 init();
1.130 start();
1.131 }
1.132 +
1.133 + /// @}
1.134
1.135 - /// \brief Returns the predecessor node in the Gomory-Hu tree.
1.136 + ///\name Query Functions
1.137 + ///The results of the algorithm can be obtained using these
1.138 + ///functions.\n
1.139 + ///The \ref run() "run()" should be called before using them.\n
1.140 + ///See also MinCutNodeIt and MinCutEdgeIt
1.141 +
1.142 + ///@{
1.143 +
1.144 + /// \brief Return the predecessor node in the Gomory-Hu tree.
1.145 ///
1.146 - /// Returns the predecessor node in the Gomory-Hu tree. If the node is
1.147 + /// This function returns the predecessor node in the Gomory-Hu tree.
1.148 + /// If the node is
1.149 /// the root of the Gomory-Hu tree, then it returns \c INVALID.
1.150 Node predNode(const Node& node) {
1.151 return (*_pred)[node];
1.152 }
1.153
1.154 - /// \brief Returns the weight of the predecessor arc in the
1.155 + /// \brief Return the distance from the root node in the Gomory-Hu tree.
1.156 + ///
1.157 + /// This function returns the distance of \c node from the root node
1.158 + /// in the Gomory-Hu tree.
1.159 + int rootDist(const Node& node) {
1.160 + return (*_order)[node];
1.161 + }
1.162 +
1.163 + /// \brief Return the weight of the predecessor edge in the
1.164 /// Gomory-Hu tree.
1.165 ///
1.166 - /// Returns the weight of the predecessor arc in the Gomory-Hu
1.167 - /// tree. If the node is the root of the Gomory-Hu tree, the
1.168 - /// result is undefined.
1.169 + /// This function returns the weight of the predecessor edge in the
1.170 + /// Gomory-Hu tree. If the node is the root, the result is undefined.
1.171 Value predValue(const Node& node) {
1.172 return (*_weight)[node];
1.173 }
1.174
1.175 - /// \brief Returns the minimum cut value between two nodes
1.176 + /// \brief Return the minimum cut value between two nodes
1.177 ///
1.178 - /// Returns the minimum cut value between two nodes. The
1.179 + /// This function returns the minimum cut value between two nodes. The
1.180 /// algorithm finds the nearest common ancestor in the Gomory-Hu
1.181 /// tree and calculates the minimum weight arc on the paths to
1.182 /// the ancestor.
1.183 @@ -228,41 +258,52 @@
1.184
1.185 while (sn != tn) {
1.186 if ((*_order)[sn] < (*_order)[tn]) {
1.187 - if ((*_weight)[tn] < value) value = (*_weight)[tn];
1.188 + if ((*_weight)[tn] <= value) value = (*_weight)[tn];
1.189 tn = (*_pred)[tn];
1.190 } else {
1.191 - if ((*_weight)[sn] < value) value = (*_weight)[sn];
1.192 + if ((*_weight)[sn] <= value) value = (*_weight)[sn];
1.193 sn = (*_pred)[sn];
1.194 }
1.195 }
1.196 return value;
1.197 }
1.198
1.199 - /// \brief Returns the minimum cut between two nodes
1.200 + /// \brief Return the minimum cut between two nodes
1.201 ///
1.202 - /// Returns the minimum cut value between two nodes. The
1.203 - /// algorithm finds the nearest common ancestor in the Gomory-Hu
1.204 - /// tree and calculates the minimum weight arc on the paths to
1.205 - /// the ancestor. Then it sets all nodes to the cut determined by
1.206 - /// this arc. The \c cutMap should be \ref concepts::ReadWriteMap
1.207 + /// This function returns the minimum cut between the nodes \c s and \c t
1.208 + /// the \r cutMap parameter by setting the nodes in the component of
1.209 + /// \c \s to true and the other nodes to false.
1.210 + ///
1.211 + /// The \c cutMap should be \ref concepts::ReadWriteMap
1.212 /// "ReadWriteMap".
1.213 + ///
1.214 + /// For higher level interfaces, see MinCutNodeIt and MinCutEdgeIt
1.215 template <typename CutMap>
1.216 - Value minCutMap(const Node& s, const Node& t, CutMap& cutMap) const {
1.217 + Value minCutMap(const Node& s, ///< Base node
1.218 + const Node& t,
1.219 + ///< The node you want to separate from Node s.
1.220 + CutMap& cutMap
1.221 + ///< The cut will be return in this map.
1.222 + /// It must be a \c bool \ref concepts::ReadWriteMap
1.223 + /// "ReadWriteMap" on the graph nodes.
1.224 + ) const {
1.225 Node sn = s, tn = t;
1.226 -
1.227 + bool s_root=false;
1.228 Node rn = INVALID;
1.229 Value value = std::numeric_limits<Value>::max();
1.230
1.231 while (sn != tn) {
1.232 if ((*_order)[sn] < (*_order)[tn]) {
1.233 - if ((*_weight)[tn] < value) {
1.234 + if ((*_weight)[tn] <= value) {
1.235 rn = tn;
1.236 + s_root = false;
1.237 value = (*_weight)[tn];
1.238 }
1.239 tn = (*_pred)[tn];
1.240 } else {
1.241 - if ((*_weight)[sn] < value) {
1.242 + if ((*_weight)[sn] <= value) {
1.243 rn = sn;
1.244 + s_root = true;
1.245 value = (*_weight)[sn];
1.246 }
1.247 sn = (*_pred)[sn];
1.248 @@ -271,13 +312,14 @@
1.249
1.250 typename Graph::template NodeMap<bool> reached(_graph, false);
1.251 reached.set(_root, true);
1.252 - cutMap.set(_root, false);
1.253 + cutMap.set(_root, !s_root);
1.254 reached.set(rn, true);
1.255 - cutMap.set(rn, true);
1.256 + cutMap.set(rn, s_root);
1.257
1.258 + std::vector<Node> st;
1.259 for (NodeIt n(_graph); n != INVALID; ++n) {
1.260 - std::vector<Node> st;
1.261 - Node nn = n;
1.262 + st.clear();
1.263 + Node nn = n;
1.264 while (!reached[nn]) {
1.265 st.push_back(nn);
1.266 nn = (*_pred)[nn];
1.267 @@ -291,6 +333,220 @@
1.268 return value;
1.269 }
1.270
1.271 + ///@}
1.272 +
1.273 + friend class MinCutNodeIt;
1.274 +
1.275 + /// Iterate on the nodes of a minimum cut
1.276 +
1.277 + /// This iterator class lists the nodes of a minimum cut found by
1.278 + /// GomoryHuTree. Before using it, you must allocate a GomoryHuTree class,
1.279 + /// and call its \ref GomoryHuTree::run() "run()" method.
1.280 + ///
1.281 + /// This example counts the nodes in the minimum cut separating \c s from
1.282 + /// \c t.
1.283 + /// \code
1.284 + /// GomoruHuTree<Graph> gom(g, capacities);
1.285 + /// gom.run();
1.286 + /// int sum=0;
1.287 + /// for(GomoruHuTree<Graph>::MinCutNodeIt n(gom,s,t);n!=INVALID;++n) ++sum;
1.288 + /// \endcode
1.289 + class MinCutNodeIt
1.290 + {
1.291 + bool _side;
1.292 + typename Graph::NodeIt _node_it;
1.293 + typename Graph::template NodeMap<bool> _cut;
1.294 + public:
1.295 + /// Constructor
1.296 +
1.297 + /// Constructor
1.298 + ///
1.299 + MinCutNodeIt(GomoryHuTree const &gomory,
1.300 + ///< The GomoryHuTree class. You must call its
1.301 + /// run() method
1.302 + /// before initializing this iterator
1.303 + const Node& s, ///< Base node
1.304 + const Node& t,
1.305 + ///< The node you want to separate from Node s.
1.306 + bool side=true
1.307 + ///< If it is \c true (default) then the iterator lists
1.308 + /// the nodes of the component containing \c s,
1.309 + /// otherwise it lists the other component.
1.310 + /// \note As the minimum cut is not always unique,
1.311 + /// \code
1.312 + /// MinCutNodeIt(gomory, s, t, true);
1.313 + /// \endcode
1.314 + /// and
1.315 + /// \code
1.316 + /// MinCutNodeIt(gomory, t, s, false);
1.317 + /// \endcode
1.318 + /// does not necessarily give the same set of nodes.
1.319 + /// However it is ensured that
1.320 + /// \code
1.321 + /// MinCutNodeIt(gomory, s, t, true);
1.322 + /// \endcode
1.323 + /// and
1.324 + /// \code
1.325 + /// MinCutNodeIt(gomory, s, t, false);
1.326 + /// \endcode
1.327 + /// together list each node exactly once.
1.328 + )
1.329 + : _side(side), _cut(gomory._graph)
1.330 + {
1.331 + gomory.minCutMap(s,t,_cut);
1.332 + for(_node_it=typename Graph::NodeIt(gomory._graph);
1.333 + _node_it!=INVALID && _cut[_node_it]!=_side;
1.334 + ++_node_it) {}
1.335 + }
1.336 + /// Conversion to Node
1.337 +
1.338 + /// Conversion to Node
1.339 + ///
1.340 + operator typename Graph::Node() const
1.341 + {
1.342 + return _node_it;
1.343 + }
1.344 + bool operator==(Invalid) { return _node_it==INVALID; }
1.345 + bool operator!=(Invalid) { return _node_it!=INVALID; }
1.346 + /// Next node
1.347 +
1.348 + /// Next node
1.349 + ///
1.350 + MinCutNodeIt &operator++()
1.351 + {
1.352 + for(++_node_it;_node_it!=INVALID&&_cut[_node_it]!=_side;++_node_it) {}
1.353 + return *this;
1.354 + }
1.355 + /// Postfix incrementation
1.356 +
1.357 + /// Postfix incrementation
1.358 + ///
1.359 + /// \warning This incrementation
1.360 + /// returns a \c Node, not a \ref MinCutNodeIt, as one may
1.361 + /// expect.
1.362 + typename Graph::Node operator++(int)
1.363 + {
1.364 + typename Graph::Node n=*this;
1.365 + ++(*this);
1.366 + return n;
1.367 + }
1.368 + };
1.369 +
1.370 + friend class MinCutEdgeIt;
1.371 +
1.372 + /// Iterate on the edges of a minimum cut
1.373 +
1.374 + /// This iterator class lists the edges of a minimum cut found by
1.375 + /// GomoryHuTree. Before using it, you must allocate a GomoryHuTree class,
1.376 + /// and call its \ref GomoryHuTree::run() "run()" method.
1.377 + ///
1.378 + /// This example computes the value of the minimum cut separating \c s from
1.379 + /// \c t.
1.380 + /// \code
1.381 + /// GomoruHuTree<Graph> gom(g, capacities);
1.382 + /// gom.run();
1.383 + /// int value=0;
1.384 + /// for(GomoruHuTree<Graph>::MinCutEdgeIt e(gom,s,t);e!=INVALID;++e)
1.385 + /// value+=capacities[e];
1.386 + /// \endcode
1.387 + /// the result will be the same as it is returned by
1.388 + /// \ref GomoryHuTree::minCostValue() "gom.minCostValue(s,t)"
1.389 + class MinCutEdgeIt
1.390 + {
1.391 + bool _side;
1.392 + const Graph &_graph;
1.393 + typename Graph::NodeIt _node_it;
1.394 + typename Graph::OutArcIt _arc_it;
1.395 + typename Graph::template NodeMap<bool> _cut;
1.396 + void step()
1.397 + {
1.398 + ++_arc_it;
1.399 + while(_node_it!=INVALID && _arc_it==INVALID)
1.400 + {
1.401 + for(++_node_it;_node_it!=INVALID&&!_cut[_node_it];++_node_it) {}
1.402 + if(_node_it!=INVALID)
1.403 + _arc_it=typename Graph::OutArcIt(_graph,_node_it);
1.404 + }
1.405 + }
1.406 +
1.407 + public:
1.408 + MinCutEdgeIt(GomoryHuTree const &gomory,
1.409 + ///< The GomoryHuTree class. You must call its
1.410 + /// run() method
1.411 + /// before initializing this iterator
1.412 + const Node& s, ///< Base node
1.413 + const Node& t,
1.414 + ///< The node you want to separate from Node s.
1.415 + bool side=true
1.416 + ///< If it is \c true (default) then the listed arcs
1.417 + /// will be oriented from the
1.418 + /// the nodes of the component containing \c s,
1.419 + /// otherwise they will be oriented in the opposite
1.420 + /// direction.
1.421 + )
1.422 + : _graph(gomory._graph), _cut(_graph)
1.423 + {
1.424 + gomory.minCutMap(s,t,_cut);
1.425 + if(!side)
1.426 + for(typename Graph::NodeIt n(_graph);n!=INVALID;++n)
1.427 + _cut[n]=!_cut[n];
1.428 +
1.429 + for(_node_it=typename Graph::NodeIt(_graph);
1.430 + _node_it!=INVALID && !_cut[_node_it];
1.431 + ++_node_it) {}
1.432 + _arc_it = _node_it!=INVALID ?
1.433 + typename Graph::OutArcIt(_graph,_node_it) : INVALID;
1.434 + while(_node_it!=INVALID && _arc_it == INVALID)
1.435 + {
1.436 + for(++_node_it; _node_it!=INVALID&&!_cut[_node_it]; ++_node_it) {}
1.437 + if(_node_it!=INVALID)
1.438 + _arc_it= typename Graph::OutArcIt(_graph,_node_it);
1.439 + }
1.440 + while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step();
1.441 + }
1.442 + /// Conversion to Arc
1.443 +
1.444 + /// Conversion to Arc
1.445 + ///
1.446 + operator typename Graph::Arc() const
1.447 + {
1.448 + return _arc_it;
1.449 + }
1.450 + /// Conversion to Edge
1.451 +
1.452 + /// Conversion to Edge
1.453 + ///
1.454 + operator typename Graph::Edge() const
1.455 + {
1.456 + return _arc_it;
1.457 + }
1.458 + bool operator==(Invalid) { return _node_it==INVALID; }
1.459 + bool operator!=(Invalid) { return _node_it!=INVALID; }
1.460 + /// Next edge
1.461 +
1.462 + /// Next edge
1.463 + ///
1.464 + MinCutEdgeIt &operator++()
1.465 + {
1.466 + step();
1.467 + while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step();
1.468 + return *this;
1.469 + }
1.470 + /// Postfix incrementation
1.471 +
1.472 + /// Postfix incrementation
1.473 + ///
1.474 + /// \warning This incrementation
1.475 + /// returns a \c Arc, not a \ref MinCutEdgeIt, as one may
1.476 + /// expect.
1.477 + typename Graph::Arc operator++(int)
1.478 + {
1.479 + typename Graph::Arc e=*this;
1.480 + ++(*this);
1.481 + return e;
1.482 + }
1.483 + };
1.484 +
1.485 };
1.486
1.487 }