1.1 --- a/lemon/Makefile.am Wed Nov 28 18:01:38 2007 +0000
1.2 +++ b/lemon/Makefile.am Wed Nov 28 18:05:49 2007 +0000
1.3 @@ -74,6 +74,7 @@
1.4 lemon/graph_writer.h \
1.5 lemon/grid_ugraph.h \
1.6 lemon/goldberg_tarjan.h \
1.7 + lemon/gomory_hu_tree.h \
1.8 lemon/hao_orlin.h \
1.9 lemon/hypercube_graph.h \
1.10 lemon/iterable_maps.h \
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/lemon/gomory_hu_tree.h Wed Nov 28 18:05:49 2007 +0000
2.3 @@ -0,0 +1,296 @@
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-2007
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 <lemon/preflow.h>
2.26 +#include <lemon/concept_check.h>
2.27 +#include <lemon/concepts/maps.h>
2.28 +
2.29 +/// \ingroup min_cut
2.30 +/// \file
2.31 +/// \brief Gomory-Hu cut tree in undirected graphs.
2.32 +
2.33 +namespace lemon {
2.34 +
2.35 + /// \ingroup min_cut
2.36 + ///
2.37 + /// \brief Gomory-Hu cut tree algorithm
2.38 + ///
2.39 + /// The Gomory-Hu tree is a tree on the nodeset of the graph, but it
2.40 + /// may contain edges which are not in the original graph. It helps
2.41 + /// to calculate the minimum cut between all pairs of nodes, because
2.42 + /// the minimum capacity edge on the tree path between two nodes has
2.43 + /// the same weight as the minimum cut in the graph between these
2.44 + /// nodes. Moreover this edge separates the nodes to two parts which
2.45 + /// determine this minimum cut.
2.46 + ///
2.47 + /// The algorithm calculates \e n-1 distinict minimum cuts with
2.48 + /// preflow algorithm, therefore the algorithm has
2.49 + /// \f$(O(n^3\sqrt{e})\f$ overall time complexity. It calculates a
2.50 + /// rooted Gomory-Hu tree, the structure of the tree and the weights
2.51 + /// can be obtained with \c predNode() and \c predValue()
2.52 + /// functions. The \c minCutValue() and \c minCutMap() calculates
2.53 + /// the minimum cut and the minimum cut value between any two node
2.54 + /// in the graph.
2.55 + template <typename _UGraph,
2.56 + typename _Capacity = typename _UGraph::template UEdgeMap<int> >
2.57 + class GomoryHuTree {
2.58 + public:
2.59 +
2.60 + /// The undirected graph type
2.61 + typedef _UGraph UGraph;
2.62 + /// The capacity on undirected edges
2.63 + typedef _Capacity Capacity;
2.64 + /// The value type of capacities
2.65 + typedef typename Capacity::Value Value;
2.66 +
2.67 + private:
2.68 +
2.69 + UGRAPH_TYPEDEFS(typename UGraph);
2.70 +
2.71 + const UGraph& _ugraph;
2.72 + const Capacity& _capacity;
2.73 +
2.74 + Node _root;
2.75 + typename UGraph::template NodeMap<Node>* _pred;
2.76 + typename UGraph::template NodeMap<Value>* _weight;
2.77 + typename UGraph::template NodeMap<int>* _order;
2.78 +
2.79 + void createStructures() {
2.80 + if (!_pred) {
2.81 + _pred = new typename UGraph::template NodeMap<Node>(_ugraph);
2.82 + }
2.83 + if (!_weight) {
2.84 + _weight = new typename UGraph::template NodeMap<Value>(_ugraph);
2.85 + }
2.86 + if (!_order) {
2.87 + _order = new typename UGraph::template NodeMap<int>(_ugraph);
2.88 + }
2.89 + }
2.90 +
2.91 + void destroyStructures() {
2.92 + if (_pred) {
2.93 + delete _pred;
2.94 + }
2.95 + if (_weight) {
2.96 + delete _weight;
2.97 + }
2.98 + if (_order) {
2.99 + delete _order;
2.100 + }
2.101 + }
2.102 +
2.103 + public:
2.104 +
2.105 + /// \brief Constructor
2.106 + ///
2.107 + /// Constructor
2.108 + /// \param ugraph The undirected graph type.
2.109 + /// \param capacity The capacity map.
2.110 + GomoryHuTree(const UGraph& ugraph, const Capacity& capacity)
2.111 + : _ugraph(ugraph), _capacity(capacity),
2.112 + _pred(0), _weight(0), _order(0)
2.113 + {
2.114 + checkConcept<concepts::ReadMap<UEdge, Value>, Capacity>();
2.115 + }
2.116 +
2.117 +
2.118 + /// \brief Destructor
2.119 + ///
2.120 + /// Destructor
2.121 + ~GomoryHuTree() {
2.122 + destroyStructures();
2.123 + }
2.124 +
2.125 + /// \brief Initializes the internal data structures.
2.126 + ///
2.127 + /// Initializes the internal data structures.
2.128 + ///
2.129 + void init() {
2.130 + createStructures();
2.131 +
2.132 + _root = NodeIt(_ugraph);
2.133 + for (NodeIt n(_ugraph); n != INVALID; ++n) {
2.134 + _pred->set(n, _root);
2.135 + _order->set(n, -1);
2.136 + }
2.137 + _pred->set(_root, INVALID);
2.138 + _weight->set(_root, std::numeric_limits<Value>::max());
2.139 + }
2.140 +
2.141 +
2.142 + /// \brief Starts the algorithm
2.143 + ///
2.144 + /// Starts the algorithm.
2.145 + void start() {
2.146 + Preflow<UGraph, Capacity> fa(_ugraph, _capacity, _root, INVALID);
2.147 +
2.148 + for (NodeIt n(_ugraph); n != INVALID; ++n) {
2.149 + if (n == _root) continue;
2.150 +
2.151 + Node pn = (*_pred)[n];
2.152 + fa.source(n);
2.153 + fa.target(pn);
2.154 +
2.155 + fa.runMinCut();
2.156 +
2.157 + _weight->set(n, fa.flowValue());
2.158 +
2.159 + for (NodeIt nn(_ugraph); nn != INVALID; ++nn) {
2.160 + if (nn != n && fa.minCut(nn) && (*_pred)[nn] == pn) {
2.161 + _pred->set(nn, n);
2.162 + }
2.163 + }
2.164 + if ((*_pred)[pn] != INVALID && fa.minCut((*_pred)[pn])) {
2.165 + _pred->set(n, (*_pred)[pn]);
2.166 + _pred->set(pn, n);
2.167 + _weight->set(n, (*_weight)[pn]);
2.168 + _weight->set(pn, fa.flowValue());
2.169 + }
2.170 + }
2.171 +
2.172 + _order->set(_root, 0);
2.173 + int index = 1;
2.174 +
2.175 + for (NodeIt n(_ugraph); n != INVALID; ++n) {
2.176 + std::vector<Node> st;
2.177 + Node nn = n;
2.178 + while ((*_order)[nn] == -1) {
2.179 + st.push_back(nn);
2.180 + nn = (*_pred)[nn];
2.181 + }
2.182 + while (!st.empty()) {
2.183 + _order->set(st.back(), index++);
2.184 + st.pop_back();
2.185 + }
2.186 + }
2.187 + }
2.188 +
2.189 + /// \brief Runs the Gomory-Hu algorithm.
2.190 + ///
2.191 + /// Runs the Gomory-Hu algorithm.
2.192 + /// \note gh.run() is just a shortcut of the following code.
2.193 + /// \code
2.194 + /// ght.init();
2.195 + /// ght.start();
2.196 + /// \endcode
2.197 + void run() {
2.198 + init();
2.199 + start();
2.200 + }
2.201 +
2.202 + /// \brief Returns the predecessor node in the Gomory-Hu tree.
2.203 + ///
2.204 + /// Returns the predecessor node in the Gomory-Hu tree. If the node is
2.205 + /// the root of the Gomory-Hu tree, then it returns \c INVALID.
2.206 + Node predNode(const Node& node) {
2.207 + return (*_pred)[node];
2.208 + }
2.209 +
2.210 + /// \brief Returns the weight of the predecessor edge in the
2.211 + /// Gomory-Hu tree.
2.212 + ///
2.213 + /// Returns the weight of the predecessor edge in the Gomory-Hu
2.214 + /// tree. If the node is the root of the Gomory-Hu tree, the
2.215 + /// result is undefined.
2.216 + Value predValue(const Node& node) {
2.217 + return (*_weight)[node];
2.218 + }
2.219 +
2.220 + /// \brief Returns the minimum cut value between two nodes
2.221 + ///
2.222 + /// Returns the minimum cut value between two nodes. The
2.223 + /// algorithm finds the nearest common ancestor in the Gomory-Hu
2.224 + /// tree and calculates the minimum weight edge on the paths to
2.225 + /// the ancestor.
2.226 + Value minCutValue(const Node& s, const Node& t) const {
2.227 + Node sn = s, tn = t;
2.228 + Value value = std::numeric_limits<Value>::max();
2.229 +
2.230 + while (sn != tn) {
2.231 + if ((*_order)[sn] < (*_order)[tn]) {
2.232 + if ((*_weight)[tn] < value) value = (*_weight)[tn];
2.233 + tn = (*_pred)[tn];
2.234 + } else {
2.235 + if ((*_weight)[sn] < value) value = (*_weight)[sn];
2.236 + sn = (*_pred)[sn];
2.237 + }
2.238 + }
2.239 + return value;
2.240 + }
2.241 +
2.242 + /// \brief Returns the minimum cut between two nodes
2.243 + ///
2.244 + /// Returns the minimum cut value between two nodes. The
2.245 + /// algorithm finds the nearest common ancestor in the Gomory-Hu
2.246 + /// tree and calculates the minimum weight edge on the paths to
2.247 + /// the ancestor. Then it sets all nodes to the cut determined by
2.248 + /// this edge. The \c cutMap should be \ref concepts::ReadWriteMap
2.249 + /// "ReadWriteMap".
2.250 + template <typename CutMap>
2.251 + Value minCutMap(const Node& s, const Node& t, CutMap& cutMap) const {
2.252 + Node sn = s, tn = t;
2.253 +
2.254 + Node rn = INVALID;
2.255 + Value value = std::numeric_limits<Value>::max();
2.256 +
2.257 + while (sn != tn) {
2.258 + if ((*_order)[sn] < (*_order)[tn]) {
2.259 + if ((*_weight)[tn] < value) {
2.260 + rn = tn;
2.261 + value = (*_weight)[tn];
2.262 + }
2.263 + tn = (*_pred)[tn];
2.264 + } else {
2.265 + if ((*_weight)[sn] < value) {
2.266 + rn = sn;
2.267 + value = (*_weight)[sn];
2.268 + }
2.269 + sn = (*_pred)[sn];
2.270 + }
2.271 + }
2.272 +
2.273 + typename UGraph::template NodeMap<bool> reached(_ugraph, false);
2.274 + reached.set(_root, true);
2.275 + cutMap.set(_root, false);
2.276 + reached.set(rn, true);
2.277 + cutMap.set(rn, true);
2.278 +
2.279 + for (NodeIt n(_ugraph); n != INVALID; ++n) {
2.280 + std::vector<Node> st;
2.281 + Node nn = n;
2.282 + while (!reached[nn]) {
2.283 + st.push_back(nn);
2.284 + nn = (*_pred)[nn];
2.285 + }
2.286 + while (!st.empty()) {
2.287 + cutMap.set(st.back(), cutMap[nn]);
2.288 + st.pop_back();
2.289 + }
2.290 + }
2.291 +
2.292 + return value;
2.293 + }
2.294 +
2.295 + };
2.296 +
2.297 +}
2.298 +
2.299 +#endif