lemon-0.x: lemon/gomory_hu_tree.h@d239741cfd44

     1 /* -*- C++ -*-

     2  *

     3  * This file is a part of LEMON, a generic C++ optimization library

     4  *

     5  * Copyright (C) 2003-2008

     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).

     8  *

     9  * Permission to use, modify and distribute this software is granted

    10  * provided that this copyright notice appears in all copies. For

    11  * precise terms see the accompanying LICENSE file.

    12  *

    13  * This software is provided "AS IS" with no warranty of any kind,

    14  * express or implied, and with no claim as to its suitability for any

    15  * purpose.

    16  *

    17  */

    19 #ifndef LEMON_GOMORY_HU_TREE_H

    20 #define LEMON_GOMORY_HU_TREE_H

    22 #include <lemon/preflow.h>

    23 #include <lemon/concept_check.h>

    24 #include <lemon/concepts/maps.h>

    26 /// \ingroup min_cut

    27 /// \file

    28 /// \brief Gomory-Hu cut tree in undirected graphs.

    30 namespace lemon {

    32   /// \ingroup min_cut

    33   ///

    34   /// \brief Gomory-Hu cut tree algorithm

    35   ///

    36   /// The Gomory-Hu tree is a tree on the nodeset of the graph, but it

    37   /// may contain edges which are not in the original graph. It helps

    38   /// to calculate the minimum cut between all pairs of nodes, because

    39   /// the minimum capacity edge on the tree path between two nodes has

    40   /// the same weight as the minimum cut in the graph between these

    41   /// nodes. Moreover this edge separates the nodes to two parts which

    42   /// determine this minimum cut.

    43   ///

    44   /// The algorithm calculates \e n-1 distinict minimum cuts with

    45   /// preflow algorithm, therefore the algorithm has

    46   /// \f$(O(n^3\sqrt{e})\f$ overall time complexity. It calculates a

    47   /// rooted Gomory-Hu tree, the structure of the tree and the weights

    48   /// can be obtained with \c predNode() and \c predValue()

    49   /// functions. The \c minCutValue() and \c minCutMap() calculates

    50   /// the minimum cut and the minimum cut value between any two node

    51   /// in the graph.

    52   template <typename _UGraph,

    53 	    typename _Capacity = typename _UGraph::template UEdgeMap<int> >

    54   class GomoryHuTree {

    55   public:

    57     /// The undirected graph type

    58     typedef _UGraph UGraph;

    59     /// The capacity on undirected edges

    60     typedef _Capacity Capacity;

    61     /// The value type of capacities

    62     typedef typename Capacity::Value Value;

    64   private:

    66     UGRAPH_TYPEDEFS(typename UGraph);

    68     const UGraph& _ugraph;

    69     const Capacity& _capacity;

    71     Node _root;

    72     typename UGraph::template NodeMap<Node>* _pred;

    73     typename UGraph::template NodeMap<Value>* _weight;

    74     typename UGraph::template NodeMap<int>* _order;

    76     void createStructures() {

    77       if (!_pred) {

    78 	_pred = new typename UGraph::template NodeMap<Node>(_ugraph);

    79       }

    80       if (!_weight) {

    81 	_weight = new typename UGraph::template NodeMap<Value>(_ugraph);

    82       }

    83       if (!_order) {

    84 	_order = new typename UGraph::template NodeMap<int>(_ugraph);

    85       }

    86     }

    88     void destroyStructures() {

    89       if (_pred) {

    90 	delete _pred;

    91       }

    92       if (_weight) {

    93 	delete _weight;

    94       }

    95       if (_order) {

    96 	delete _order;

    97       }

    98     }

   100   public:

   102     /// \brief Constructor

   103     ///

   104     /// Constructor

   105     /// \param ugraph The undirected graph type.

   106     /// \param capacity The capacity map.

   107     GomoryHuTree(const UGraph& ugraph, const Capacity& capacity)

   108       : _ugraph(ugraph), _capacity(capacity),

   109 	_pred(0), _weight(0), _order(0)

   110     {

   111       checkConcept<concepts::ReadMap<UEdge, Value>, Capacity>();

   112     }

   115     /// \brief Destructor

   116     ///

   117     /// Destructor

   118     ~GomoryHuTree() {

   119       destroyStructures();

   120     }

   122     /// \brief Initializes the internal data structures.

   123     ///

   124     /// Initializes the internal data structures.

   125     ///

   126     void init() {

   127       createStructures();

   129       _root = NodeIt(_ugraph);

   130       for (NodeIt n(_ugraph); n != INVALID; ++n) {

   131 	_pred->set(n, _root);

   132 	_order->set(n, -1);

   133       }

   134       _pred->set(_root, INVALID);

   135       _weight->set(_root, std::numeric_limits<Value>::max());

   136     }

   139     /// \brief Starts the algorithm

   140     ///

   141     /// Starts the algorithm.

   142     void start() {

   143       Preflow<UGraph, Capacity> fa(_ugraph, _capacity, _root, INVALID);

   145       for (NodeIt n(_ugraph); n != INVALID; ++n) {

   146 	if (n == _root) continue;

   148 	Node pn = (*_pred)[n];

   149 	fa.source(n);

   150 	fa.target(pn);

   152 	fa.runMinCut();

   154 	_weight->set(n, fa.flowValue());

   156 	for (NodeIt nn(_ugraph); nn != INVALID; ++nn) {

   157 	  if (nn != n && fa.minCut(nn) && (*_pred)[nn] == pn) {

   158 	    _pred->set(nn, n);

   159 	  }

   160 	}

   161 	if ((*_pred)[pn] != INVALID && fa.minCut((*_pred)[pn])) {

   162 	  _pred->set(n, (*_pred)[pn]);

   163 	  _pred->set(pn, n);

   164 	  _weight->set(n, (*_weight)[pn]);

   165 	  _weight->set(pn, fa.flowValue());

   166 	}

   167       }

   169       _order->set(_root, 0);

   170       int index = 1;

   172       for (NodeIt n(_ugraph); n != INVALID; ++n) {

   173 	std::vector<Node> st;

   174 	Node nn = n;

   175 	while ((*_order)[nn] == -1) {

   176 	  st.push_back(nn);

   177 	  nn = (*_pred)[nn];

   178 	}

   179 	while (!st.empty()) {

   180 	  _order->set(st.back(), index++);

   181 	  st.pop_back();

   182 	}

   183       }

   184     }

   186     /// \brief Runs the Gomory-Hu algorithm.

   187     ///

   188     /// Runs the Gomory-Hu algorithm.

   189     /// \note gh.run() is just a shortcut of the following code.

   190     /// \code

   191     ///   ght.init();

   192     ///   ght.start();

   193     /// \endcode

   194     void run() {

   195       init();

   196       start();

   197     }

   199     /// \brief Returns the predecessor node in the Gomory-Hu tree.

   200     ///

   201     /// Returns the predecessor node in the Gomory-Hu tree. If the node is

   202     /// the root of the Gomory-Hu tree, then it returns \c INVALID.

   203     Node predNode(const Node& node) {

   204       return (*_pred)[node];

   205     }

   207     /// \brief Returns the weight of the predecessor edge in the

   208     /// Gomory-Hu tree.

   209     ///

   210     /// Returns the weight of the predecessor edge in the Gomory-Hu

   211     /// tree.  If the node is the root of the Gomory-Hu tree, the

   212     /// result is undefined.

   213     Value predValue(const Node& node) {

   214       return (*_weight)[node];

   215     }

   217     /// \brief Returns the minimum cut value between two nodes

   218     ///

   219     /// Returns the minimum cut value between two nodes. The

   220     /// algorithm finds the nearest common ancestor in the Gomory-Hu

   221     /// tree and calculates the minimum weight edge on the paths to

   222     /// the ancestor.

   223     Value minCutValue(const Node& s, const Node& t) const {

   224       Node sn = s, tn = t;

   225       Value value = std::numeric_limits<Value>::max();

   227       while (sn != tn) {

   228 	if ((*_order)[sn] < (*_order)[tn]) {

   229 	  if ((*_weight)[tn] < value) value = (*_weight)[tn];

   230 	  tn = (*_pred)[tn];

   231 	} else {

   232 	  if ((*_weight)[sn] < value) value = (*_weight)[sn];

   233 	  sn = (*_pred)[sn];

   234 	}

   235       }

   236       return value;

   237     }

   239     /// \brief Returns the minimum cut between two nodes

   240     ///

   241     /// Returns the minimum cut value between two nodes. The

   242     /// algorithm finds the nearest common ancestor in the Gomory-Hu

   243     /// tree and calculates the minimum weight edge on the paths to

   244     /// the ancestor. Then it sets all nodes to the cut determined by

   245     /// this edge. The \c cutMap should be \ref concepts::ReadWriteMap

   246     /// "ReadWriteMap".

   247     template <typename CutMap>

   248     Value minCutMap(const Node& s, const Node& t, CutMap& cutMap) const {

   249       Node sn = s, tn = t;

   251       Node rn = INVALID;

   252       Value value = std::numeric_limits<Value>::max();

   254       while (sn != tn) {

   255 	if ((*_order)[sn] < (*_order)[tn]) {

   256 	  if ((*_weight)[tn] < value) {

   257 	    rn = tn;

   258 	    value = (*_weight)[tn];

   259 	  }

   260 	  tn = (*_pred)[tn];

   261 	} else {

   262 	  if ((*_weight)[sn] < value) {

   263 	    rn = sn;

   264 	    value = (*_weight)[sn];

   265 	  }

   266 	  sn = (*_pred)[sn];

   267 	}

   268       }

   270       typename UGraph::template NodeMap<bool> reached(_ugraph, false);

   271       reached.set(_root, true);

   272       cutMap.set(_root, false);

   273       reached.set(rn, true);

   274       cutMap.set(rn, true);

   276       for (NodeIt n(_ugraph); n != INVALID; ++n) {

   277 	std::vector<Node> st;

   278 	Node nn = n;

   279 	while (!reached[nn]) {

   280 	  st.push_back(nn);

   281 	  nn = (*_pred)[nn];

   282 	}

   283 	while (!st.empty()) {

   284 	  cutMap.set(st.back(), cutMap[nn]);

   285 	  st.pop_back();

   286 	}

   287       }

   289       return value;

   290     }

   292   };

   294 }

   296 #endif

author	kpeter
	Thu, 13 Nov 2008 16:17:50 +0000
changeset 2630	d239741cfd44
parent 2528	e6bc5c0032e9
permissions	-rw-r--r--