# Changeset 877:141f9c0db4a3 in lemon-1.2 for lemon/gomory_hu.h

Ignore:
Timestamp:
03/06/10 15:35:12 (10 years ago)
Branch:
default
Children:
878:f802439d2b58, 880:38213abd2911, 909:f112c18bc304
Phase:
public
Message:

Unify the sources (#339)

File:
1 edited

### Legend:

Unmodified
 r786 /* -*- C++ -*- /* -*- mode: C++; indent-tabs-mode: nil; -*- * * This file is a part of LEMON, a generic C++ optimization library * This file is a part of LEMON, a generic C++ optimization library. * * Copyright (C) 2003-2008 * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). /// \ingroup min_cut /// \file /// \file /// \brief Gomory-Hu cut tree in graphs. /// The Gomory-Hu tree is a tree on the node set of a given graph, but it /// may contain edges which are not in the original graph. It has the /// property that the minimum capacity edge of the path between two nodes /// property that the minimum capacity edge of the path between two nodes /// in this tree has the same weight as the minimum cut in the graph /// between these nodes. Moreover the components obtained by removing /// Therefore once this tree is computed, the minimum cut between any pair /// of nodes can easily be obtained. /// /// /// The algorithm calculates \e n-1 distinct minimum cuts (currently with /// the \ref Preflow algorithm), thus it has \f$O(n^3\sqrt{e})\f$ overall #ifdef DOXYGEN template typename CAP> #else template > typename CAP = typename GR::template EdgeMap > #endif class GomoryHu { /// The value type of capacities typedef typename Capacity::Value Value; private: void createStructures() { if (!_pred) { _pred = new typename Graph::template NodeMap(_graph); _pred = new typename Graph::template NodeMap(_graph); } if (!_weight) { _weight = new typename Graph::template NodeMap(_graph); _weight = new typename Graph::template NodeMap(_graph); } if (!_order) { _order = new typename Graph::template NodeMap(_graph); _order = new typename Graph::template NodeMap(_graph); } } void destroyStructures() { if (_pred) { delete _pred; delete _pred; } if (_weight) { delete _weight; delete _weight; } if (_order) { delete _order; } } delete _order; } } public: /// \param graph The undirected graph the algorithm runs on. /// \param capacity The edge capacity map. GomoryHu(const Graph& graph, const Capacity& capacity) GomoryHu(const Graph& graph, const Capacity& capacity) : _graph(graph), _capacity(capacity), _pred(0), _weight(0), _order(0) _pred(0), _weight(0), _order(0) { checkConcept, Capacity>(); private: // Initialize the internal data structures void init() { } (*_pred)[_root] = INVALID; (*_weight)[_root] = std::numeric_limits::max(); (*_weight)[_root] = std::numeric_limits::max(); } for (NodeIt n(_graph); n != INVALID; ++n) { if (n == _root) continue; Node pn = (*_pred)[n]; fa.source(n); fa.target(pn); fa.runMinCut(); (*_weight)[n] = fa.flowValue(); for (NodeIt nn(_graph); nn != INVALID; ++nn) { if (nn != n && fa.minCut(nn) && (*_pred)[nn] == pn) { (*_pred)[nn] = n; } } if ((*_pred)[pn] != INVALID && fa.minCut((*_pred)[pn])) { (*_pred)[n] = (*_pred)[pn]; (*_pred)[pn] = n; (*_weight)[n] = (*_weight)[pn]; (*_weight)[pn] = fa.flowValue(); } if (n == _root) continue; Node pn = (*_pred)[n]; fa.source(n); fa.target(pn); fa.runMinCut(); (*_weight)[n] = fa.flowValue(); for (NodeIt nn(_graph); nn != INVALID; ++nn) { if (nn != n && fa.minCut(nn) && (*_pred)[nn] == pn) { (*_pred)[nn] = n; } } if ((*_pred)[pn] != INVALID && fa.minCut((*_pred)[pn])) { (*_pred)[n] = (*_pred)[pn]; (*_pred)[pn] = n; (*_weight)[n] = (*_weight)[pn]; (*_weight)[pn] = fa.flowValue(); } } for (NodeIt n(_graph); n != INVALID; ++n) { std::vector st; Node nn = n; while ((*_order)[nn] == -1) { st.push_back(nn); nn = (*_pred)[nn]; } while (!st.empty()) { (*_order)[st.back()] = index++; st.pop_back(); } std::vector st; Node nn = n; while ((*_order)[nn] == -1) { st.push_back(nn); nn = (*_pred)[nn]; } while (!st.empty()) { (*_order)[st.back()] = index++; st.pop_back(); } } } ///\name Execution Control ///@{ start(); } /// @} /// Gomory-Hu tree. /// /// This function returns the weight of the predecessor edge of the /// This function returns the weight of the predecessor edge of the /// given node in the Gomory-Hu tree. /// If \c node is the root of the tree, the result is undefined. /// /// This function returns the minimum cut value between the nodes /// \c s and \c t. /// \c s and \c t. /// It finds the nearest common ancestor of the given nodes in the /// Gomory-Hu tree and calculates the minimum weight edge on the Node sn = s, tn = t; Value value = std::numeric_limits::max(); while (sn != tn) { if ((*_order)[sn] < (*_order)[tn]) { if ((*_weight)[tn] <= value) value = (*_weight)[tn]; tn = (*_pred)[tn]; } else { if ((*_weight)[sn] <= value) value = (*_weight)[sn]; sn = (*_pred)[sn]; } if ((*_order)[sn] < (*_order)[tn]) { if ((*_weight)[tn] <= value) value = (*_weight)[tn]; tn = (*_pred)[tn]; } else { if ((*_weight)[sn] <= value) value = (*_weight)[sn]; sn = (*_pred)[sn]; } } return value; Node rn = INVALID; Value value = std::numeric_limits::max(); while (sn != tn) { if ((*_order)[sn] < (*_order)[tn]) { if ((*_weight)[tn] <= value) { rn = tn; if ((*_order)[sn] < (*_order)[tn]) { if ((*_weight)[tn] <= value) { rn = tn; s_root = false; value = (*_weight)[tn]; } tn = (*_pred)[tn]; } else { if ((*_weight)[sn] <= value) { rn = sn; value = (*_weight)[tn]; } tn = (*_pred)[tn]; } else { if ((*_weight)[sn] <= value) { rn = sn; s_root = true; value = (*_weight)[sn]; } sn = (*_pred)[sn]; } value = (*_weight)[sn]; } sn = (*_pred)[sn]; } } std::vector st; for (NodeIt n(_graph); n != INVALID; ++n) { st.clear(); st.clear(); Node nn = n; while (!reached[nn]) { st.push_back(nn); nn = (*_pred)[nn]; } while (!st.empty()) { cutMap.set(st.back(), cutMap[nn]); st.pop_back(); } } while (!reached[nn]) { st.push_back(nn); nn = (*_pred)[nn]; } while (!st.empty()) { cutMap.set(st.back(), cutMap[nn]); st.pop_back(); } } return value; } /// Iterate on the nodes of a minimum cut /// This iterator class lists the nodes of a minimum cut found by /// GomoryHu. Before using it, you must allocate a GomoryHu class } }; friend class MinCutEdgeIt; /// Iterate on the edges of a minimum cut /// This iterator class lists the edges of a minimum cut found by /// GomoryHu. Before using it, you must allocate a GomoryHu class } } public: /// Constructor } /// Postfix incrementation /// Postfix incrementation. ///