COIN-OR::LEMON - Graph Library

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


Ignore:
Timestamp:
03/06/10 15:35:12 (10 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Children:
878:f802439d2b58, 880:38213abd2911, 909:f112c18bc304
Phase:
public
Message:

Unify the sources (#339)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/gomory_hu.h

    r786 r877  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    2828
    2929/// \ingroup min_cut
    30 /// \file 
     30/// \file
    3131/// \brief Gomory-Hu cut tree in graphs.
    3232
     
    3939  /// The Gomory-Hu tree is a tree on the node set of a given graph, but it
    4040  /// may contain edges which are not in the original graph. It has the
    41   /// property that the minimum capacity edge of the path between two nodes 
     41  /// property that the minimum capacity edge of the path between two nodes
    4242  /// in this tree has the same weight as the minimum cut in the graph
    4343  /// between these nodes. Moreover the components obtained by removing
     
    4545  /// Therefore once this tree is computed, the minimum cut between any pair
    4646  /// of nodes can easily be obtained.
    47   /// 
     47  ///
    4848  /// The algorithm calculates \e n-1 distinct minimum cuts (currently with
    4949  /// the \ref Preflow algorithm), thus it has \f$O(n^3\sqrt{e})\f$ overall
     
    6161#ifdef DOXYGEN
    6262  template <typename GR,
    63             typename CAP>
     63            typename CAP>
    6464#else
    6565  template <typename GR,
    66             typename CAP = typename GR::template EdgeMap<int> >
     66            typename CAP = typename GR::template EdgeMap<int> >
    6767#endif
    6868  class GomoryHu {
     
    7575    /// The value type of capacities
    7676    typedef typename Capacity::Value Value;
    77    
     77
    7878  private:
    7979
     
    9090    void createStructures() {
    9191      if (!_pred) {
    92         _pred = new typename Graph::template NodeMap<Node>(_graph);
     92        _pred = new typename Graph::template NodeMap<Node>(_graph);
    9393      }
    9494      if (!_weight) {
    95         _weight = new typename Graph::template NodeMap<Value>(_graph);
     95        _weight = new typename Graph::template NodeMap<Value>(_graph);
    9696      }
    9797      if (!_order) {
    98         _order = new typename Graph::template NodeMap<int>(_graph);
     98        _order = new typename Graph::template NodeMap<int>(_graph);
    9999      }
    100100    }
     
    102102    void destroyStructures() {
    103103      if (_pred) {
    104         delete _pred;
     104        delete _pred;
    105105      }
    106106      if (_weight) {
    107         delete _weight;
     107        delete _weight;
    108108      }
    109109      if (_order) {
    110         delete _order;
    111       }
    112     }
    113  
     110        delete _order;
     111      }
     112    }
     113
    114114  public:
    115115
     
    119119    /// \param graph The undirected graph the algorithm runs on.
    120120    /// \param capacity The edge capacity map.
    121     GomoryHu(const Graph& graph, const Capacity& capacity) 
     121    GomoryHu(const Graph& graph, const Capacity& capacity)
    122122      : _graph(graph), _capacity(capacity),
    123         _pred(0), _weight(0), _order(0)
     123        _pred(0), _weight(0), _order(0)
    124124    {
    125125      checkConcept<concepts::ReadMap<Edge, Value>, Capacity>();
     
    135135
    136136  private:
    137  
     137
    138138    // Initialize the internal data structures
    139139    void init() {
     
    146146      }
    147147      (*_pred)[_root] = INVALID;
    148       (*_weight)[_root] = std::numeric_limits<Value>::max(); 
     148      (*_weight)[_root] = std::numeric_limits<Value>::max();
    149149    }
    150150
     
    155155
    156156      for (NodeIt n(_graph); n != INVALID; ++n) {
    157         if (n == _root) continue;
    158 
    159         Node pn = (*_pred)[n];
    160         fa.source(n);
    161         fa.target(pn);
    162 
    163         fa.runMinCut();
    164 
    165         (*_weight)[n] = fa.flowValue();
    166 
    167         for (NodeIt nn(_graph); nn != INVALID; ++nn) {
    168           if (nn != n && fa.minCut(nn) && (*_pred)[nn] == pn) {
    169             (*_pred)[nn] = n;
    170           }
    171         }
    172         if ((*_pred)[pn] != INVALID && fa.minCut((*_pred)[pn])) {
    173           (*_pred)[n] = (*_pred)[pn];
    174           (*_pred)[pn] = n;
    175           (*_weight)[n] = (*_weight)[pn];
    176           (*_weight)[pn] = fa.flowValue();
    177         }
     157        if (n == _root) continue;
     158
     159        Node pn = (*_pred)[n];
     160        fa.source(n);
     161        fa.target(pn);
     162
     163        fa.runMinCut();
     164
     165        (*_weight)[n] = fa.flowValue();
     166
     167        for (NodeIt nn(_graph); nn != INVALID; ++nn) {
     168          if (nn != n && fa.minCut(nn) && (*_pred)[nn] == pn) {
     169            (*_pred)[nn] = n;
     170          }
     171        }
     172        if ((*_pred)[pn] != INVALID && fa.minCut((*_pred)[pn])) {
     173          (*_pred)[n] = (*_pred)[pn];
     174          (*_pred)[pn] = n;
     175          (*_weight)[n] = (*_weight)[pn];
     176          (*_weight)[pn] = fa.flowValue();
     177        }
    178178      }
    179179
     
    182182
    183183      for (NodeIt n(_graph); n != INVALID; ++n) {
    184         std::vector<Node> st;
    185         Node nn = n;
    186         while ((*_order)[nn] == -1) {
    187           st.push_back(nn);
    188           nn = (*_pred)[nn];
    189         }
    190         while (!st.empty()) {
    191           (*_order)[st.back()] = index++;
    192           st.pop_back();
    193         }
     184        std::vector<Node> st;
     185        Node nn = n;
     186        while ((*_order)[nn] == -1) {
     187          st.push_back(nn);
     188          nn = (*_pred)[nn];
     189        }
     190        while (!st.empty()) {
     191          (*_order)[st.back()] = index++;
     192          st.pop_back();
     193        }
    194194      }
    195195    }
     
    198198
    199199    ///\name Execution Control
    200  
     200
    201201    ///@{
    202202
     
    208208      start();
    209209    }
    210    
     210
    211211    /// @}
    212212
     
    233233    /// Gomory-Hu tree.
    234234    ///
    235     /// This function returns the weight of the predecessor edge of the 
     235    /// This function returns the weight of the predecessor edge of the
    236236    /// given node in the Gomory-Hu tree.
    237237    /// If \c node is the root of the tree, the result is undefined.
     
    255255    ///
    256256    /// This function returns the minimum cut value between the nodes
    257     /// \c s and \c t. 
     257    /// \c s and \c t.
    258258    /// It finds the nearest common ancestor of the given nodes in the
    259259    /// Gomory-Hu tree and calculates the minimum weight edge on the
     
    264264      Node sn = s, tn = t;
    265265      Value value = std::numeric_limits<Value>::max();
    266      
     266
    267267      while (sn != tn) {
    268         if ((*_order)[sn] < (*_order)[tn]) {
    269           if ((*_weight)[tn] <= value) value = (*_weight)[tn];
    270           tn = (*_pred)[tn];
    271         } else {
    272           if ((*_weight)[sn] <= value) value = (*_weight)[sn];
    273           sn = (*_pred)[sn];
    274         }
     268        if ((*_order)[sn] < (*_order)[tn]) {
     269          if ((*_weight)[tn] <= value) value = (*_weight)[tn];
     270          tn = (*_pred)[tn];
     271        } else {
     272          if ((*_weight)[sn] <= value) value = (*_weight)[sn];
     273          sn = (*_pred)[sn];
     274        }
    275275      }
    276276      return value;
     
    303303      Node rn = INVALID;
    304304      Value value = std::numeric_limits<Value>::max();
    305      
     305
    306306      while (sn != tn) {
    307         if ((*_order)[sn] < (*_order)[tn]) {
    308           if ((*_weight)[tn] <= value) {
    309             rn = tn;
     307        if ((*_order)[sn] < (*_order)[tn]) {
     308          if ((*_weight)[tn] <= value) {
     309            rn = tn;
    310310            s_root = false;
    311             value = (*_weight)[tn];
    312           }
    313           tn = (*_pred)[tn];
    314         } else {
    315           if ((*_weight)[sn] <= value) {
    316             rn = sn;
     311            value = (*_weight)[tn];
     312          }
     313          tn = (*_pred)[tn];
     314        } else {
     315          if ((*_weight)[sn] <= value) {
     316            rn = sn;
    317317            s_root = true;
    318             value = (*_weight)[sn];
    319           }
    320           sn = (*_pred)[sn];
    321         }
     318            value = (*_weight)[sn];
     319          }
     320          sn = (*_pred)[sn];
     321        }
    322322      }
    323323
     
    330330      std::vector<Node> st;
    331331      for (NodeIt n(_graph); n != INVALID; ++n) {
    332         st.clear();
     332        st.clear();
    333333        Node nn = n;
    334         while (!reached[nn]) {
    335           st.push_back(nn);
    336           nn = (*_pred)[nn];
    337         }
    338         while (!st.empty()) {
    339           cutMap.set(st.back(), cutMap[nn]);
    340           st.pop_back();
    341         }
    342       }
    343      
     334        while (!reached[nn]) {
     335          st.push_back(nn);
     336          nn = (*_pred)[nn];
     337        }
     338        while (!st.empty()) {
     339          cutMap.set(st.back(), cutMap[nn]);
     340          st.pop_back();
     341        }
     342      }
     343
    344344      return value;
    345345    }
     
    350350
    351351    /// Iterate on the nodes of a minimum cut
    352    
     352
    353353    /// This iterator class lists the nodes of a minimum cut found by
    354354    /// GomoryHu. Before using it, you must allocate a GomoryHu class
     
    443443      }
    444444    };
    445    
     445
    446446    friend class MinCutEdgeIt;
    447    
     447
    448448    /// Iterate on the edges of a minimum cut
    449    
     449
    450450    /// This iterator class lists the edges of a minimum cut found by
    451451    /// GomoryHu. Before using it, you must allocate a GomoryHu class
     
    480480          }
    481481      }
    482      
     482
    483483    public:
    484484      /// Constructor
     
    549549      }
    550550      /// Postfix incrementation
    551      
     551
    552552      /// Postfix incrementation.
    553553      ///
Note: See TracChangeset for help on using the changeset viewer.