# HG changeset patch
# User Alpar Juttner <alpar@cs.elte.hu>
# Date 1235560257 0
# Node ID e72bacfea6b78fd9d84df2128824bc027f6e5afa
# Parent  ccd2d3a3001ebc80a67dd8d4de56486d82eec773
Remane GomoryHuTree to GomoryHu (#66)

diff -r ccd2d3a3001e -r e72bacfea6b7 lemon/Makefile.am
--- a/lemon/Makefile.am	Wed Feb 25 11:10:52 2009 +0000
+++ b/lemon/Makefile.am	Wed Feb 25 11:10:57 2009 +0000
@@ -68,7 +68,7 @@
 	lemon/euler.h \
 	lemon/full_graph.h \
 	lemon/glpk.h \
-	lemon/gomory_hu_tree.h \
+	lemon/gomory_hu.h \
 	lemon/graph_to_eps.h \
 	lemon/grid_graph.h \
 	lemon/hypercube_graph.h \
diff -r ccd2d3a3001e -r e72bacfea6b7 lemon/gomory_hu.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/gomory_hu.h	Wed Feb 25 11:10:57 2009 +0000
@@ -0,0 +1,554 @@
+/* -*- C++ -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2003-2008
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#ifndef LEMON_GOMORY_HU_TREE_H
+#define LEMON_GOMORY_HU_TREE_H
+
+#include <limits>
+
+#include <lemon/core.h>
+#include <lemon/preflow.h>
+#include <lemon/concept_check.h>
+#include <lemon/concepts/maps.h>
+
+/// \ingroup min_cut
+/// \file 
+/// \brief Gomory-Hu cut tree in graphs.
+
+namespace lemon {
+
+  /// \ingroup min_cut
+  ///
+  /// \brief Gomory-Hu cut tree algorithm
+  ///
+  /// The Gomory-Hu tree is a tree on the node set of the graph, but it
+  /// may contain edges which are not in the original digraph. It has the
+  /// 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 digraph
+  /// between these nodes. Moreover the components obtained by removing
+  /// this edge from the tree determine the corresponding minimum cut.
+  ///
+  /// 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), therefore the algorithm has
+  /// \f$(O(n^3\sqrt{e})\f$ overall time complexity. It calculates a
+  /// rooted Gomory-Hu tree, its structure and the weights can be obtained
+  /// by \c predNode(), \c predValue() and \c rootDist().
+  /// 
+  /// The members \c minCutMap() and \c minCutValue() calculate
+  /// the minimum cut and the minimum cut value between any two node
+  /// in the digraph. You can also list (iterate on) the nodes and the
+  /// edges of the cuts using MinCutNodeIt and MinCutEdgeIt.
+  ///
+  /// \tparam GR The undirected graph data structure the algorithm will run on
+  /// \tparam CAP type of the EdgeMap describing the Edge capacities.
+  /// it is typename GR::template EdgeMap<int> by default.
+  template <typename GR,
+	    typename CAP = typename GR::template EdgeMap<int>
+            >
+  class GomoryHu {
+  public:
+
+    /// The graph type
+    typedef GR Graph;
+    /// The type if the edge capacity map
+    typedef CAP Capacity;
+    /// The value type of capacities
+    typedef typename Capacity::Value Value;
+    
+  private:
+
+    TEMPLATE_GRAPH_TYPEDEFS(Graph);
+
+    const Graph& _graph;
+    const Capacity& _capacity;
+
+    Node _root;
+    typename Graph::template NodeMap<Node>* _pred;
+    typename Graph::template NodeMap<Value>* _weight;
+    typename Graph::template NodeMap<int>* _order;
+
+    void createStructures() {
+      if (!_pred) {
+	_pred = new typename Graph::template NodeMap<Node>(_graph);
+      }
+      if (!_weight) {
+	_weight = new typename Graph::template NodeMap<Value>(_graph);
+      }
+      if (!_order) {
+	_order = new typename Graph::template NodeMap<int>(_graph);
+      }
+    }
+
+    void destroyStructures() {
+      if (_pred) {
+	delete _pred;
+      }
+      if (_weight) {
+	delete _weight;
+      }
+      if (_order) {
+	delete _order;
+      }
+    }
+  
+  public:
+
+    /// \brief Constructor
+    ///
+    /// Constructor
+    /// \param graph The graph the algorithm will run on.
+    /// \param capacity The capacity map.
+    GomoryHu(const Graph& graph, const Capacity& capacity) 
+      : _graph(graph), _capacity(capacity),
+	_pred(0), _weight(0), _order(0) 
+    {
+      checkConcept<concepts::ReadMap<Edge, Value>, Capacity>();
+    }
+
+
+    /// \brief Destructor
+    ///
+    /// Destructor
+    ~GomoryHu() {
+      destroyStructures();
+    }
+
+    // \brief Initialize the internal data structures.
+    //
+    // This function initializes the internal data structures.
+    //
+    void init() {
+      createStructures();
+
+      _root = NodeIt(_graph);
+      for (NodeIt n(_graph); n != INVALID; ++n) {
+	_pred->set(n, _root);
+	_order->set(n, -1);
+      }
+      _pred->set(_root, INVALID);
+      _weight->set(_root, std::numeric_limits<Value>::max()); 
+    }
+
+
+    // \brief Start the algorithm
+    //
+    // This function starts the algorithm.
+    //
+    // \pre \ref init() must be called before using this function.
+    //
+    void start() {
+      Preflow<Graph, Capacity> fa(_graph, _capacity, _root, INVALID);
+
+      for (NodeIt n(_graph); n != INVALID; ++n) {
+	if (n == _root) continue;
+
+	Node pn = (*_pred)[n];
+	fa.source(n);
+	fa.target(pn);
+
+	fa.runMinCut();
+
+	_weight->set(n, fa.flowValue());
+
+	for (NodeIt nn(_graph); nn != INVALID; ++nn) {
+	  if (nn != n && fa.minCut(nn) && (*_pred)[nn] == pn) {
+	    _pred->set(nn, n);
+	  }
+	}
+	if ((*_pred)[pn] != INVALID && fa.minCut((*_pred)[pn])) {
+	  _pred->set(n, (*_pred)[pn]);
+	  _pred->set(pn, n);
+	  _weight->set(n, (*_weight)[pn]);
+	  _weight->set(pn, fa.flowValue());	
+	}
+      }
+
+      _order->set(_root, 0);
+      int index = 1;
+
+      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->set(st.back(), index++);
+	  st.pop_back();
+	}
+      }
+    }
+
+    ///\name Execution Control
+ 
+    ///@{
+
+    /// \brief Run the Gomory-Hu algorithm.
+    ///
+    /// This function runs the Gomory-Hu algorithm.
+    void run() {
+      init();
+      start();
+    }
+    
+    /// @}
+
+    ///\name Query Functions
+    ///The results of the algorithm can be obtained using these
+    ///functions.\n
+    ///The \ref run() "run()" should be called before using them.\n
+    ///See also MinCutNodeIt and MinCutEdgeIt
+
+    ///@{
+
+    /// \brief Return the predecessor node in the Gomory-Hu tree.
+    ///
+    /// This function returns the predecessor node in the Gomory-Hu tree.
+    /// If the node is
+    /// the root of the Gomory-Hu tree, then it returns \c INVALID.
+    Node predNode(const Node& node) {
+      return (*_pred)[node];
+    }
+
+    /// \brief Return the distance from the root node in the Gomory-Hu tree.
+    ///
+    /// This function returns the distance of \c node from the root node
+    /// in the Gomory-Hu tree.
+    int rootDist(const Node& node) {
+      return (*_order)[node];
+    }
+
+    /// \brief Return the weight of the predecessor edge in the
+    /// Gomory-Hu tree.
+    ///
+    /// This function returns the weight of the predecessor edge in the
+    /// Gomory-Hu tree.  If the node is the root, the result is undefined.
+    Value predValue(const Node& node) {
+      return (*_weight)[node];
+    }
+
+    /// \brief Return the minimum cut value between two nodes
+    ///
+    /// This function returns the minimum cut value between two nodes. The
+    /// algorithm finds the nearest common ancestor in the Gomory-Hu
+    /// tree and calculates the minimum weight arc on the paths to
+    /// the ancestor.
+    Value minCutValue(const Node& s, const Node& t) const {
+      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];
+	}
+      }
+      return value;
+    }
+
+    /// \brief Return the minimum cut between two nodes
+    ///
+    /// This function returns the minimum cut between the nodes \c s and \c t
+    /// the \r cutMap parameter by setting the nodes in the component of
+    /// \c \s to true and the other nodes to false.
+    ///
+    /// The \c cutMap should be \ref concepts::ReadWriteMap
+    /// "ReadWriteMap".
+    ///
+    /// For higher level interfaces, see MinCutNodeIt and MinCutEdgeIt
+    template <typename CutMap>
+    Value minCutMap(const Node& s, ///< Base node
+                    const Node& t,
+                    ///< The node you want to separate from Node s.
+                    CutMap& cutMap
+                    ///< The cut will be return in this map.
+                    /// It must be a \c bool \ref concepts::ReadWriteMap
+                    /// "ReadWriteMap" on the graph nodes.
+                    ) const {
+      Node sn = s, tn = t;
+      bool s_root=false;
+      Node rn = INVALID;
+      Value value = std::numeric_limits<Value>::max();
+      
+      while (sn != 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;
+            s_root = true;
+	    value = (*_weight)[sn];
+	  }
+	  sn = (*_pred)[sn];
+	}
+      }
+
+      typename Graph::template NodeMap<bool> reached(_graph, false);
+      reached.set(_root, true);
+      cutMap.set(_root, !s_root);
+      reached.set(rn, true);
+      cutMap.set(rn, s_root);
+
+      std::vector<Node> st;
+      for (NodeIt n(_graph); n != INVALID; ++n) {
+	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();
+	}
+      }
+      
+      return value;
+    }
+
+    ///@}
+
+    friend class MinCutNodeIt;
+
+    /// 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,
+    /// and call its \ref GomoryHu::run() "run()" method.
+    ///
+    /// This example counts the nodes in the minimum cut separating \c s from
+    /// \c t.
+    /// \code
+    /// GomoruHu<Graph> gom(g, capacities);
+    /// gom.run();
+    /// int sum=0;
+    /// for(GomoruHu<Graph>::MinCutNodeIt n(gom,s,t);n!=INVALID;++n) ++sum;
+    /// \endcode
+    class MinCutNodeIt
+    {
+      bool _side;
+      typename Graph::NodeIt _node_it;
+      typename Graph::template NodeMap<bool> _cut;
+    public:
+      /// Constructor
+
+      /// Constructor
+      ///
+      MinCutNodeIt(GomoryHu const &gomory,
+                   ///< The GomoryHu class. You must call its
+                   ///  run() method
+                   ///  before initializing this iterator
+                   const Node& s, ///< Base node
+                   const Node& t,
+                   ///< The node you want to separate from Node s.
+                   bool side=true
+                   ///< If it is \c true (default) then the iterator lists
+                   ///  the nodes of the component containing \c s,
+                   ///  otherwise it lists the other component.
+                   /// \note As the minimum cut is not always unique,
+                   /// \code
+                   /// MinCutNodeIt(gomory, s, t, true);
+                   /// \endcode
+                   /// and
+                   /// \code
+                   /// MinCutNodeIt(gomory, t, s, false);
+                   /// \endcode
+                   /// does not necessarily give the same set of nodes.
+                   /// However it is ensured that
+                   /// \code
+                   /// MinCutNodeIt(gomory, s, t, true);
+                   /// \endcode
+                   /// and
+                   /// \code
+                   /// MinCutNodeIt(gomory, s, t, false);
+                   /// \endcode
+                   /// together list each node exactly once.
+                   )
+        : _side(side), _cut(gomory._graph)
+      {
+        gomory.minCutMap(s,t,_cut);
+        for(_node_it=typename Graph::NodeIt(gomory._graph);
+            _node_it!=INVALID && _cut[_node_it]!=_side;
+            ++_node_it) {}
+      }
+      /// Conversion to Node
+
+      /// Conversion to Node
+      ///
+      operator typename Graph::Node() const
+      {
+        return _node_it;
+      }
+      bool operator==(Invalid) { return _node_it==INVALID; }
+      bool operator!=(Invalid) { return _node_it!=INVALID; }
+      /// Next node
+
+      /// Next node
+      ///
+      MinCutNodeIt &operator++()
+      {
+        for(++_node_it;_node_it!=INVALID&&_cut[_node_it]!=_side;++_node_it) {}
+        return *this;
+      }
+      /// Postfix incrementation
+
+      /// Postfix incrementation
+      ///
+      /// \warning This incrementation
+      /// returns a \c Node, not a \ref MinCutNodeIt, as one may
+      /// expect.
+      typename Graph::Node operator++(int)
+      {
+        typename Graph::Node n=*this;
+        ++(*this);
+        return n;
+      }
+    };
+    
+    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,
+    /// and call its \ref GomoryHu::run() "run()" method.
+    ///
+    /// This example computes the value of the minimum cut separating \c s from
+    /// \c t.
+    /// \code
+    /// GomoruHu<Graph> gom(g, capacities);
+    /// gom.run();
+    /// int value=0;
+    /// for(GomoruHu<Graph>::MinCutEdgeIt e(gom,s,t);e!=INVALID;++e)
+    ///   value+=capacities[e];
+    /// \endcode
+    /// the result will be the same as it is returned by
+    /// \ref GomoryHu::minCostValue() "gom.minCostValue(s,t)"
+    class MinCutEdgeIt
+    {
+      bool _side;
+      const Graph &_graph;
+      typename Graph::NodeIt _node_it;
+      typename Graph::OutArcIt _arc_it;
+      typename Graph::template NodeMap<bool> _cut;
+      void step()
+      {
+        ++_arc_it;
+        while(_node_it!=INVALID && _arc_it==INVALID)
+          {
+            for(++_node_it;_node_it!=INVALID&&!_cut[_node_it];++_node_it) {}
+            if(_node_it!=INVALID)
+              _arc_it=typename Graph::OutArcIt(_graph,_node_it);
+          }
+      }
+      
+    public:
+      MinCutEdgeIt(GomoryHu const &gomory,
+                   ///< The GomoryHu class. You must call its
+                   ///  run() method
+                   ///  before initializing this iterator
+                   const Node& s,  ///< Base node
+                   const Node& t,
+                   ///< The node you want to separate from Node s.
+                   bool side=true
+                   ///< If it is \c true (default) then the listed arcs
+                   ///  will be oriented from the
+                   ///  the nodes of the component containing \c s,
+                   ///  otherwise they will be oriented in the opposite
+                   ///  direction.
+                   )
+        : _graph(gomory._graph), _cut(_graph)
+      {
+        gomory.minCutMap(s,t,_cut);
+        if(!side)
+          for(typename Graph::NodeIt n(_graph);n!=INVALID;++n)
+            _cut[n]=!_cut[n];
+
+        for(_node_it=typename Graph::NodeIt(_graph);
+            _node_it!=INVALID && !_cut[_node_it];
+            ++_node_it) {}
+        _arc_it = _node_it!=INVALID ?
+          typename Graph::OutArcIt(_graph,_node_it) : INVALID;
+        while(_node_it!=INVALID && _arc_it == INVALID)
+          {
+            for(++_node_it; _node_it!=INVALID&&!_cut[_node_it]; ++_node_it) {}
+            if(_node_it!=INVALID)
+              _arc_it= typename Graph::OutArcIt(_graph,_node_it);
+          }
+        while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step();
+      }
+      /// Conversion to Arc
+
+      /// Conversion to Arc
+      ///
+      operator typename Graph::Arc() const
+      {
+        return _arc_it;
+      }
+      /// Conversion to Edge
+
+      /// Conversion to Edge
+      ///
+      operator typename Graph::Edge() const
+      {
+        return _arc_it;
+      }
+      bool operator==(Invalid) { return _node_it==INVALID; }
+      bool operator!=(Invalid) { return _node_it!=INVALID; }
+      /// Next edge
+
+      /// Next edge
+      ///
+      MinCutEdgeIt &operator++()
+      {
+        step();
+        while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step();
+        return *this;
+      }
+      /// Postfix incrementation
+      
+      /// Postfix incrementation
+      ///
+      /// \warning This incrementation
+      /// returns a \c Arc, not a \ref MinCutEdgeIt, as one may
+      /// expect.
+      typename Graph::Arc operator++(int)
+      {
+        typename Graph::Arc e=*this;
+        ++(*this);
+        return e;
+      }
+    };
+
+  };
+
+}
+
+#endif
diff -r ccd2d3a3001e -r e72bacfea6b7 lemon/gomory_hu_tree.h
--- a/lemon/gomory_hu_tree.h	Wed Feb 25 11:10:52 2009 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,554 +0,0 @@
-/* -*- C++ -*-
- *
- * This file is a part of LEMON, a generic C++ optimization library
- *
- * Copyright (C) 2003-2008
- * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
- * (Egervary Research Group on Combinatorial Optimization, EGRES).
- *
- * Permission to use, modify and distribute this software is granted
- * provided that this copyright notice appears in all copies. For
- * precise terms see the accompanying LICENSE file.
- *
- * This software is provided "AS IS" with no warranty of any kind,
- * express or implied, and with no claim as to its suitability for any
- * purpose.
- *
- */
-
-#ifndef LEMON_GOMORY_HU_TREE_H
-#define LEMON_GOMORY_HU_TREE_H
-
-#include <limits>
-
-#include <lemon/core.h>
-#include <lemon/preflow.h>
-#include <lemon/concept_check.h>
-#include <lemon/concepts/maps.h>
-
-/// \ingroup min_cut
-/// \file 
-/// \brief Gomory-Hu cut tree in graphs.
-
-namespace lemon {
-
-  /// \ingroup min_cut
-  ///
-  /// \brief Gomory-Hu cut tree algorithm
-  ///
-  /// The Gomory-Hu tree is a tree on the node set of the graph, but it
-  /// may contain edges which are not in the original digraph. It has the
-  /// 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 digraph
-  /// between these nodes. Moreover the components obtained by removing
-  /// this edge from the tree determine the corresponding minimum cut.
-  ///
-  /// 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), therefore the algorithm has
-  /// \f$(O(n^3\sqrt{e})\f$ overall time complexity. It calculates a
-  /// rooted Gomory-Hu tree, its structure and the weights can be obtained
-  /// by \c predNode(), \c predValue() and \c rootDist().
-  /// 
-  /// The members \c minCutMap() and \c minCutValue() calculate
-  /// the minimum cut and the minimum cut value between any two node
-  /// in the digraph. You can also list (iterate on) the nodes and the
-  /// edges of the cuts using MinCutNodeIt and MinCutEdgeIt.
-  ///
-  /// \tparam GR The undirected graph data structure the algorithm will run on
-  /// \tparam CAP type of the EdgeMap describing the Edge capacities.
-  /// it is typename GR::template EdgeMap<int> by default.
-  template <typename GR,
-	    typename CAP = typename GR::template EdgeMap<int>
-            >
-  class GomoryHuTree {
-  public:
-
-    /// The graph type
-    typedef GR Graph;
-    /// The type if the edge capacity map
-    typedef CAP Capacity;
-    /// The value type of capacities
-    typedef typename Capacity::Value Value;
-    
-  private:
-
-    TEMPLATE_GRAPH_TYPEDEFS(Graph);
-
-    const Graph& _graph;
-    const Capacity& _capacity;
-
-    Node _root;
-    typename Graph::template NodeMap<Node>* _pred;
-    typename Graph::template NodeMap<Value>* _weight;
-    typename Graph::template NodeMap<int>* _order;
-
-    void createStructures() {
-      if (!_pred) {
-	_pred = new typename Graph::template NodeMap<Node>(_graph);
-      }
-      if (!_weight) {
-	_weight = new typename Graph::template NodeMap<Value>(_graph);
-      }
-      if (!_order) {
-	_order = new typename Graph::template NodeMap<int>(_graph);
-      }
-    }
-
-    void destroyStructures() {
-      if (_pred) {
-	delete _pred;
-      }
-      if (_weight) {
-	delete _weight;
-      }
-      if (_order) {
-	delete _order;
-      }
-    }
-  
-  public:
-
-    /// \brief Constructor
-    ///
-    /// Constructor
-    /// \param graph The graph the algorithm will run on.
-    /// \param capacity The capacity map.
-    GomoryHuTree(const Graph& graph, const Capacity& capacity) 
-      : _graph(graph), _capacity(capacity),
-	_pred(0), _weight(0), _order(0) 
-    {
-      checkConcept<concepts::ReadMap<Edge, Value>, Capacity>();
-    }
-
-
-    /// \brief Destructor
-    ///
-    /// Destructor
-    ~GomoryHuTree() {
-      destroyStructures();
-    }
-
-    // \brief Initialize the internal data structures.
-    //
-    // This function initializes the internal data structures.
-    //
-    void init() {
-      createStructures();
-
-      _root = NodeIt(_graph);
-      for (NodeIt n(_graph); n != INVALID; ++n) {
-	_pred->set(n, _root);
-	_order->set(n, -1);
-      }
-      _pred->set(_root, INVALID);
-      _weight->set(_root, std::numeric_limits<Value>::max()); 
-    }
-
-
-    // \brief Start the algorithm
-    //
-    // This function starts the algorithm.
-    //
-    // \pre \ref init() must be called before using this function.
-    //
-    void start() {
-      Preflow<Graph, Capacity> fa(_graph, _capacity, _root, INVALID);
-
-      for (NodeIt n(_graph); n != INVALID; ++n) {
-	if (n == _root) continue;
-
-	Node pn = (*_pred)[n];
-	fa.source(n);
-	fa.target(pn);
-
-	fa.runMinCut();
-
-	_weight->set(n, fa.flowValue());
-
-	for (NodeIt nn(_graph); nn != INVALID; ++nn) {
-	  if (nn != n && fa.minCut(nn) && (*_pred)[nn] == pn) {
-	    _pred->set(nn, n);
-	  }
-	}
-	if ((*_pred)[pn] != INVALID && fa.minCut((*_pred)[pn])) {
-	  _pred->set(n, (*_pred)[pn]);
-	  _pred->set(pn, n);
-	  _weight->set(n, (*_weight)[pn]);
-	  _weight->set(pn, fa.flowValue());	
-	}
-      }
-
-      _order->set(_root, 0);
-      int index = 1;
-
-      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->set(st.back(), index++);
-	  st.pop_back();
-	}
-      }
-    }
-
-    ///\name Execution Control
- 
-    ///@{
-
-    /// \brief Run the Gomory-Hu algorithm.
-    ///
-    /// This function runs the Gomory-Hu algorithm.
-    void run() {
-      init();
-      start();
-    }
-    
-    /// @}
-
-    ///\name Query Functions
-    ///The results of the algorithm can be obtained using these
-    ///functions.\n
-    ///The \ref run() "run()" should be called before using them.\n
-    ///See also MinCutNodeIt and MinCutEdgeIt
-
-    ///@{
-
-    /// \brief Return the predecessor node in the Gomory-Hu tree.
-    ///
-    /// This function returns the predecessor node in the Gomory-Hu tree.
-    /// If the node is
-    /// the root of the Gomory-Hu tree, then it returns \c INVALID.
-    Node predNode(const Node& node) {
-      return (*_pred)[node];
-    }
-
-    /// \brief Return the distance from the root node in the Gomory-Hu tree.
-    ///
-    /// This function returns the distance of \c node from the root node
-    /// in the Gomory-Hu tree.
-    int rootDist(const Node& node) {
-      return (*_order)[node];
-    }
-
-    /// \brief Return the weight of the predecessor edge in the
-    /// Gomory-Hu tree.
-    ///
-    /// This function returns the weight of the predecessor edge in the
-    /// Gomory-Hu tree.  If the node is the root, the result is undefined.
-    Value predValue(const Node& node) {
-      return (*_weight)[node];
-    }
-
-    /// \brief Return the minimum cut value between two nodes
-    ///
-    /// This function returns the minimum cut value between two nodes. The
-    /// algorithm finds the nearest common ancestor in the Gomory-Hu
-    /// tree and calculates the minimum weight arc on the paths to
-    /// the ancestor.
-    Value minCutValue(const Node& s, const Node& t) const {
-      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];
-	}
-      }
-      return value;
-    }
-
-    /// \brief Return the minimum cut between two nodes
-    ///
-    /// This function returns the minimum cut between the nodes \c s and \c t
-    /// the \r cutMap parameter by setting the nodes in the component of
-    /// \c \s to true and the other nodes to false.
-    ///
-    /// The \c cutMap should be \ref concepts::ReadWriteMap
-    /// "ReadWriteMap".
-    ///
-    /// For higher level interfaces, see MinCutNodeIt and MinCutEdgeIt
-    template <typename CutMap>
-    Value minCutMap(const Node& s, ///< Base node
-                    const Node& t,
-                    ///< The node you want to separate from Node s.
-                    CutMap& cutMap
-                    ///< The cut will be return in this map.
-                    /// It must be a \c bool \ref concepts::ReadWriteMap
-                    /// "ReadWriteMap" on the graph nodes.
-                    ) const {
-      Node sn = s, tn = t;
-      bool s_root=false;
-      Node rn = INVALID;
-      Value value = std::numeric_limits<Value>::max();
-      
-      while (sn != 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;
-            s_root = true;
-	    value = (*_weight)[sn];
-	  }
-	  sn = (*_pred)[sn];
-	}
-      }
-
-      typename Graph::template NodeMap<bool> reached(_graph, false);
-      reached.set(_root, true);
-      cutMap.set(_root, !s_root);
-      reached.set(rn, true);
-      cutMap.set(rn, s_root);
-
-      std::vector<Node> st;
-      for (NodeIt n(_graph); n != INVALID; ++n) {
-	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();
-	}
-      }
-      
-      return value;
-    }
-
-    ///@}
-
-    friend class MinCutNodeIt;
-
-    /// Iterate on the nodes of a minimum cut
-    
-    /// This iterator class lists the nodes of a minimum cut found by
-    /// GomoryHuTree. Before using it, you must allocate a GomoryHuTree class,
-    /// and call its \ref GomoryHuTree::run() "run()" method.
-    ///
-    /// This example counts the nodes in the minimum cut separating \c s from
-    /// \c t.
-    /// \code
-    /// GomoruHuTree<Graph> gom(g, capacities);
-    /// gom.run();
-    /// int sum=0;
-    /// for(GomoruHuTree<Graph>::MinCutNodeIt n(gom,s,t);n!=INVALID;++n) ++sum;
-    /// \endcode
-    class MinCutNodeIt
-    {
-      bool _side;
-      typename Graph::NodeIt _node_it;
-      typename Graph::template NodeMap<bool> _cut;
-    public:
-      /// Constructor
-
-      /// Constructor
-      ///
-      MinCutNodeIt(GomoryHuTree const &gomory,
-                   ///< The GomoryHuTree class. You must call its
-                   ///  run() method
-                   ///  before initializing this iterator
-                   const Node& s, ///< Base node
-                   const Node& t,
-                   ///< The node you want to separate from Node s.
-                   bool side=true
-                   ///< If it is \c true (default) then the iterator lists
-                   ///  the nodes of the component containing \c s,
-                   ///  otherwise it lists the other component.
-                   /// \note As the minimum cut is not always unique,
-                   /// \code
-                   /// MinCutNodeIt(gomory, s, t, true);
-                   /// \endcode
-                   /// and
-                   /// \code
-                   /// MinCutNodeIt(gomory, t, s, false);
-                   /// \endcode
-                   /// does not necessarily give the same set of nodes.
-                   /// However it is ensured that
-                   /// \code
-                   /// MinCutNodeIt(gomory, s, t, true);
-                   /// \endcode
-                   /// and
-                   /// \code
-                   /// MinCutNodeIt(gomory, s, t, false);
-                   /// \endcode
-                   /// together list each node exactly once.
-                   )
-        : _side(side), _cut(gomory._graph)
-      {
-        gomory.minCutMap(s,t,_cut);
-        for(_node_it=typename Graph::NodeIt(gomory._graph);
-            _node_it!=INVALID && _cut[_node_it]!=_side;
-            ++_node_it) {}
-      }
-      /// Conversion to Node
-
-      /// Conversion to Node
-      ///
-      operator typename Graph::Node() const
-      {
-        return _node_it;
-      }
-      bool operator==(Invalid) { return _node_it==INVALID; }
-      bool operator!=(Invalid) { return _node_it!=INVALID; }
-      /// Next node
-
-      /// Next node
-      ///
-      MinCutNodeIt &operator++()
-      {
-        for(++_node_it;_node_it!=INVALID&&_cut[_node_it]!=_side;++_node_it) {}
-        return *this;
-      }
-      /// Postfix incrementation
-
-      /// Postfix incrementation
-      ///
-      /// \warning This incrementation
-      /// returns a \c Node, not a \ref MinCutNodeIt, as one may
-      /// expect.
-      typename Graph::Node operator++(int)
-      {
-        typename Graph::Node n=*this;
-        ++(*this);
-        return n;
-      }
-    };
-    
-    friend class MinCutEdgeIt;
-    
-    /// Iterate on the edges of a minimum cut
-    
-    /// This iterator class lists the edges of a minimum cut found by
-    /// GomoryHuTree. Before using it, you must allocate a GomoryHuTree class,
-    /// and call its \ref GomoryHuTree::run() "run()" method.
-    ///
-    /// This example computes the value of the minimum cut separating \c s from
-    /// \c t.
-    /// \code
-    /// GomoruHuTree<Graph> gom(g, capacities);
-    /// gom.run();
-    /// int value=0;
-    /// for(GomoruHuTree<Graph>::MinCutEdgeIt e(gom,s,t);e!=INVALID;++e)
-    ///   value+=capacities[e];
-    /// \endcode
-    /// the result will be the same as it is returned by
-    /// \ref GomoryHuTree::minCostValue() "gom.minCostValue(s,t)"
-    class MinCutEdgeIt
-    {
-      bool _side;
-      const Graph &_graph;
-      typename Graph::NodeIt _node_it;
-      typename Graph::OutArcIt _arc_it;
-      typename Graph::template NodeMap<bool> _cut;
-      void step()
-      {
-        ++_arc_it;
-        while(_node_it!=INVALID && _arc_it==INVALID)
-          {
-            for(++_node_it;_node_it!=INVALID&&!_cut[_node_it];++_node_it) {}
-            if(_node_it!=INVALID)
-              _arc_it=typename Graph::OutArcIt(_graph,_node_it);
-          }
-      }
-      
-    public:
-      MinCutEdgeIt(GomoryHuTree const &gomory,
-                   ///< The GomoryHuTree class. You must call its
-                   ///  run() method
-                   ///  before initializing this iterator
-                   const Node& s,  ///< Base node
-                   const Node& t,
-                   ///< The node you want to separate from Node s.
-                   bool side=true
-                   ///< If it is \c true (default) then the listed arcs
-                   ///  will be oriented from the
-                   ///  the nodes of the component containing \c s,
-                   ///  otherwise they will be oriented in the opposite
-                   ///  direction.
-                   )
-        : _graph(gomory._graph), _cut(_graph)
-      {
-        gomory.minCutMap(s,t,_cut);
-        if(!side)
-          for(typename Graph::NodeIt n(_graph);n!=INVALID;++n)
-            _cut[n]=!_cut[n];
-
-        for(_node_it=typename Graph::NodeIt(_graph);
-            _node_it!=INVALID && !_cut[_node_it];
-            ++_node_it) {}
-        _arc_it = _node_it!=INVALID ?
-          typename Graph::OutArcIt(_graph,_node_it) : INVALID;
-        while(_node_it!=INVALID && _arc_it == INVALID)
-          {
-            for(++_node_it; _node_it!=INVALID&&!_cut[_node_it]; ++_node_it) {}
-            if(_node_it!=INVALID)
-              _arc_it= typename Graph::OutArcIt(_graph,_node_it);
-          }
-        while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step();
-      }
-      /// Conversion to Arc
-
-      /// Conversion to Arc
-      ///
-      operator typename Graph::Arc() const
-      {
-        return _arc_it;
-      }
-      /// Conversion to Edge
-
-      /// Conversion to Edge
-      ///
-      operator typename Graph::Edge() const
-      {
-        return _arc_it;
-      }
-      bool operator==(Invalid) { return _node_it==INVALID; }
-      bool operator!=(Invalid) { return _node_it!=INVALID; }
-      /// Next edge
-
-      /// Next edge
-      ///
-      MinCutEdgeIt &operator++()
-      {
-        step();
-        while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step();
-        return *this;
-      }
-      /// Postfix incrementation
-      
-      /// Postfix incrementation
-      ///
-      /// \warning This incrementation
-      /// returns a \c Arc, not a \ref MinCutEdgeIt, as one may
-      /// expect.
-      typename Graph::Arc operator++(int)
-      {
-        typename Graph::Arc e=*this;
-        ++(*this);
-        return e;
-      }
-    };
-
-  };
-
-}
-
-#endif
diff -r ccd2d3a3001e -r e72bacfea6b7 test/gomory_hu_test.cc
--- a/test/gomory_hu_test.cc	Wed Feb 25 11:10:52 2009 +0000
+++ b/test/gomory_hu_test.cc	Wed Feb 25 11:10:57 2009 +0000
@@ -3,7 +3,7 @@
 #include "test_tools.h"
 #include <lemon/smart_graph.h>
 #include <lemon/lgf_reader.h>
-#include <lemon/gomory_hu_tree.h>
+#include <lemon/gomory_hu.h>
 #include <cstdlib>
 
 using namespace std;
@@ -60,7 +60,7 @@
   GraphReader<Graph>(graph, input).
     edgeMap("capacity", capacity).run();
 
-  GomoryHuTree<Graph> ght(graph, capacity);
+  GomoryHu<Graph> ght(graph, capacity);
   ght.init();
   ght.run();
 
@@ -75,14 +75,14 @@
       check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 2");
 
       int sum=0;
-      for(GomoryHuTree<Graph>::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a)
+      for(GomoryHu<Graph>::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a)
         sum+=capacity[a]; 
       check(sum == ght.minCutValue(u, v), "Problem with MinCutEdgeIt");
 
       sum=0;
-      for(GomoryHuTree<Graph>::MinCutNodeIt n(ght, u, v,true);n!=INVALID;++n)
+      for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,true);n!=INVALID;++n)
         sum++;
-      for(GomoryHuTree<Graph>::MinCutNodeIt n(ght, u, v,false);n!=INVALID;++n)
+      for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,false);n!=INVALID;++n)
         sum++;
       check(sum == countNodes(graph), "Problem with MinCutNodeIt");