deba@2528: /* -*- C++ -*-
deba@2528: *
deba@2528: * This file is a part of LEMON, a generic C++ optimization library
deba@2528: *
alpar@2553: * Copyright (C) 2003-2008
deba@2528: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@2528: * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@2528: *
deba@2528: * Permission to use, modify and distribute this software is granted
deba@2528: * provided that this copyright notice appears in all copies. For
deba@2528: * precise terms see the accompanying LICENSE file.
deba@2528: *
deba@2528: * This software is provided "AS IS" with no warranty of any kind,
deba@2528: * express or implied, and with no claim as to its suitability for any
deba@2528: * purpose.
deba@2528: *
deba@2528: */
deba@2528:
deba@2528: #ifndef LEMON_GOMORY_HU_TREE_H
deba@2528: #define LEMON_GOMORY_HU_TREE_H
deba@2528:
deba@2528: #include <lemon/preflow.h>
deba@2528: #include <lemon/concept_check.h>
deba@2528: #include <lemon/concepts/maps.h>
deba@2528:
deba@2528: /// \ingroup min_cut
deba@2528: /// \file
deba@2528: /// \brief Gomory-Hu cut tree in undirected graphs.
deba@2528:
deba@2528: namespace lemon {
deba@2528:
deba@2528: /// \ingroup min_cut
deba@2528: ///
deba@2528: /// \brief Gomory-Hu cut tree algorithm
deba@2528: ///
deba@2528: /// The Gomory-Hu tree is a tree on the nodeset of the graph, but it
deba@2528: /// may contain edges which are not in the original graph. It helps
deba@2528: /// to calculate the minimum cut between all pairs of nodes, because
deba@2528: /// the minimum capacity edge on the tree path between two nodes has
deba@2528: /// the same weight as the minimum cut in the graph between these
deba@2528: /// nodes. Moreover this edge separates the nodes to two parts which
deba@2528: /// determine this minimum cut.
deba@2528: ///
deba@2528: /// The algorithm calculates \e n-1 distinict minimum cuts with
deba@2528: /// preflow algorithm, therefore the algorithm has
deba@2528: /// \f$(O(n^3\sqrt{e})\f$ overall time complexity. It calculates a
deba@2528: /// rooted Gomory-Hu tree, the structure of the tree and the weights
deba@2528: /// can be obtained with \c predNode() and \c predValue()
deba@2528: /// functions. The \c minCutValue() and \c minCutMap() calculates
deba@2528: /// the minimum cut and the minimum cut value between any two node
deba@2528: /// in the graph.
deba@2528: template <typename _UGraph,
deba@2528: typename _Capacity = typename _UGraph::template UEdgeMap<int> >
deba@2528: class GomoryHuTree {
deba@2528: public:
deba@2528:
deba@2528: /// The undirected graph type
deba@2528: typedef _UGraph UGraph;
deba@2528: /// The capacity on undirected edges
deba@2528: typedef _Capacity Capacity;
deba@2528: /// The value type of capacities
deba@2528: typedef typename Capacity::Value Value;
deba@2528:
deba@2528: private:
deba@2528:
deba@2528: UGRAPH_TYPEDEFS(typename UGraph);
deba@2528:
deba@2528: const UGraph& _ugraph;
deba@2528: const Capacity& _capacity;
deba@2528:
deba@2528: Node _root;
deba@2528: typename UGraph::template NodeMap<Node>* _pred;
deba@2528: typename UGraph::template NodeMap<Value>* _weight;
deba@2528: typename UGraph::template NodeMap<int>* _order;
deba@2528:
deba@2528: void createStructures() {
deba@2528: if (!_pred) {
deba@2528: _pred = new typename UGraph::template NodeMap<Node>(_ugraph);
deba@2528: }
deba@2528: if (!_weight) {
deba@2528: _weight = new typename UGraph::template NodeMap<Value>(_ugraph);
deba@2528: }
deba@2528: if (!_order) {
deba@2528: _order = new typename UGraph::template NodeMap<int>(_ugraph);
deba@2528: }
deba@2528: }
deba@2528:
deba@2528: void destroyStructures() {
deba@2528: if (_pred) {
deba@2528: delete _pred;
deba@2528: }
deba@2528: if (_weight) {
deba@2528: delete _weight;
deba@2528: }
deba@2528: if (_order) {
deba@2528: delete _order;
deba@2528: }
deba@2528: }
deba@2528:
deba@2528: public:
deba@2528:
deba@2528: /// \brief Constructor
deba@2528: ///
deba@2528: /// Constructor
deba@2528: /// \param ugraph The undirected graph type.
deba@2528: /// \param capacity The capacity map.
deba@2528: GomoryHuTree(const UGraph& ugraph, const Capacity& capacity)
deba@2528: : _ugraph(ugraph), _capacity(capacity),
deba@2528: _pred(0), _weight(0), _order(0)
deba@2528: {
deba@2528: checkConcept<concepts::ReadMap<UEdge, Value>, Capacity>();
deba@2528: }
deba@2528:
deba@2528:
deba@2528: /// \brief Destructor
deba@2528: ///
deba@2528: /// Destructor
deba@2528: ~GomoryHuTree() {
deba@2528: destroyStructures();
deba@2528: }
deba@2528:
deba@2528: /// \brief Initializes the internal data structures.
deba@2528: ///
deba@2528: /// Initializes the internal data structures.
deba@2528: ///
deba@2528: void init() {
deba@2528: createStructures();
deba@2528:
deba@2528: _root = NodeIt(_ugraph);
deba@2528: for (NodeIt n(_ugraph); n != INVALID; ++n) {
deba@2528: _pred->set(n, _root);
deba@2528: _order->set(n, -1);
deba@2528: }
deba@2528: _pred->set(_root, INVALID);
deba@2528: _weight->set(_root, std::numeric_limits<Value>::max());
deba@2528: }
deba@2528:
deba@2528:
deba@2528: /// \brief Starts the algorithm
deba@2528: ///
deba@2528: /// Starts the algorithm.
deba@2528: void start() {
deba@2528: Preflow<UGraph, Capacity> fa(_ugraph, _capacity, _root, INVALID);
deba@2528:
deba@2528: for (NodeIt n(_ugraph); n != INVALID; ++n) {
deba@2528: if (n == _root) continue;
deba@2528:
deba@2528: Node pn = (*_pred)[n];
deba@2528: fa.source(n);
deba@2528: fa.target(pn);
deba@2528:
deba@2528: fa.runMinCut();
deba@2528:
deba@2528: _weight->set(n, fa.flowValue());
deba@2528:
deba@2528: for (NodeIt nn(_ugraph); nn != INVALID; ++nn) {
deba@2528: if (nn != n && fa.minCut(nn) && (*_pred)[nn] == pn) {
deba@2528: _pred->set(nn, n);
deba@2528: }
deba@2528: }
deba@2528: if ((*_pred)[pn] != INVALID && fa.minCut((*_pred)[pn])) {
deba@2528: _pred->set(n, (*_pred)[pn]);
deba@2528: _pred->set(pn, n);
deba@2528: _weight->set(n, (*_weight)[pn]);
deba@2528: _weight->set(pn, fa.flowValue());
deba@2528: }
deba@2528: }
deba@2528:
deba@2528: _order->set(_root, 0);
deba@2528: int index = 1;
deba@2528:
deba@2528: for (NodeIt n(_ugraph); n != INVALID; ++n) {
deba@2528: std::vector<Node> st;
deba@2528: Node nn = n;
deba@2528: while ((*_order)[nn] == -1) {
deba@2528: st.push_back(nn);
deba@2528: nn = (*_pred)[nn];
deba@2528: }
deba@2528: while (!st.empty()) {
deba@2528: _order->set(st.back(), index++);
deba@2528: st.pop_back();
deba@2528: }
deba@2528: }
deba@2528: }
deba@2528:
deba@2528: /// \brief Runs the Gomory-Hu algorithm.
deba@2528: ///
deba@2528: /// Runs the Gomory-Hu algorithm.
deba@2528: /// \note gh.run() is just a shortcut of the following code.
deba@2528: /// \code
deba@2528: /// ght.init();
deba@2528: /// ght.start();
deba@2528: /// \endcode
deba@2528: void run() {
deba@2528: init();
deba@2528: start();
deba@2528: }
deba@2528:
deba@2528: /// \brief Returns the predecessor node in the Gomory-Hu tree.
deba@2528: ///
deba@2528: /// Returns the predecessor node in the Gomory-Hu tree. If the node is
deba@2528: /// the root of the Gomory-Hu tree, then it returns \c INVALID.
deba@2528: Node predNode(const Node& node) {
deba@2528: return (*_pred)[node];
deba@2528: }
deba@2528:
deba@2528: /// \brief Returns the weight of the predecessor edge in the
deba@2528: /// Gomory-Hu tree.
deba@2528: ///
deba@2528: /// Returns the weight of the predecessor edge in the Gomory-Hu
deba@2528: /// tree. If the node is the root of the Gomory-Hu tree, the
deba@2528: /// result is undefined.
deba@2528: Value predValue(const Node& node) {
deba@2528: return (*_weight)[node];
deba@2528: }
deba@2528:
deba@2528: /// \brief Returns the minimum cut value between two nodes
deba@2528: ///
deba@2528: /// Returns the minimum cut value between two nodes. The
deba@2528: /// algorithm finds the nearest common ancestor in the Gomory-Hu
deba@2528: /// tree and calculates the minimum weight edge on the paths to
deba@2528: /// the ancestor.
deba@2528: Value minCutValue(const Node& s, const Node& t) const {
deba@2528: Node sn = s, tn = t;
deba@2528: Value value = std::numeric_limits<Value>::max();
deba@2528:
deba@2528: while (sn != tn) {
deba@2528: if ((*_order)[sn] < (*_order)[tn]) {
deba@2528: if ((*_weight)[tn] < value) value = (*_weight)[tn];
deba@2528: tn = (*_pred)[tn];
deba@2528: } else {
deba@2528: if ((*_weight)[sn] < value) value = (*_weight)[sn];
deba@2528: sn = (*_pred)[sn];
deba@2528: }
deba@2528: }
deba@2528: return value;
deba@2528: }
deba@2528:
deba@2528: /// \brief Returns the minimum cut between two nodes
deba@2528: ///
deba@2528: /// Returns the minimum cut value between two nodes. The
deba@2528: /// algorithm finds the nearest common ancestor in the Gomory-Hu
deba@2528: /// tree and calculates the minimum weight edge on the paths to
deba@2528: /// the ancestor. Then it sets all nodes to the cut determined by
deba@2528: /// this edge. The \c cutMap should be \ref concepts::ReadWriteMap
deba@2528: /// "ReadWriteMap".
deba@2528: template <typename CutMap>
deba@2528: Value minCutMap(const Node& s, const Node& t, CutMap& cutMap) const {
deba@2528: Node sn = s, tn = t;
deba@2528:
deba@2528: Node rn = INVALID;
deba@2528: Value value = std::numeric_limits<Value>::max();
deba@2528:
deba@2528: while (sn != tn) {
deba@2528: if ((*_order)[sn] < (*_order)[tn]) {
deba@2528: if ((*_weight)[tn] < value) {
deba@2528: rn = tn;
deba@2528: value = (*_weight)[tn];
deba@2528: }
deba@2528: tn = (*_pred)[tn];
deba@2528: } else {
deba@2528: if ((*_weight)[sn] < value) {
deba@2528: rn = sn;
deba@2528: value = (*_weight)[sn];
deba@2528: }
deba@2528: sn = (*_pred)[sn];
deba@2528: }
deba@2528: }
deba@2528:
deba@2528: typename UGraph::template NodeMap<bool> reached(_ugraph, false);
deba@2528: reached.set(_root, true);
deba@2528: cutMap.set(_root, false);
deba@2528: reached.set(rn, true);
deba@2528: cutMap.set(rn, true);
deba@2528:
deba@2528: for (NodeIt n(_ugraph); n != INVALID; ++n) {
deba@2528: std::vector<Node> st;
deba@2528: Node nn = n;
deba@2528: while (!reached[nn]) {
deba@2528: st.push_back(nn);
deba@2528: nn = (*_pred)[nn];
deba@2528: }
deba@2528: while (!st.empty()) {
deba@2528: cutMap.set(st.back(), cutMap[nn]);
deba@2528: st.pop_back();
deba@2528: }
deba@2528: }
deba@2528:
deba@2528: return value;
deba@2528: }
deba@2528:
deba@2528: };
deba@2528:
deba@2528: }
deba@2528:
deba@2528: #endif