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

Timestamp:

03/06/10 15:35:12 (14 years ago)

Author:

Alpar Juttner <alpar@…>

Branch:

default

Children:

878:f802439d2b58, 880:38213abd2911, 909:f112c18bc304

Phase:

public

Message:

Unify the sources (#339)

File:

• lemon/gomory_hu.h (modified) (24 diffs)

lemon/gomory_hu.h

@@ -1 @@
-/* -*- 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).
@@ -28 +28 @@
 
 /// \ingroup min_cut
-/// \file 
+/// \file
 /// \brief Gomory-Hu cut tree in graphs.
 
@@ -39 +39 @@
   /// 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
@@ -45 +45 @@
   /// 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
@@ -61 +61 @@
 #ifdef DOXYGEN
   template <typename GR,
-            typename CAP>
+            typename CAP>
 #else
   template <typename GR,
-            typename CAP = typename GR::template EdgeMap<int> >
+            typename CAP = typename GR::template EdgeMap<int> >
 #endif
   class GomoryHu {
@@ -75 +75 @@
     /// The value type of capacities
     typedef typename Capacity::Value Value;
-    
+
   private:
 
@@ -90 +90 @@
     void createStructures() {
       if (!_pred) {
-        _pred = new typename Graph::template NodeMap<Node>(_graph);
+        _pred = new typename Graph::template NodeMap<Node>(_graph);
       }
       if (!_weight) {
-        _weight = new typename Graph::template NodeMap<Value>(_graph);
+        _weight = new typename Graph::template NodeMap<Value>(_graph);
       }
       if (!_order) {
-        _order = new typename Graph::template NodeMap<int>(_graph);
+        _order = new typename Graph::template NodeMap<int>(_graph);
       }
     }
@@ -102 +102 @@
     void destroyStructures() {
       if (_pred) {
-        delete _pred;
+        delete _pred;
       }
       if (_weight) {
-        delete _weight;
+        delete _weight;
       }
       if (_order) {
-        delete _order;
-      }
-    }
-  
+        delete _order;
+      }
+    }
+
   public:
 
@@ -119 +119 @@
     /// \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<concepts::ReadMap<Edge, Value>, Capacity>();
@@ -135 +135 @@
 
   private:
-  
+
     // Initialize the internal data structures
     void init() {
@@ -146 +146 @@
       }
       (*_pred)[_root] = INVALID;
-      (*_weight)[_root] = std::numeric_limits<Value>::max(); 
+      (*_weight)[_root] = std::numeric_limits<Value>::max();
     }
 
@@ -155 +155 @@
 
       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();
+        }
       }
 
@@ -182 +182 @@
 
       for (NodeIt n(_graph); n != INVALID; ++n) {
-        std::vector<Node> 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<Node> 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();
+        }
       }
     }
@@ -198 +198 @@
 
     ///\name Execution Control
- 
+
     ///@{
 
@@ -208 +208 @@
       start();
     }
-    
+
     /// @}
 
@@ -233 +233 @@
     /// 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.
@@ -255 +255 @@
     ///
     /// 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
@@ -264 +264 @@
       Node sn = s, tn = t;
       Value value = std::numeric_limits<Value>::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;
@@ -303 +303 @@
       Node rn = INVALID;
       Value value = std::numeric_limits<Value>::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];
+        }
       }
 
@@ -330 +330 @@
       std::vector<Node> 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;
     }
@@ -350 +350 @@
 
     /// 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
@@ -443 +443 @@
       }
     };
-    
+
     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
@@ -480 +480 @@
           }
       }
-      
+
     public:
       /// Constructor
@@ -549 +549 @@
       }
       /// Postfix incrementation
-      
+
       /// Postfix incrementation.
       ///