1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/gomory_hu_tree.h Wed Nov 28 18:05:49 2007 +0000
1.3 @@ -0,0 +1,296 @@
1.4 +/* -*- C++ -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library
1.7 + *
1.8 + * Copyright (C) 2003-2007
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +#ifndef LEMON_GOMORY_HU_TREE_H
1.23 +#define LEMON_GOMORY_HU_TREE_H
1.24 +
1.25 +#include <lemon/preflow.h>
1.26 +#include <lemon/concept_check.h>
1.27 +#include <lemon/concepts/maps.h>
1.28 +
1.29 +/// \ingroup min_cut
1.30 +/// \file
1.31 +/// \brief Gomory-Hu cut tree in undirected graphs.
1.32 +
1.33 +namespace lemon {
1.34 +
1.35 + /// \ingroup min_cut
1.36 + ///
1.37 + /// \brief Gomory-Hu cut tree algorithm
1.38 + ///
1.39 + /// The Gomory-Hu tree is a tree on the nodeset of the graph, but it
1.40 + /// may contain edges which are not in the original graph. It helps
1.41 + /// to calculate the minimum cut between all pairs of nodes, because
1.42 + /// the minimum capacity edge on the tree path between two nodes has
1.43 + /// the same weight as the minimum cut in the graph between these
1.44 + /// nodes. Moreover this edge separates the nodes to two parts which
1.45 + /// determine this minimum cut.
1.46 + ///
1.47 + /// The algorithm calculates \e n-1 distinict minimum cuts with
1.48 + /// preflow algorithm, therefore the algorithm has
1.49 + /// \f$(O(n^3\sqrt{e})\f$ overall time complexity. It calculates a
1.50 + /// rooted Gomory-Hu tree, the structure of the tree and the weights
1.51 + /// can be obtained with \c predNode() and \c predValue()
1.52 + /// functions. The \c minCutValue() and \c minCutMap() calculates
1.53 + /// the minimum cut and the minimum cut value between any two node
1.54 + /// in the graph.
1.55 + template <typename _UGraph,
1.56 + typename _Capacity = typename _UGraph::template UEdgeMap<int> >
1.57 + class GomoryHuTree {
1.58 + public:
1.59 +
1.60 + /// The undirected graph type
1.61 + typedef _UGraph UGraph;
1.62 + /// The capacity on undirected edges
1.63 + typedef _Capacity Capacity;
1.64 + /// The value type of capacities
1.65 + typedef typename Capacity::Value Value;
1.66 +
1.67 + private:
1.68 +
1.69 + UGRAPH_TYPEDEFS(typename UGraph);
1.70 +
1.71 + const UGraph& _ugraph;
1.72 + const Capacity& _capacity;
1.73 +
1.74 + Node _root;
1.75 + typename UGraph::template NodeMap<Node>* _pred;
1.76 + typename UGraph::template NodeMap<Value>* _weight;
1.77 + typename UGraph::template NodeMap<int>* _order;
1.78 +
1.79 + void createStructures() {
1.80 + if (!_pred) {
1.81 + _pred = new typename UGraph::template NodeMap<Node>(_ugraph);
1.82 + }
1.83 + if (!_weight) {
1.84 + _weight = new typename UGraph::template NodeMap<Value>(_ugraph);
1.85 + }
1.86 + if (!_order) {
1.87 + _order = new typename UGraph::template NodeMap<int>(_ugraph);
1.88 + }
1.89 + }
1.90 +
1.91 + void destroyStructures() {
1.92 + if (_pred) {
1.93 + delete _pred;
1.94 + }
1.95 + if (_weight) {
1.96 + delete _weight;
1.97 + }
1.98 + if (_order) {
1.99 + delete _order;
1.100 + }
1.101 + }
1.102 +
1.103 + public:
1.104 +
1.105 + /// \brief Constructor
1.106 + ///
1.107 + /// Constructor
1.108 + /// \param ugraph The undirected graph type.
1.109 + /// \param capacity The capacity map.
1.110 + GomoryHuTree(const UGraph& ugraph, const Capacity& capacity)
1.111 + : _ugraph(ugraph), _capacity(capacity),
1.112 + _pred(0), _weight(0), _order(0)
1.113 + {
1.114 + checkConcept<concepts::ReadMap<UEdge, Value>, Capacity>();
1.115 + }
1.116 +
1.117 +
1.118 + /// \brief Destructor
1.119 + ///
1.120 + /// Destructor
1.121 + ~GomoryHuTree() {
1.122 + destroyStructures();
1.123 + }
1.124 +
1.125 + /// \brief Initializes the internal data structures.
1.126 + ///
1.127 + /// Initializes the internal data structures.
1.128 + ///
1.129 + void init() {
1.130 + createStructures();
1.131 +
1.132 + _root = NodeIt(_ugraph);
1.133 + for (NodeIt n(_ugraph); n != INVALID; ++n) {
1.134 + _pred->set(n, _root);
1.135 + _order->set(n, -1);
1.136 + }
1.137 + _pred->set(_root, INVALID);
1.138 + _weight->set(_root, std::numeric_limits<Value>::max());
1.139 + }
1.140 +
1.141 +
1.142 + /// \brief Starts the algorithm
1.143 + ///
1.144 + /// Starts the algorithm.
1.145 + void start() {
1.146 + Preflow<UGraph, Capacity> fa(_ugraph, _capacity, _root, INVALID);
1.147 +
1.148 + for (NodeIt n(_ugraph); n != INVALID; ++n) {
1.149 + if (n == _root) continue;
1.150 +
1.151 + Node pn = (*_pred)[n];
1.152 + fa.source(n);
1.153 + fa.target(pn);
1.154 +
1.155 + fa.runMinCut();
1.156 +
1.157 + _weight->set(n, fa.flowValue());
1.158 +
1.159 + for (NodeIt nn(_ugraph); nn != INVALID; ++nn) {
1.160 + if (nn != n && fa.minCut(nn) && (*_pred)[nn] == pn) {
1.161 + _pred->set(nn, n);
1.162 + }
1.163 + }
1.164 + if ((*_pred)[pn] != INVALID && fa.minCut((*_pred)[pn])) {
1.165 + _pred->set(n, (*_pred)[pn]);
1.166 + _pred->set(pn, n);
1.167 + _weight->set(n, (*_weight)[pn]);
1.168 + _weight->set(pn, fa.flowValue());
1.169 + }
1.170 + }
1.171 +
1.172 + _order->set(_root, 0);
1.173 + int index = 1;
1.174 +
1.175 + for (NodeIt n(_ugraph); n != INVALID; ++n) {
1.176 + std::vector<Node> st;
1.177 + Node nn = n;
1.178 + while ((*_order)[nn] == -1) {
1.179 + st.push_back(nn);
1.180 + nn = (*_pred)[nn];
1.181 + }
1.182 + while (!st.empty()) {
1.183 + _order->set(st.back(), index++);
1.184 + st.pop_back();
1.185 + }
1.186 + }
1.187 + }
1.188 +
1.189 + /// \brief Runs the Gomory-Hu algorithm.
1.190 + ///
1.191 + /// Runs the Gomory-Hu algorithm.
1.192 + /// \note gh.run() is just a shortcut of the following code.
1.193 + /// \code
1.194 + /// ght.init();
1.195 + /// ght.start();
1.196 + /// \endcode
1.197 + void run() {
1.198 + init();
1.199 + start();
1.200 + }
1.201 +
1.202 + /// \brief Returns the predecessor node in the Gomory-Hu tree.
1.203 + ///
1.204 + /// Returns the predecessor node in the Gomory-Hu tree. If the node is
1.205 + /// the root of the Gomory-Hu tree, then it returns \c INVALID.
1.206 + Node predNode(const Node& node) {
1.207 + return (*_pred)[node];
1.208 + }
1.209 +
1.210 + /// \brief Returns the weight of the predecessor edge in the
1.211 + /// Gomory-Hu tree.
1.212 + ///
1.213 + /// Returns the weight of the predecessor edge in the Gomory-Hu
1.214 + /// tree. If the node is the root of the Gomory-Hu tree, the
1.215 + /// result is undefined.
1.216 + Value predValue(const Node& node) {
1.217 + return (*_weight)[node];
1.218 + }
1.219 +
1.220 + /// \brief Returns the minimum cut value between two nodes
1.221 + ///
1.222 + /// Returns the minimum cut value between two nodes. The
1.223 + /// algorithm finds the nearest common ancestor in the Gomory-Hu
1.224 + /// tree and calculates the minimum weight edge on the paths to
1.225 + /// the ancestor.
1.226 + Value minCutValue(const Node& s, const Node& t) const {
1.227 + Node sn = s, tn = t;
1.228 + Value value = std::numeric_limits<Value>::max();
1.229 +
1.230 + while (sn != tn) {
1.231 + if ((*_order)[sn] < (*_order)[tn]) {
1.232 + if ((*_weight)[tn] < value) value = (*_weight)[tn];
1.233 + tn = (*_pred)[tn];
1.234 + } else {
1.235 + if ((*_weight)[sn] < value) value = (*_weight)[sn];
1.236 + sn = (*_pred)[sn];
1.237 + }
1.238 + }
1.239 + return value;
1.240 + }
1.241 +
1.242 + /// \brief Returns the minimum cut between two nodes
1.243 + ///
1.244 + /// Returns the minimum cut value between two nodes. The
1.245 + /// algorithm finds the nearest common ancestor in the Gomory-Hu
1.246 + /// tree and calculates the minimum weight edge on the paths to
1.247 + /// the ancestor. Then it sets all nodes to the cut determined by
1.248 + /// this edge. The \c cutMap should be \ref concepts::ReadWriteMap
1.249 + /// "ReadWriteMap".
1.250 + template <typename CutMap>
1.251 + Value minCutMap(const Node& s, const Node& t, CutMap& cutMap) const {
1.252 + Node sn = s, tn = t;
1.253 +
1.254 + Node rn = INVALID;
1.255 + Value value = std::numeric_limits<Value>::max();
1.256 +
1.257 + while (sn != tn) {
1.258 + if ((*_order)[sn] < (*_order)[tn]) {
1.259 + if ((*_weight)[tn] < value) {
1.260 + rn = tn;
1.261 + value = (*_weight)[tn];
1.262 + }
1.263 + tn = (*_pred)[tn];
1.264 + } else {
1.265 + if ((*_weight)[sn] < value) {
1.266 + rn = sn;
1.267 + value = (*_weight)[sn];
1.268 + }
1.269 + sn = (*_pred)[sn];
1.270 + }
1.271 + }
1.272 +
1.273 + typename UGraph::template NodeMap<bool> reached(_ugraph, false);
1.274 + reached.set(_root, true);
1.275 + cutMap.set(_root, false);
1.276 + reached.set(rn, true);
1.277 + cutMap.set(rn, true);
1.278 +
1.279 + for (NodeIt n(_ugraph); n != INVALID; ++n) {
1.280 + std::vector<Node> st;
1.281 + Node nn = n;
1.282 + while (!reached[nn]) {
1.283 + st.push_back(nn);
1.284 + nn = (*_pred)[nn];
1.285 + }
1.286 + while (!st.empty()) {
1.287 + cutMap.set(st.back(), cutMap[nn]);
1.288 + st.pop_back();
1.289 + }
1.290 + }
1.291 +
1.292 + return value;
1.293 + }
1.294 +
1.295 + };
1.296 +
1.297 +}
1.298 +
1.299 +#endif