1.1 --- a/lemon/Makefile.am Wed Feb 25 11:10:52 2009 +0000
1.2 +++ b/lemon/Makefile.am Wed Feb 25 11:10:57 2009 +0000
1.3 @@ -68,7 +68,7 @@
1.4 lemon/euler.h \
1.5 lemon/full_graph.h \
1.6 lemon/glpk.h \
1.7 - lemon/gomory_hu_tree.h \
1.8 + lemon/gomory_hu.h \
1.9 lemon/graph_to_eps.h \
1.10 lemon/grid_graph.h \
1.11 lemon/hypercube_graph.h \
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/lemon/gomory_hu.h Wed Feb 25 11:10:57 2009 +0000
2.3 @@ -0,0 +1,554 @@
2.4 +/* -*- C++ -*-
2.5 + *
2.6 + * This file is a part of LEMON, a generic C++ optimization library
2.7 + *
2.8 + * Copyright (C) 2003-2008
2.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
2.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
2.11 + *
2.12 + * Permission to use, modify and distribute this software is granted
2.13 + * provided that this copyright notice appears in all copies. For
2.14 + * precise terms see the accompanying LICENSE file.
2.15 + *
2.16 + * This software is provided "AS IS" with no warranty of any kind,
2.17 + * express or implied, and with no claim as to its suitability for any
2.18 + * purpose.
2.19 + *
2.20 + */
2.21 +
2.22 +#ifndef LEMON_GOMORY_HU_TREE_H
2.23 +#define LEMON_GOMORY_HU_TREE_H
2.24 +
2.25 +#include <limits>
2.26 +
2.27 +#include <lemon/core.h>
2.28 +#include <lemon/preflow.h>
2.29 +#include <lemon/concept_check.h>
2.30 +#include <lemon/concepts/maps.h>
2.31 +
2.32 +/// \ingroup min_cut
2.33 +/// \file
2.34 +/// \brief Gomory-Hu cut tree in graphs.
2.35 +
2.36 +namespace lemon {
2.37 +
2.38 + /// \ingroup min_cut
2.39 + ///
2.40 + /// \brief Gomory-Hu cut tree algorithm
2.41 + ///
2.42 + /// The Gomory-Hu tree is a tree on the node set of the graph, but it
2.43 + /// may contain edges which are not in the original digraph. It has the
2.44 + /// property that the minimum capacity edge of the path between two nodes
2.45 + /// in this tree has the same weight as the minimum cut in the digraph
2.46 + /// between these nodes. Moreover the components obtained by removing
2.47 + /// this edge from the tree determine the corresponding minimum cut.
2.48 + ///
2.49 + /// Therefore once this tree is computed, the minimum cut between any pair
2.50 + /// of nodes can easily be obtained.
2.51 + ///
2.52 + /// The algorithm calculates \e n-1 distinct minimum cuts (currently with
2.53 + /// the \ref Preflow algorithm), therefore the algorithm has
2.54 + /// \f$(O(n^3\sqrt{e})\f$ overall time complexity. It calculates a
2.55 + /// rooted Gomory-Hu tree, its structure and the weights can be obtained
2.56 + /// by \c predNode(), \c predValue() and \c rootDist().
2.57 + ///
2.58 + /// The members \c minCutMap() and \c minCutValue() calculate
2.59 + /// the minimum cut and the minimum cut value between any two node
2.60 + /// in the digraph. You can also list (iterate on) the nodes and the
2.61 + /// edges of the cuts using MinCutNodeIt and MinCutEdgeIt.
2.62 + ///
2.63 + /// \tparam GR The undirected graph data structure the algorithm will run on
2.64 + /// \tparam CAP type of the EdgeMap describing the Edge capacities.
2.65 + /// it is typename GR::template EdgeMap<int> by default.
2.66 + template <typename GR,
2.67 + typename CAP = typename GR::template EdgeMap<int>
2.68 + >
2.69 + class GomoryHu {
2.70 + public:
2.71 +
2.72 + /// The graph type
2.73 + typedef GR Graph;
2.74 + /// The type if the edge capacity map
2.75 + typedef CAP Capacity;
2.76 + /// The value type of capacities
2.77 + typedef typename Capacity::Value Value;
2.78 +
2.79 + private:
2.80 +
2.81 + TEMPLATE_GRAPH_TYPEDEFS(Graph);
2.82 +
2.83 + const Graph& _graph;
2.84 + const Capacity& _capacity;
2.85 +
2.86 + Node _root;
2.87 + typename Graph::template NodeMap<Node>* _pred;
2.88 + typename Graph::template NodeMap<Value>* _weight;
2.89 + typename Graph::template NodeMap<int>* _order;
2.90 +
2.91 + void createStructures() {
2.92 + if (!_pred) {
2.93 + _pred = new typename Graph::template NodeMap<Node>(_graph);
2.94 + }
2.95 + if (!_weight) {
2.96 + _weight = new typename Graph::template NodeMap<Value>(_graph);
2.97 + }
2.98 + if (!_order) {
2.99 + _order = new typename Graph::template NodeMap<int>(_graph);
2.100 + }
2.101 + }
2.102 +
2.103 + void destroyStructures() {
2.104 + if (_pred) {
2.105 + delete _pred;
2.106 + }
2.107 + if (_weight) {
2.108 + delete _weight;
2.109 + }
2.110 + if (_order) {
2.111 + delete _order;
2.112 + }
2.113 + }
2.114 +
2.115 + public:
2.116 +
2.117 + /// \brief Constructor
2.118 + ///
2.119 + /// Constructor
2.120 + /// \param graph The graph the algorithm will run on.
2.121 + /// \param capacity The capacity map.
2.122 + GomoryHu(const Graph& graph, const Capacity& capacity)
2.123 + : _graph(graph), _capacity(capacity),
2.124 + _pred(0), _weight(0), _order(0)
2.125 + {
2.126 + checkConcept<concepts::ReadMap<Edge, Value>, Capacity>();
2.127 + }
2.128 +
2.129 +
2.130 + /// \brief Destructor
2.131 + ///
2.132 + /// Destructor
2.133 + ~GomoryHu() {
2.134 + destroyStructures();
2.135 + }
2.136 +
2.137 + // \brief Initialize the internal data structures.
2.138 + //
2.139 + // This function initializes the internal data structures.
2.140 + //
2.141 + void init() {
2.142 + createStructures();
2.143 +
2.144 + _root = NodeIt(_graph);
2.145 + for (NodeIt n(_graph); n != INVALID; ++n) {
2.146 + _pred->set(n, _root);
2.147 + _order->set(n, -1);
2.148 + }
2.149 + _pred->set(_root, INVALID);
2.150 + _weight->set(_root, std::numeric_limits<Value>::max());
2.151 + }
2.152 +
2.153 +
2.154 + // \brief Start the algorithm
2.155 + //
2.156 + // This function starts the algorithm.
2.157 + //
2.158 + // \pre \ref init() must be called before using this function.
2.159 + //
2.160 + void start() {
2.161 + Preflow<Graph, Capacity> fa(_graph, _capacity, _root, INVALID);
2.162 +
2.163 + for (NodeIt n(_graph); n != INVALID; ++n) {
2.164 + if (n == _root) continue;
2.165 +
2.166 + Node pn = (*_pred)[n];
2.167 + fa.source(n);
2.168 + fa.target(pn);
2.169 +
2.170 + fa.runMinCut();
2.171 +
2.172 + _weight->set(n, fa.flowValue());
2.173 +
2.174 + for (NodeIt nn(_graph); nn != INVALID; ++nn) {
2.175 + if (nn != n && fa.minCut(nn) && (*_pred)[nn] == pn) {
2.176 + _pred->set(nn, n);
2.177 + }
2.178 + }
2.179 + if ((*_pred)[pn] != INVALID && fa.minCut((*_pred)[pn])) {
2.180 + _pred->set(n, (*_pred)[pn]);
2.181 + _pred->set(pn, n);
2.182 + _weight->set(n, (*_weight)[pn]);
2.183 + _weight->set(pn, fa.flowValue());
2.184 + }
2.185 + }
2.186 +
2.187 + _order->set(_root, 0);
2.188 + int index = 1;
2.189 +
2.190 + for (NodeIt n(_graph); n != INVALID; ++n) {
2.191 + std::vector<Node> st;
2.192 + Node nn = n;
2.193 + while ((*_order)[nn] == -1) {
2.194 + st.push_back(nn);
2.195 + nn = (*_pred)[nn];
2.196 + }
2.197 + while (!st.empty()) {
2.198 + _order->set(st.back(), index++);
2.199 + st.pop_back();
2.200 + }
2.201 + }
2.202 + }
2.203 +
2.204 + ///\name Execution Control
2.205 +
2.206 + ///@{
2.207 +
2.208 + /// \brief Run the Gomory-Hu algorithm.
2.209 + ///
2.210 + /// This function runs the Gomory-Hu algorithm.
2.211 + void run() {
2.212 + init();
2.213 + start();
2.214 + }
2.215 +
2.216 + /// @}
2.217 +
2.218 + ///\name Query Functions
2.219 + ///The results of the algorithm can be obtained using these
2.220 + ///functions.\n
2.221 + ///The \ref run() "run()" should be called before using them.\n
2.222 + ///See also MinCutNodeIt and MinCutEdgeIt
2.223 +
2.224 + ///@{
2.225 +
2.226 + /// \brief Return the predecessor node in the Gomory-Hu tree.
2.227 + ///
2.228 + /// This function returns the predecessor node in the Gomory-Hu tree.
2.229 + /// If the node is
2.230 + /// the root of the Gomory-Hu tree, then it returns \c INVALID.
2.231 + Node predNode(const Node& node) {
2.232 + return (*_pred)[node];
2.233 + }
2.234 +
2.235 + /// \brief Return the distance from the root node in the Gomory-Hu tree.
2.236 + ///
2.237 + /// This function returns the distance of \c node from the root node
2.238 + /// in the Gomory-Hu tree.
2.239 + int rootDist(const Node& node) {
2.240 + return (*_order)[node];
2.241 + }
2.242 +
2.243 + /// \brief Return the weight of the predecessor edge in the
2.244 + /// Gomory-Hu tree.
2.245 + ///
2.246 + /// This function returns the weight of the predecessor edge in the
2.247 + /// Gomory-Hu tree. If the node is the root, the result is undefined.
2.248 + Value predValue(const Node& node) {
2.249 + return (*_weight)[node];
2.250 + }
2.251 +
2.252 + /// \brief Return the minimum cut value between two nodes
2.253 + ///
2.254 + /// This function returns the minimum cut value between two nodes. The
2.255 + /// algorithm finds the nearest common ancestor in the Gomory-Hu
2.256 + /// tree and calculates the minimum weight arc on the paths to
2.257 + /// the ancestor.
2.258 + Value minCutValue(const Node& s, const Node& t) const {
2.259 + Node sn = s, tn = t;
2.260 + Value value = std::numeric_limits<Value>::max();
2.261 +
2.262 + while (sn != tn) {
2.263 + if ((*_order)[sn] < (*_order)[tn]) {
2.264 + if ((*_weight)[tn] <= value) value = (*_weight)[tn];
2.265 + tn = (*_pred)[tn];
2.266 + } else {
2.267 + if ((*_weight)[sn] <= value) value = (*_weight)[sn];
2.268 + sn = (*_pred)[sn];
2.269 + }
2.270 + }
2.271 + return value;
2.272 + }
2.273 +
2.274 + /// \brief Return the minimum cut between two nodes
2.275 + ///
2.276 + /// This function returns the minimum cut between the nodes \c s and \c t
2.277 + /// the \r cutMap parameter by setting the nodes in the component of
2.278 + /// \c \s to true and the other nodes to false.
2.279 + ///
2.280 + /// The \c cutMap should be \ref concepts::ReadWriteMap
2.281 + /// "ReadWriteMap".
2.282 + ///
2.283 + /// For higher level interfaces, see MinCutNodeIt and MinCutEdgeIt
2.284 + template <typename CutMap>
2.285 + Value minCutMap(const Node& s, ///< Base node
2.286 + const Node& t,
2.287 + ///< The node you want to separate from Node s.
2.288 + CutMap& cutMap
2.289 + ///< The cut will be return in this map.
2.290 + /// It must be a \c bool \ref concepts::ReadWriteMap
2.291 + /// "ReadWriteMap" on the graph nodes.
2.292 + ) const {
2.293 + Node sn = s, tn = t;
2.294 + bool s_root=false;
2.295 + Node rn = INVALID;
2.296 + Value value = std::numeric_limits<Value>::max();
2.297 +
2.298 + while (sn != tn) {
2.299 + if ((*_order)[sn] < (*_order)[tn]) {
2.300 + if ((*_weight)[tn] <= value) {
2.301 + rn = tn;
2.302 + s_root = false;
2.303 + value = (*_weight)[tn];
2.304 + }
2.305 + tn = (*_pred)[tn];
2.306 + } else {
2.307 + if ((*_weight)[sn] <= value) {
2.308 + rn = sn;
2.309 + s_root = true;
2.310 + value = (*_weight)[sn];
2.311 + }
2.312 + sn = (*_pred)[sn];
2.313 + }
2.314 + }
2.315 +
2.316 + typename Graph::template NodeMap<bool> reached(_graph, false);
2.317 + reached.set(_root, true);
2.318 + cutMap.set(_root, !s_root);
2.319 + reached.set(rn, true);
2.320 + cutMap.set(rn, s_root);
2.321 +
2.322 + std::vector<Node> st;
2.323 + for (NodeIt n(_graph); n != INVALID; ++n) {
2.324 + st.clear();
2.325 + Node nn = n;
2.326 + while (!reached[nn]) {
2.327 + st.push_back(nn);
2.328 + nn = (*_pred)[nn];
2.329 + }
2.330 + while (!st.empty()) {
2.331 + cutMap.set(st.back(), cutMap[nn]);
2.332 + st.pop_back();
2.333 + }
2.334 + }
2.335 +
2.336 + return value;
2.337 + }
2.338 +
2.339 + ///@}
2.340 +
2.341 + friend class MinCutNodeIt;
2.342 +
2.343 + /// Iterate on the nodes of a minimum cut
2.344 +
2.345 + /// This iterator class lists the nodes of a minimum cut found by
2.346 + /// GomoryHu. Before using it, you must allocate a GomoryHu class,
2.347 + /// and call its \ref GomoryHu::run() "run()" method.
2.348 + ///
2.349 + /// This example counts the nodes in the minimum cut separating \c s from
2.350 + /// \c t.
2.351 + /// \code
2.352 + /// GomoruHu<Graph> gom(g, capacities);
2.353 + /// gom.run();
2.354 + /// int sum=0;
2.355 + /// for(GomoruHu<Graph>::MinCutNodeIt n(gom,s,t);n!=INVALID;++n) ++sum;
2.356 + /// \endcode
2.357 + class MinCutNodeIt
2.358 + {
2.359 + bool _side;
2.360 + typename Graph::NodeIt _node_it;
2.361 + typename Graph::template NodeMap<bool> _cut;
2.362 + public:
2.363 + /// Constructor
2.364 +
2.365 + /// Constructor
2.366 + ///
2.367 + MinCutNodeIt(GomoryHu const &gomory,
2.368 + ///< The GomoryHu class. You must call its
2.369 + /// run() method
2.370 + /// before initializing this iterator
2.371 + const Node& s, ///< Base node
2.372 + const Node& t,
2.373 + ///< The node you want to separate from Node s.
2.374 + bool side=true
2.375 + ///< If it is \c true (default) then the iterator lists
2.376 + /// the nodes of the component containing \c s,
2.377 + /// otherwise it lists the other component.
2.378 + /// \note As the minimum cut is not always unique,
2.379 + /// \code
2.380 + /// MinCutNodeIt(gomory, s, t, true);
2.381 + /// \endcode
2.382 + /// and
2.383 + /// \code
2.384 + /// MinCutNodeIt(gomory, t, s, false);
2.385 + /// \endcode
2.386 + /// does not necessarily give the same set of nodes.
2.387 + /// However it is ensured that
2.388 + /// \code
2.389 + /// MinCutNodeIt(gomory, s, t, true);
2.390 + /// \endcode
2.391 + /// and
2.392 + /// \code
2.393 + /// MinCutNodeIt(gomory, s, t, false);
2.394 + /// \endcode
2.395 + /// together list each node exactly once.
2.396 + )
2.397 + : _side(side), _cut(gomory._graph)
2.398 + {
2.399 + gomory.minCutMap(s,t,_cut);
2.400 + for(_node_it=typename Graph::NodeIt(gomory._graph);
2.401 + _node_it!=INVALID && _cut[_node_it]!=_side;
2.402 + ++_node_it) {}
2.403 + }
2.404 + /// Conversion to Node
2.405 +
2.406 + /// Conversion to Node
2.407 + ///
2.408 + operator typename Graph::Node() const
2.409 + {
2.410 + return _node_it;
2.411 + }
2.412 + bool operator==(Invalid) { return _node_it==INVALID; }
2.413 + bool operator!=(Invalid) { return _node_it!=INVALID; }
2.414 + /// Next node
2.415 +
2.416 + /// Next node
2.417 + ///
2.418 + MinCutNodeIt &operator++()
2.419 + {
2.420 + for(++_node_it;_node_it!=INVALID&&_cut[_node_it]!=_side;++_node_it) {}
2.421 + return *this;
2.422 + }
2.423 + /// Postfix incrementation
2.424 +
2.425 + /// Postfix incrementation
2.426 + ///
2.427 + /// \warning This incrementation
2.428 + /// returns a \c Node, not a \ref MinCutNodeIt, as one may
2.429 + /// expect.
2.430 + typename Graph::Node operator++(int)
2.431 + {
2.432 + typename Graph::Node n=*this;
2.433 + ++(*this);
2.434 + return n;
2.435 + }
2.436 + };
2.437 +
2.438 + friend class MinCutEdgeIt;
2.439 +
2.440 + /// Iterate on the edges of a minimum cut
2.441 +
2.442 + /// This iterator class lists the edges of a minimum cut found by
2.443 + /// GomoryHu. Before using it, you must allocate a GomoryHu class,
2.444 + /// and call its \ref GomoryHu::run() "run()" method.
2.445 + ///
2.446 + /// This example computes the value of the minimum cut separating \c s from
2.447 + /// \c t.
2.448 + /// \code
2.449 + /// GomoruHu<Graph> gom(g, capacities);
2.450 + /// gom.run();
2.451 + /// int value=0;
2.452 + /// for(GomoruHu<Graph>::MinCutEdgeIt e(gom,s,t);e!=INVALID;++e)
2.453 + /// value+=capacities[e];
2.454 + /// \endcode
2.455 + /// the result will be the same as it is returned by
2.456 + /// \ref GomoryHu::minCostValue() "gom.minCostValue(s,t)"
2.457 + class MinCutEdgeIt
2.458 + {
2.459 + bool _side;
2.460 + const Graph &_graph;
2.461 + typename Graph::NodeIt _node_it;
2.462 + typename Graph::OutArcIt _arc_it;
2.463 + typename Graph::template NodeMap<bool> _cut;
2.464 + void step()
2.465 + {
2.466 + ++_arc_it;
2.467 + while(_node_it!=INVALID && _arc_it==INVALID)
2.468 + {
2.469 + for(++_node_it;_node_it!=INVALID&&!_cut[_node_it];++_node_it) {}
2.470 + if(_node_it!=INVALID)
2.471 + _arc_it=typename Graph::OutArcIt(_graph,_node_it);
2.472 + }
2.473 + }
2.474 +
2.475 + public:
2.476 + MinCutEdgeIt(GomoryHu const &gomory,
2.477 + ///< The GomoryHu class. You must call its
2.478 + /// run() method
2.479 + /// before initializing this iterator
2.480 + const Node& s, ///< Base node
2.481 + const Node& t,
2.482 + ///< The node you want to separate from Node s.
2.483 + bool side=true
2.484 + ///< If it is \c true (default) then the listed arcs
2.485 + /// will be oriented from the
2.486 + /// the nodes of the component containing \c s,
2.487 + /// otherwise they will be oriented in the opposite
2.488 + /// direction.
2.489 + )
2.490 + : _graph(gomory._graph), _cut(_graph)
2.491 + {
2.492 + gomory.minCutMap(s,t,_cut);
2.493 + if(!side)
2.494 + for(typename Graph::NodeIt n(_graph);n!=INVALID;++n)
2.495 + _cut[n]=!_cut[n];
2.496 +
2.497 + for(_node_it=typename Graph::NodeIt(_graph);
2.498 + _node_it!=INVALID && !_cut[_node_it];
2.499 + ++_node_it) {}
2.500 + _arc_it = _node_it!=INVALID ?
2.501 + typename Graph::OutArcIt(_graph,_node_it) : INVALID;
2.502 + while(_node_it!=INVALID && _arc_it == INVALID)
2.503 + {
2.504 + for(++_node_it; _node_it!=INVALID&&!_cut[_node_it]; ++_node_it) {}
2.505 + if(_node_it!=INVALID)
2.506 + _arc_it= typename Graph::OutArcIt(_graph,_node_it);
2.507 + }
2.508 + while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step();
2.509 + }
2.510 + /// Conversion to Arc
2.511 +
2.512 + /// Conversion to Arc
2.513 + ///
2.514 + operator typename Graph::Arc() const
2.515 + {
2.516 + return _arc_it;
2.517 + }
2.518 + /// Conversion to Edge
2.519 +
2.520 + /// Conversion to Edge
2.521 + ///
2.522 + operator typename Graph::Edge() const
2.523 + {
2.524 + return _arc_it;
2.525 + }
2.526 + bool operator==(Invalid) { return _node_it==INVALID; }
2.527 + bool operator!=(Invalid) { return _node_it!=INVALID; }
2.528 + /// Next edge
2.529 +
2.530 + /// Next edge
2.531 + ///
2.532 + MinCutEdgeIt &operator++()
2.533 + {
2.534 + step();
2.535 + while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step();
2.536 + return *this;
2.537 + }
2.538 + /// Postfix incrementation
2.539 +
2.540 + /// Postfix incrementation
2.541 + ///
2.542 + /// \warning This incrementation
2.543 + /// returns a \c Arc, not a \ref MinCutEdgeIt, as one may
2.544 + /// expect.
2.545 + typename Graph::Arc operator++(int)
2.546 + {
2.547 + typename Graph::Arc e=*this;
2.548 + ++(*this);
2.549 + return e;
2.550 + }
2.551 + };
2.552 +
2.553 + };
2.554 +
2.555 +}
2.556 +
2.557 +#endif
3.1 --- a/lemon/gomory_hu_tree.h Wed Feb 25 11:10:52 2009 +0000
3.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
3.3 @@ -1,554 +0,0 @@
3.4 -/* -*- C++ -*-
3.5 - *
3.6 - * This file is a part of LEMON, a generic C++ optimization library
3.7 - *
3.8 - * Copyright (C) 2003-2008
3.9 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
3.10 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
3.11 - *
3.12 - * Permission to use, modify and distribute this software is granted
3.13 - * provided that this copyright notice appears in all copies. For
3.14 - * precise terms see the accompanying LICENSE file.
3.15 - *
3.16 - * This software is provided "AS IS" with no warranty of any kind,
3.17 - * express or implied, and with no claim as to its suitability for any
3.18 - * purpose.
3.19 - *
3.20 - */
3.21 -
3.22 -#ifndef LEMON_GOMORY_HU_TREE_H
3.23 -#define LEMON_GOMORY_HU_TREE_H
3.24 -
3.25 -#include <limits>
3.26 -
3.27 -#include <lemon/core.h>
3.28 -#include <lemon/preflow.h>
3.29 -#include <lemon/concept_check.h>
3.30 -#include <lemon/concepts/maps.h>
3.31 -
3.32 -/// \ingroup min_cut
3.33 -/// \file
3.34 -/// \brief Gomory-Hu cut tree in graphs.
3.35 -
3.36 -namespace lemon {
3.37 -
3.38 - /// \ingroup min_cut
3.39 - ///
3.40 - /// \brief Gomory-Hu cut tree algorithm
3.41 - ///
3.42 - /// The Gomory-Hu tree is a tree on the node set of the graph, but it
3.43 - /// may contain edges which are not in the original digraph. It has the
3.44 - /// property that the minimum capacity edge of the path between two nodes
3.45 - /// in this tree has the same weight as the minimum cut in the digraph
3.46 - /// between these nodes. Moreover the components obtained by removing
3.47 - /// this edge from the tree determine the corresponding minimum cut.
3.48 - ///
3.49 - /// Therefore once this tree is computed, the minimum cut between any pair
3.50 - /// of nodes can easily be obtained.
3.51 - ///
3.52 - /// The algorithm calculates \e n-1 distinct minimum cuts (currently with
3.53 - /// the \ref Preflow algorithm), therefore the algorithm has
3.54 - /// \f$(O(n^3\sqrt{e})\f$ overall time complexity. It calculates a
3.55 - /// rooted Gomory-Hu tree, its structure and the weights can be obtained
3.56 - /// by \c predNode(), \c predValue() and \c rootDist().
3.57 - ///
3.58 - /// The members \c minCutMap() and \c minCutValue() calculate
3.59 - /// the minimum cut and the minimum cut value between any two node
3.60 - /// in the digraph. You can also list (iterate on) the nodes and the
3.61 - /// edges of the cuts using MinCutNodeIt and MinCutEdgeIt.
3.62 - ///
3.63 - /// \tparam GR The undirected graph data structure the algorithm will run on
3.64 - /// \tparam CAP type of the EdgeMap describing the Edge capacities.
3.65 - /// it is typename GR::template EdgeMap<int> by default.
3.66 - template <typename GR,
3.67 - typename CAP = typename GR::template EdgeMap<int>
3.68 - >
3.69 - class GomoryHuTree {
3.70 - public:
3.71 -
3.72 - /// The graph type
3.73 - typedef GR Graph;
3.74 - /// The type if the edge capacity map
3.75 - typedef CAP Capacity;
3.76 - /// The value type of capacities
3.77 - typedef typename Capacity::Value Value;
3.78 -
3.79 - private:
3.80 -
3.81 - TEMPLATE_GRAPH_TYPEDEFS(Graph);
3.82 -
3.83 - const Graph& _graph;
3.84 - const Capacity& _capacity;
3.85 -
3.86 - Node _root;
3.87 - typename Graph::template NodeMap<Node>* _pred;
3.88 - typename Graph::template NodeMap<Value>* _weight;
3.89 - typename Graph::template NodeMap<int>* _order;
3.90 -
3.91 - void createStructures() {
3.92 - if (!_pred) {
3.93 - _pred = new typename Graph::template NodeMap<Node>(_graph);
3.94 - }
3.95 - if (!_weight) {
3.96 - _weight = new typename Graph::template NodeMap<Value>(_graph);
3.97 - }
3.98 - if (!_order) {
3.99 - _order = new typename Graph::template NodeMap<int>(_graph);
3.100 - }
3.101 - }
3.102 -
3.103 - void destroyStructures() {
3.104 - if (_pred) {
3.105 - delete _pred;
3.106 - }
3.107 - if (_weight) {
3.108 - delete _weight;
3.109 - }
3.110 - if (_order) {
3.111 - delete _order;
3.112 - }
3.113 - }
3.114 -
3.115 - public:
3.116 -
3.117 - /// \brief Constructor
3.118 - ///
3.119 - /// Constructor
3.120 - /// \param graph The graph the algorithm will run on.
3.121 - /// \param capacity The capacity map.
3.122 - GomoryHuTree(const Graph& graph, const Capacity& capacity)
3.123 - : _graph(graph), _capacity(capacity),
3.124 - _pred(0), _weight(0), _order(0)
3.125 - {
3.126 - checkConcept<concepts::ReadMap<Edge, Value>, Capacity>();
3.127 - }
3.128 -
3.129 -
3.130 - /// \brief Destructor
3.131 - ///
3.132 - /// Destructor
3.133 - ~GomoryHuTree() {
3.134 - destroyStructures();
3.135 - }
3.136 -
3.137 - // \brief Initialize the internal data structures.
3.138 - //
3.139 - // This function initializes the internal data structures.
3.140 - //
3.141 - void init() {
3.142 - createStructures();
3.143 -
3.144 - _root = NodeIt(_graph);
3.145 - for (NodeIt n(_graph); n != INVALID; ++n) {
3.146 - _pred->set(n, _root);
3.147 - _order->set(n, -1);
3.148 - }
3.149 - _pred->set(_root, INVALID);
3.150 - _weight->set(_root, std::numeric_limits<Value>::max());
3.151 - }
3.152 -
3.153 -
3.154 - // \brief Start the algorithm
3.155 - //
3.156 - // This function starts the algorithm.
3.157 - //
3.158 - // \pre \ref init() must be called before using this function.
3.159 - //
3.160 - void start() {
3.161 - Preflow<Graph, Capacity> fa(_graph, _capacity, _root, INVALID);
3.162 -
3.163 - for (NodeIt n(_graph); n != INVALID; ++n) {
3.164 - if (n == _root) continue;
3.165 -
3.166 - Node pn = (*_pred)[n];
3.167 - fa.source(n);
3.168 - fa.target(pn);
3.169 -
3.170 - fa.runMinCut();
3.171 -
3.172 - _weight->set(n, fa.flowValue());
3.173 -
3.174 - for (NodeIt nn(_graph); nn != INVALID; ++nn) {
3.175 - if (nn != n && fa.minCut(nn) && (*_pred)[nn] == pn) {
3.176 - _pred->set(nn, n);
3.177 - }
3.178 - }
3.179 - if ((*_pred)[pn] != INVALID && fa.minCut((*_pred)[pn])) {
3.180 - _pred->set(n, (*_pred)[pn]);
3.181 - _pred->set(pn, n);
3.182 - _weight->set(n, (*_weight)[pn]);
3.183 - _weight->set(pn, fa.flowValue());
3.184 - }
3.185 - }
3.186 -
3.187 - _order->set(_root, 0);
3.188 - int index = 1;
3.189 -
3.190 - for (NodeIt n(_graph); n != INVALID; ++n) {
3.191 - std::vector<Node> st;
3.192 - Node nn = n;
3.193 - while ((*_order)[nn] == -1) {
3.194 - st.push_back(nn);
3.195 - nn = (*_pred)[nn];
3.196 - }
3.197 - while (!st.empty()) {
3.198 - _order->set(st.back(), index++);
3.199 - st.pop_back();
3.200 - }
3.201 - }
3.202 - }
3.203 -
3.204 - ///\name Execution Control
3.205 -
3.206 - ///@{
3.207 -
3.208 - /// \brief Run the Gomory-Hu algorithm.
3.209 - ///
3.210 - /// This function runs the Gomory-Hu algorithm.
3.211 - void run() {
3.212 - init();
3.213 - start();
3.214 - }
3.215 -
3.216 - /// @}
3.217 -
3.218 - ///\name Query Functions
3.219 - ///The results of the algorithm can be obtained using these
3.220 - ///functions.\n
3.221 - ///The \ref run() "run()" should be called before using them.\n
3.222 - ///See also MinCutNodeIt and MinCutEdgeIt
3.223 -
3.224 - ///@{
3.225 -
3.226 - /// \brief Return the predecessor node in the Gomory-Hu tree.
3.227 - ///
3.228 - /// This function returns the predecessor node in the Gomory-Hu tree.
3.229 - /// If the node is
3.230 - /// the root of the Gomory-Hu tree, then it returns \c INVALID.
3.231 - Node predNode(const Node& node) {
3.232 - return (*_pred)[node];
3.233 - }
3.234 -
3.235 - /// \brief Return the distance from the root node in the Gomory-Hu tree.
3.236 - ///
3.237 - /// This function returns the distance of \c node from the root node
3.238 - /// in the Gomory-Hu tree.
3.239 - int rootDist(const Node& node) {
3.240 - return (*_order)[node];
3.241 - }
3.242 -
3.243 - /// \brief Return the weight of the predecessor edge in the
3.244 - /// Gomory-Hu tree.
3.245 - ///
3.246 - /// This function returns the weight of the predecessor edge in the
3.247 - /// Gomory-Hu tree. If the node is the root, the result is undefined.
3.248 - Value predValue(const Node& node) {
3.249 - return (*_weight)[node];
3.250 - }
3.251 -
3.252 - /// \brief Return the minimum cut value between two nodes
3.253 - ///
3.254 - /// This function returns the minimum cut value between two nodes. The
3.255 - /// algorithm finds the nearest common ancestor in the Gomory-Hu
3.256 - /// tree and calculates the minimum weight arc on the paths to
3.257 - /// the ancestor.
3.258 - Value minCutValue(const Node& s, const Node& t) const {
3.259 - Node sn = s, tn = t;
3.260 - Value value = std::numeric_limits<Value>::max();
3.261 -
3.262 - while (sn != tn) {
3.263 - if ((*_order)[sn] < (*_order)[tn]) {
3.264 - if ((*_weight)[tn] <= value) value = (*_weight)[tn];
3.265 - tn = (*_pred)[tn];
3.266 - } else {
3.267 - if ((*_weight)[sn] <= value) value = (*_weight)[sn];
3.268 - sn = (*_pred)[sn];
3.269 - }
3.270 - }
3.271 - return value;
3.272 - }
3.273 -
3.274 - /// \brief Return the minimum cut between two nodes
3.275 - ///
3.276 - /// This function returns the minimum cut between the nodes \c s and \c t
3.277 - /// the \r cutMap parameter by setting the nodes in the component of
3.278 - /// \c \s to true and the other nodes to false.
3.279 - ///
3.280 - /// The \c cutMap should be \ref concepts::ReadWriteMap
3.281 - /// "ReadWriteMap".
3.282 - ///
3.283 - /// For higher level interfaces, see MinCutNodeIt and MinCutEdgeIt
3.284 - template <typename CutMap>
3.285 - Value minCutMap(const Node& s, ///< Base node
3.286 - const Node& t,
3.287 - ///< The node you want to separate from Node s.
3.288 - CutMap& cutMap
3.289 - ///< The cut will be return in this map.
3.290 - /// It must be a \c bool \ref concepts::ReadWriteMap
3.291 - /// "ReadWriteMap" on the graph nodes.
3.292 - ) const {
3.293 - Node sn = s, tn = t;
3.294 - bool s_root=false;
3.295 - Node rn = INVALID;
3.296 - Value value = std::numeric_limits<Value>::max();
3.297 -
3.298 - while (sn != tn) {
3.299 - if ((*_order)[sn] < (*_order)[tn]) {
3.300 - if ((*_weight)[tn] <= value) {
3.301 - rn = tn;
3.302 - s_root = false;
3.303 - value = (*_weight)[tn];
3.304 - }
3.305 - tn = (*_pred)[tn];
3.306 - } else {
3.307 - if ((*_weight)[sn] <= value) {
3.308 - rn = sn;
3.309 - s_root = true;
3.310 - value = (*_weight)[sn];
3.311 - }
3.312 - sn = (*_pred)[sn];
3.313 - }
3.314 - }
3.315 -
3.316 - typename Graph::template NodeMap<bool> reached(_graph, false);
3.317 - reached.set(_root, true);
3.318 - cutMap.set(_root, !s_root);
3.319 - reached.set(rn, true);
3.320 - cutMap.set(rn, s_root);
3.321 -
3.322 - std::vector<Node> st;
3.323 - for (NodeIt n(_graph); n != INVALID; ++n) {
3.324 - st.clear();
3.325 - Node nn = n;
3.326 - while (!reached[nn]) {
3.327 - st.push_back(nn);
3.328 - nn = (*_pred)[nn];
3.329 - }
3.330 - while (!st.empty()) {
3.331 - cutMap.set(st.back(), cutMap[nn]);
3.332 - st.pop_back();
3.333 - }
3.334 - }
3.335 -
3.336 - return value;
3.337 - }
3.338 -
3.339 - ///@}
3.340 -
3.341 - friend class MinCutNodeIt;
3.342 -
3.343 - /// Iterate on the nodes of a minimum cut
3.344 -
3.345 - /// This iterator class lists the nodes of a minimum cut found by
3.346 - /// GomoryHuTree. Before using it, you must allocate a GomoryHuTree class,
3.347 - /// and call its \ref GomoryHuTree::run() "run()" method.
3.348 - ///
3.349 - /// This example counts the nodes in the minimum cut separating \c s from
3.350 - /// \c t.
3.351 - /// \code
3.352 - /// GomoruHuTree<Graph> gom(g, capacities);
3.353 - /// gom.run();
3.354 - /// int sum=0;
3.355 - /// for(GomoruHuTree<Graph>::MinCutNodeIt n(gom,s,t);n!=INVALID;++n) ++sum;
3.356 - /// \endcode
3.357 - class MinCutNodeIt
3.358 - {
3.359 - bool _side;
3.360 - typename Graph::NodeIt _node_it;
3.361 - typename Graph::template NodeMap<bool> _cut;
3.362 - public:
3.363 - /// Constructor
3.364 -
3.365 - /// Constructor
3.366 - ///
3.367 - MinCutNodeIt(GomoryHuTree const &gomory,
3.368 - ///< The GomoryHuTree class. You must call its
3.369 - /// run() method
3.370 - /// before initializing this iterator
3.371 - const Node& s, ///< Base node
3.372 - const Node& t,
3.373 - ///< The node you want to separate from Node s.
3.374 - bool side=true
3.375 - ///< If it is \c true (default) then the iterator lists
3.376 - /// the nodes of the component containing \c s,
3.377 - /// otherwise it lists the other component.
3.378 - /// \note As the minimum cut is not always unique,
3.379 - /// \code
3.380 - /// MinCutNodeIt(gomory, s, t, true);
3.381 - /// \endcode
3.382 - /// and
3.383 - /// \code
3.384 - /// MinCutNodeIt(gomory, t, s, false);
3.385 - /// \endcode
3.386 - /// does not necessarily give the same set of nodes.
3.387 - /// However it is ensured that
3.388 - /// \code
3.389 - /// MinCutNodeIt(gomory, s, t, true);
3.390 - /// \endcode
3.391 - /// and
3.392 - /// \code
3.393 - /// MinCutNodeIt(gomory, s, t, false);
3.394 - /// \endcode
3.395 - /// together list each node exactly once.
3.396 - )
3.397 - : _side(side), _cut(gomory._graph)
3.398 - {
3.399 - gomory.minCutMap(s,t,_cut);
3.400 - for(_node_it=typename Graph::NodeIt(gomory._graph);
3.401 - _node_it!=INVALID && _cut[_node_it]!=_side;
3.402 - ++_node_it) {}
3.403 - }
3.404 - /// Conversion to Node
3.405 -
3.406 - /// Conversion to Node
3.407 - ///
3.408 - operator typename Graph::Node() const
3.409 - {
3.410 - return _node_it;
3.411 - }
3.412 - bool operator==(Invalid) { return _node_it==INVALID; }
3.413 - bool operator!=(Invalid) { return _node_it!=INVALID; }
3.414 - /// Next node
3.415 -
3.416 - /// Next node
3.417 - ///
3.418 - MinCutNodeIt &operator++()
3.419 - {
3.420 - for(++_node_it;_node_it!=INVALID&&_cut[_node_it]!=_side;++_node_it) {}
3.421 - return *this;
3.422 - }
3.423 - /// Postfix incrementation
3.424 -
3.425 - /// Postfix incrementation
3.426 - ///
3.427 - /// \warning This incrementation
3.428 - /// returns a \c Node, not a \ref MinCutNodeIt, as one may
3.429 - /// expect.
3.430 - typename Graph::Node operator++(int)
3.431 - {
3.432 - typename Graph::Node n=*this;
3.433 - ++(*this);
3.434 - return n;
3.435 - }
3.436 - };
3.437 -
3.438 - friend class MinCutEdgeIt;
3.439 -
3.440 - /// Iterate on the edges of a minimum cut
3.441 -
3.442 - /// This iterator class lists the edges of a minimum cut found by
3.443 - /// GomoryHuTree. Before using it, you must allocate a GomoryHuTree class,
3.444 - /// and call its \ref GomoryHuTree::run() "run()" method.
3.445 - ///
3.446 - /// This example computes the value of the minimum cut separating \c s from
3.447 - /// \c t.
3.448 - /// \code
3.449 - /// GomoruHuTree<Graph> gom(g, capacities);
3.450 - /// gom.run();
3.451 - /// int value=0;
3.452 - /// for(GomoruHuTree<Graph>::MinCutEdgeIt e(gom,s,t);e!=INVALID;++e)
3.453 - /// value+=capacities[e];
3.454 - /// \endcode
3.455 - /// the result will be the same as it is returned by
3.456 - /// \ref GomoryHuTree::minCostValue() "gom.minCostValue(s,t)"
3.457 - class MinCutEdgeIt
3.458 - {
3.459 - bool _side;
3.460 - const Graph &_graph;
3.461 - typename Graph::NodeIt _node_it;
3.462 - typename Graph::OutArcIt _arc_it;
3.463 - typename Graph::template NodeMap<bool> _cut;
3.464 - void step()
3.465 - {
3.466 - ++_arc_it;
3.467 - while(_node_it!=INVALID && _arc_it==INVALID)
3.468 - {
3.469 - for(++_node_it;_node_it!=INVALID&&!_cut[_node_it];++_node_it) {}
3.470 - if(_node_it!=INVALID)
3.471 - _arc_it=typename Graph::OutArcIt(_graph,_node_it);
3.472 - }
3.473 - }
3.474 -
3.475 - public:
3.476 - MinCutEdgeIt(GomoryHuTree const &gomory,
3.477 - ///< The GomoryHuTree class. You must call its
3.478 - /// run() method
3.479 - /// before initializing this iterator
3.480 - const Node& s, ///< Base node
3.481 - const Node& t,
3.482 - ///< The node you want to separate from Node s.
3.483 - bool side=true
3.484 - ///< If it is \c true (default) then the listed arcs
3.485 - /// will be oriented from the
3.486 - /// the nodes of the component containing \c s,
3.487 - /// otherwise they will be oriented in the opposite
3.488 - /// direction.
3.489 - )
3.490 - : _graph(gomory._graph), _cut(_graph)
3.491 - {
3.492 - gomory.minCutMap(s,t,_cut);
3.493 - if(!side)
3.494 - for(typename Graph::NodeIt n(_graph);n!=INVALID;++n)
3.495 - _cut[n]=!_cut[n];
3.496 -
3.497 - for(_node_it=typename Graph::NodeIt(_graph);
3.498 - _node_it!=INVALID && !_cut[_node_it];
3.499 - ++_node_it) {}
3.500 - _arc_it = _node_it!=INVALID ?
3.501 - typename Graph::OutArcIt(_graph,_node_it) : INVALID;
3.502 - while(_node_it!=INVALID && _arc_it == INVALID)
3.503 - {
3.504 - for(++_node_it; _node_it!=INVALID&&!_cut[_node_it]; ++_node_it) {}
3.505 - if(_node_it!=INVALID)
3.506 - _arc_it= typename Graph::OutArcIt(_graph,_node_it);
3.507 - }
3.508 - while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step();
3.509 - }
3.510 - /// Conversion to Arc
3.511 -
3.512 - /// Conversion to Arc
3.513 - ///
3.514 - operator typename Graph::Arc() const
3.515 - {
3.516 - return _arc_it;
3.517 - }
3.518 - /// Conversion to Edge
3.519 -
3.520 - /// Conversion to Edge
3.521 - ///
3.522 - operator typename Graph::Edge() const
3.523 - {
3.524 - return _arc_it;
3.525 - }
3.526 - bool operator==(Invalid) { return _node_it==INVALID; }
3.527 - bool operator!=(Invalid) { return _node_it!=INVALID; }
3.528 - /// Next edge
3.529 -
3.530 - /// Next edge
3.531 - ///
3.532 - MinCutEdgeIt &operator++()
3.533 - {
3.534 - step();
3.535 - while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step();
3.536 - return *this;
3.537 - }
3.538 - /// Postfix incrementation
3.539 -
3.540 - /// Postfix incrementation
3.541 - ///
3.542 - /// \warning This incrementation
3.543 - /// returns a \c Arc, not a \ref MinCutEdgeIt, as one may
3.544 - /// expect.
3.545 - typename Graph::Arc operator++(int)
3.546 - {
3.547 - typename Graph::Arc e=*this;
3.548 - ++(*this);
3.549 - return e;
3.550 - }
3.551 - };
3.552 -
3.553 - };
3.554 -
3.555 -}
3.556 -
3.557 -#endif
4.1 --- a/test/gomory_hu_test.cc Wed Feb 25 11:10:52 2009 +0000
4.2 +++ b/test/gomory_hu_test.cc Wed Feb 25 11:10:57 2009 +0000
4.3 @@ -3,7 +3,7 @@
4.4 #include "test_tools.h"
4.5 #include <lemon/smart_graph.h>
4.6 #include <lemon/lgf_reader.h>
4.7 -#include <lemon/gomory_hu_tree.h>
4.8 +#include <lemon/gomory_hu.h>
4.9 #include <cstdlib>
4.10
4.11 using namespace std;
4.12 @@ -60,7 +60,7 @@
4.13 GraphReader<Graph>(graph, input).
4.14 edgeMap("capacity", capacity).run();
4.15
4.16 - GomoryHuTree<Graph> ght(graph, capacity);
4.17 + GomoryHu<Graph> ght(graph, capacity);
4.18 ght.init();
4.19 ght.run();
4.20
4.21 @@ -75,14 +75,14 @@
4.22 check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 2");
4.23
4.24 int sum=0;
4.25 - for(GomoryHuTree<Graph>::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a)
4.26 + for(GomoryHu<Graph>::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a)
4.27 sum+=capacity[a];
4.28 check(sum == ght.minCutValue(u, v), "Problem with MinCutEdgeIt");
4.29
4.30 sum=0;
4.31 - for(GomoryHuTree<Graph>::MinCutNodeIt n(ght, u, v,true);n!=INVALID;++n)
4.32 + for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,true);n!=INVALID;++n)
4.33 sum++;
4.34 - for(GomoryHuTree<Graph>::MinCutNodeIt n(ght, u, v,false);n!=INVALID;++n)
4.35 + for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,false);n!=INVALID;++n)
4.36 sum++;
4.37 check(sum == countNodes(graph), "Problem with MinCutNodeIt");
4.38