Index: lemon/Makefile.am
===================================================================
--- lemon/Makefile.am	(revision 513)
+++ lemon/Makefile.am	(revision 531)
@@ -69,4 +69,5 @@
 	lemon/full_graph.h \
 	lemon/glpk.h \
+	lemon/gomory_hu_tree.h \
 	lemon/graph_to_eps.h \
 	lemon/grid_graph.h \
Index: lemon/clp.cc
===================================================================
--- lemon/clp.cc	(revision 528)
+++ lemon/clp.cc	(revision 462)
@@ -57,10 +57,10 @@
   }
 
-  ClpLp* ClpLp::newSolver() const {
+  ClpLp* ClpLp::_newSolver() const {
     ClpLp* newlp = new ClpLp;
     return newlp;
   }
 
-  ClpLp* ClpLp::cloneSolver() const {
+  ClpLp* ClpLp::_cloneSolver() const {
     ClpLp* copylp = new ClpLp(*this);
     return copylp;
Index: lemon/clp.h
===================================================================
--- lemon/clp.h	(revision 528)
+++ lemon/clp.h	(revision 462)
@@ -57,9 +57,4 @@
     ~ClpLp();
 
-    /// \e
-    virtual ClpLp* newSolver() const;
-    /// \e
-    virtual ClpLp* cloneSolver() const;
-
   protected:
 
@@ -71,4 +66,7 @@
 
   protected:
+
+    virtual ClpLp* _newSolver() const;
+    virtual ClpLp* _cloneSolver() const;
 
     virtual const char* _solverName() const;
Index: lemon/cplex.cc
===================================================================
--- lemon/cplex.cc	(revision 528)
+++ lemon/cplex.cc	(revision 462)
@@ -452,6 +452,6 @@
   CplexLp::~CplexLp() {}
 
-  CplexLp* CplexLp::newSolver() const { return new CplexLp; }
-  CplexLp* CplexLp::cloneSolver() const {return new CplexLp(*this); }
+  CplexLp* CplexLp::_newSolver() const { return new CplexLp; }
+  CplexLp* CplexLp::_cloneSolver() const {return new CplexLp(*this); }
 
   const char* CplexLp::_solverName() const { return "CplexLp"; }
@@ -824,6 +824,6 @@
   CplexMip::~CplexMip() {}
 
-  CplexMip* CplexMip::newSolver() const { return new CplexMip; }
-  CplexMip* CplexMip::cloneSolver() const {return new CplexMip(*this); }
+  CplexMip* CplexMip::_newSolver() const { return new CplexMip; }
+  CplexMip* CplexMip::_cloneSolver() const {return new CplexMip(*this); }
 
   const char* CplexMip::_solverName() const { return "CplexMip"; }
Index: lemon/cplex.h
===================================================================
--- lemon/cplex.h	(revision 528)
+++ lemon/cplex.h	(revision 462)
@@ -161,5 +161,5 @@
   /// This class implements an interface for the CPLEX LP solver.
   ///\ingroup lp_group
-  class CplexLp : public LpSolver, public CplexBase {
+  class CplexLp : public CplexBase, public LpSolver {
   public:
     /// \e
@@ -171,9 +171,4 @@
     /// \e
     virtual ~CplexLp();
-
-    /// \e
-    virtual CplexLp* cloneSolver() const;
-    /// \e
-    virtual CplexLp* newSolver() const;
 
   private:
@@ -191,4 +186,7 @@
 
   protected:
+
+    virtual CplexLp* _cloneSolver() const;
+    virtual CplexLp* _newSolver() const;
 
     virtual const char* _solverName() const;
@@ -225,5 +223,5 @@
   /// This class implements an interface for the CPLEX MIP solver.
   ///\ingroup lp_group
-  class CplexMip : public MipSolver, public CplexBase {
+  class CplexMip : public CplexBase, public MipSolver {
   public:
     /// \e
Index: lemon/glpk.cc
===================================================================
--- lemon/glpk.cc	(revision 530)
+++ lemon/glpk.cc	(revision 462)
@@ -523,10 +523,4 @@
   }
 
-  void GlpkBase::freeEnv() {
-    glp_free_env();
-  }
-
-  GlpkBase::FreeEnvHelper GlpkBase::freeEnvHelper;
-
   // GlpkLp members
 
@@ -541,6 +535,6 @@
   }
 
-  GlpkLp* GlpkLp::newSolver() const { return new GlpkLp; }
-  GlpkLp* GlpkLp::cloneSolver() const { return new GlpkLp(*this); }
+  GlpkLp* GlpkLp::_newSolver() const { return new GlpkLp; }
+  GlpkLp* GlpkLp::_cloneSolver() const { return new GlpkLp(*this); }
 
   const char* GlpkLp::_solverName() const { return "GlpkLp"; }
@@ -947,6 +941,6 @@
   }
 
-  GlpkMip* GlpkMip::newSolver() const { return new GlpkMip; }
-  GlpkMip* GlpkMip::cloneSolver() const {return new GlpkMip(*this); }
+  GlpkMip* GlpkMip::_newSolver() const { return new GlpkMip; }
+  GlpkMip* GlpkMip::_cloneSolver() const {return new GlpkMip(*this); }
 
   const char* GlpkMip::_solverName() const { return "GlpkMip"; }
Index: lemon/glpk.h
===================================================================
--- lemon/glpk.h	(revision 530)
+++ lemon/glpk.h	(revision 462)
@@ -101,16 +101,4 @@
     virtual void _clear();
 
-  private:
-
-    static void freeEnv();
-
-    struct FreeEnvHelper {
-      ~FreeEnvHelper() {
-        freeEnv();
-      }
-    };
-    
-    static FreeEnvHelper freeEnvHelper;
-    
   public:
 
@@ -132,5 +120,5 @@
   /// This class implements an interface for the GLPK LP solver.
   ///\ingroup lp_group
-  class GlpkLp : public LpSolver, public GlpkBase {
+  class GlpkLp : public GlpkBase, public LpSolver {
   public:
 
@@ -139,9 +127,4 @@
     ///\e
     GlpkLp(const GlpkLp&);
-
-    ///\e
-    virtual GlpkLp* cloneSolver() const;
-    ///\e
-    virtual GlpkLp* newSolver() const;
 
   private:
@@ -153,4 +136,7 @@
 
   protected:
+
+    virtual GlpkLp* _cloneSolver() const;
+    virtual GlpkLp* _newSolver() const;
 
     virtual const char* _solverName() const;
@@ -168,4 +154,6 @@
     virtual Value _getDualRay(int i) const;
 
+    ///\todo It should be clarified
+    ///
     virtual ProblemType _getPrimalType() const;
     virtual ProblemType _getDualType() const;
@@ -216,5 +204,5 @@
   /// This class implements an interface for the GLPK MIP solver.
   ///\ingroup lp_group
-  class GlpkMip : public MipSolver, public GlpkBase {
+  class GlpkMip : public GlpkBase, public MipSolver {
   public:
 
@@ -224,8 +212,8 @@
     GlpkMip(const GlpkMip&);
 
-    virtual GlpkMip* cloneSolver() const;
-    virtual GlpkMip* newSolver() const;
-
-  protected:
+  protected:
+
+    virtual GlpkMip* _cloneSolver() const;
+    virtual GlpkMip* _newSolver() const;
 
     virtual const char* _solverName() const;
Index: lemon/gomory_hu_tree.h
===================================================================
--- lemon/gomory_hu_tree.h	(revision 531)
+++ lemon/gomory_hu_tree.h	(revision 531)
@@ -0,0 +1,298 @@
+/* -*- 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/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 nodeset of the digraph, but it
+  /// may contain arcs which are not in the original digraph. It helps
+  /// to calculate the minimum cut between all pairs of nodes, because
+  /// the minimum capacity arc on the tree path between two nodes has
+  /// the same weight as the minimum cut in the digraph between these
+  /// nodes. Moreover this arc separates the nodes to two parts which
+  /// determine this minimum cut.
+  /// 
+  /// The algorithm calculates \e n-1 distinict minimum cuts with
+  /// preflow algorithm, therefore the algorithm has
+  /// \f$(O(n^3\sqrt{e})\f$ overall time complexity. It calculates a
+  /// rooted Gomory-Hu tree, the structure of the tree and the weights
+  /// can be obtained with \c predNode() and \c predValue()
+  /// functions. The \c minCutValue() and \c minCutMap() calculates
+  /// the minimum cut and the minimum cut value between any two node
+  /// in the digraph.
+  template <typename _Graph, 
+	    typename _Capacity = typename _Graph::template EdgeMap<int> >
+  class GomoryHuTree {
+  public:
+
+    /// The graph type
+    typedef _Graph Graph;
+    /// The capacity on edges
+    typedef _Capacity 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 type.
+    /// \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 Initializes the internal data structures.
+    ///
+    /// 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 Starts the algorithm
+    ///
+    /// Starts the algorithm.
+    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();
+	}
+      }
+    }
+
+    /// \brief Runs the Gomory-Hu algorithm.  
+    ///
+    /// Runs the Gomory-Hu algorithm.
+    /// \note gh.run() is just a shortcut of the following code.
+    /// \code
+    ///   ght.init();
+    ///   ght.start();
+    /// \endcode
+    void run() {
+      init();
+      start();
+    }
+
+    /// \brief Returns the predecessor node in the Gomory-Hu tree.
+    ///
+    /// 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 Returns the weight of the predecessor arc in the
+    /// Gomory-Hu tree.
+    ///
+    /// Returns the weight of the predecessor arc in the Gomory-Hu
+    /// tree.  If the node is the root of the Gomory-Hu tree, the
+    /// result is undefined.
+    Value predValue(const Node& node) {
+      return (*_weight)[node];
+    }
+
+    /// \brief Returns the minimum cut value between two nodes
+    ///
+    /// 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 Returns the minimum cut between two nodes
+    ///
+    /// 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. Then it sets all nodes to the cut determined by
+    /// this arc. The \c cutMap should be \ref concepts::ReadWriteMap
+    /// "ReadWriteMap".
+    template <typename CutMap>
+    Value minCutMap(const Node& s, const Node& t, CutMap& cutMap) const {
+      Node sn = s, tn = t;
+
+      Node rn = INVALID;
+      Value value = std::numeric_limits<Value>::max();
+      
+      while (sn != tn) {
+	if ((*_order)[sn] < (*_order)[tn]) {
+	  if ((*_weight)[tn] < value) {
+	    rn = tn;
+	    value = (*_weight)[tn];
+	  }
+	  tn = (*_pred)[tn];
+	} else {
+	  if ((*_weight)[sn] < value) {
+	    rn = sn;
+	    value = (*_weight)[sn];
+	  }
+	  sn = (*_pred)[sn];
+	}
+      }
+
+      typename Graph::template NodeMap<bool> reached(_graph, false);
+      reached.set(_root, true);
+      cutMap.set(_root, false);
+      reached.set(rn, true);
+      cutMap.set(rn, true);
+
+      for (NodeIt n(_graph); n != INVALID; ++n) {
+	std::vector<Node> st;
+	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;
+    }
+
+  };
+
+}
+
+#endif
Index: lemon/lp_base.h
===================================================================
--- lemon/lp_base.h	(revision 528)
+++ lemon/lp_base.h	(revision 490)
@@ -919,4 +919,6 @@
 
     //Abstract virtual functions
+    virtual LpBase* _newSolver() const = 0;
+    virtual LpBase* _cloneSolver() const = 0;
 
     virtual int _addColId(int col) { return cols.addIndex(col); }
@@ -985,4 +987,9 @@
     /// Virtual destructor
     virtual ~LpBase() {}
+
+    ///Creates a new LP problem
+    LpBase* newSolver() {return _newSolver();}
+    ///Makes a copy of the LP problem
+    LpBase* cloneSolver() {return _cloneSolver();}
 
     ///Gives back the name of the solver.
@@ -1815,9 +1822,4 @@
   public:
 
-    ///Allocate a new LP problem instance
-    virtual LpSolver* newSolver() const = 0;
-    ///Make a copy of the LP problem
-    virtual LpSolver* cloneSolver() const = 0;
-
     ///\name Solve the LP
 
@@ -1934,6 +1936,11 @@
     ///@}
 
+    LpSolver* newSolver() {return _newSolver();}
+    LpSolver* cloneSolver() {return _cloneSolver();}
+
   protected:
 
+    virtual LpSolver* _newSolver() const = 0;
+    virtual LpSolver* _cloneSolver() const = 0;
   };
 
@@ -1969,9 +1976,4 @@
     };
 
-    ///Allocate a new MIP problem instance
-    virtual MipSolver* newSolver() const = 0;
-    ///Make a copy of the MIP problem
-    virtual MipSolver* cloneSolver() const = 0;
-
     ///\name Solve the MIP
 
@@ -2061,4 +2063,13 @@
     virtual Value _getSolValue() const = 0;
 
+  public:
+
+    MipSolver* newSolver() {return _newSolver();}
+    MipSolver* cloneSolver() {return _cloneSolver();}
+
+  protected:
+
+    virtual MipSolver* _newSolver() const = 0;
+    virtual MipSolver* _cloneSolver() const = 0;
   };
 
Index: lemon/lp_skeleton.cc
===================================================================
--- lemon/lp_skeleton.cc	(revision 528)
+++ lemon/lp_skeleton.cc	(revision 459)
@@ -106,8 +106,8 @@
   { return BASIC; }
 
-  LpSkeleton* LpSkeleton::newSolver() const
+  LpSkeleton* LpSkeleton::_newSolver() const
   { return static_cast<LpSkeleton*>(0); }
 
-  LpSkeleton* LpSkeleton::cloneSolver() const
+  LpSkeleton* LpSkeleton::_cloneSolver() const
   { return static_cast<LpSkeleton*>(0); }
 
@@ -123,8 +123,8 @@
   { return UNDEFINED; }
 
-  MipSkeleton* MipSkeleton::newSolver() const
+  MipSkeleton* MipSkeleton::_newSolver() const
   { return static_cast<MipSkeleton*>(0); }
 
-  MipSkeleton* MipSkeleton::cloneSolver() const
+  MipSkeleton* MipSkeleton::_cloneSolver() const
   { return static_cast<MipSkeleton*>(0); }
 
Index: lemon/lp_skeleton.h
===================================================================
--- lemon/lp_skeleton.h	(revision 529)
+++ lemon/lp_skeleton.h	(revision 514)
@@ -23,14 +23,8 @@
 
 ///\file
-///\brief Skeleton file to implement LP/MIP solver interfaces
-///  
-///The classes in this file do nothing, but they can serve as skeletons when
-///implementing an interface to new solvers.
+///\brief A skeleton file to implement LP solver interfaces
 namespace lemon {
 
-  ///A skeleton class to implement LP/MIP solver base interface
-  
-  ///This class does nothing, but it can serve as a skeleton when
-  ///implementing an interface to new solvers.
+  ///A skeleton class to implement LP solver interfaces
   class SkeletonSolverBase : public virtual LpBase {
     int col_num,row_num;
@@ -143,18 +137,12 @@
   };
 
-  /// \brief Skeleton class for an LP solver interface
+  /// \brief Interface for a skeleton LP solver
   ///
-  ///This class does nothing, but it can serve as a skeleton when
-  ///implementing an interface to new solvers.
-
+  /// This class implements an interface for a skeleton LP solver.
   ///\ingroup lp_group
-  class LpSkeleton : public LpSolver, public SkeletonSolverBase {
+  class LpSkeleton : public SkeletonSolverBase, public LpSolver {
   public:
-    ///\e
-    LpSkeleton() : LpSolver(), SkeletonSolverBase() {}
-    ///\e
-    virtual LpSkeleton* newSolver() const;
-    ///\e
-    virtual LpSkeleton* cloneSolver() const;
+    LpSkeleton() : SkeletonSolverBase(), LpSolver() {}
+
   protected:
 
@@ -186,37 +174,53 @@
 
     ///\e
+    virtual LpSkeleton* _newSolver() const;
+    ///\e
+    virtual LpSkeleton* _cloneSolver() const;
+    ///\e
     virtual const char* _solverName() const;
 
   };
 
-  /// \brief Skeleton class for a MIP solver interface
+  /// \brief Interface for a skeleton MIP solver
   ///
-  ///This class does nothing, but it can serve as a skeleton when
-  ///implementing an interface to new solvers.
+  /// This class implements an interface for a skeleton MIP solver.
   ///\ingroup lp_group
-  class MipSkeleton : public MipSolver, public SkeletonSolverBase {
+  class MipSkeleton : public SkeletonSolverBase, public MipSolver {
   public:
-    ///\e
-    MipSkeleton() : MipSolver(), SkeletonSolverBase() {}
-    ///\e
-    virtual MipSkeleton* newSolver() const;
-    ///\e
-    virtual MipSkeleton* cloneSolver() const;
+    MipSkeleton() : SkeletonSolverBase(), MipSolver() {}
 
   protected:
     ///\e
+
+    ///\bug Wrong interface
+    ///
     virtual SolveExitStatus _solve();
 
     ///\e
+
+    ///\bug Wrong interface
+    ///
     virtual Value _getSol(int i) const;
 
     ///\e
+
+    ///\bug Wrong interface
+    ///
     virtual Value _getSolValue() const;
 
     ///\e
+
+    ///\bug Wrong interface
+    ///
     virtual ProblemType _getType() const;
 
     ///\e
+    virtual MipSkeleton* _newSolver() const;
+
+    ///\e
+    virtual MipSkeleton* _cloneSolver() const;
+    ///\e
     virtual const char* _solverName() const;
+
   };
 
Index: lemon/soplex.cc
===================================================================
--- lemon/soplex.cc	(revision 528)
+++ lemon/soplex.cc	(revision 462)
@@ -20,5 +20,5 @@
 #include <lemon/soplex.h>
 
-#include <soplex.h>
+#include <soplex/soplex.h>
 
 
@@ -55,10 +55,10 @@
   }
 
-  SoplexLp* SoplexLp::newSolver() const {
+  SoplexLp* SoplexLp::_newSolver() const {
     SoplexLp* newlp = new SoplexLp();
     return newlp;
   }
 
-  SoplexLp* SoplexLp::cloneSolver() const {
+  SoplexLp* SoplexLp::_cloneSolver() const {
     SoplexLp* newlp = new SoplexLp(*this);
     return newlp;
Index: lemon/soplex.h
===================================================================
--- lemon/soplex.h	(revision 528)
+++ lemon/soplex.h	(revision 462)
@@ -74,10 +74,9 @@
     /// \e
     ~SoplexLp();
-    /// \e
-    virtual SoplexLp* newSolver() const;
-    /// \e
-    virtual SoplexLp* cloneSolver() const;
 
   protected:
+
+    virtual SoplexLp* _newSolver() const;
+    virtual SoplexLp* _cloneSolver() const;
 
     virtual const char* _solverName() const;
Index: m4/lx_check_soplex.m4
===================================================================
--- m4/lx_check_soplex.m4	(revision 527)
+++ m4/lx_check_soplex.m4	(revision 457)
@@ -21,5 +21,5 @@
       SOPLEX_CXXFLAGS="-I$with_soplex_includedir"
     elif test x"$with_soplex" != x"yes"; then
-      SOPLEX_CXXFLAGS="-I$with_soplex/src"
+      SOPLEX_CXXFLAGS="-I$with_soplex/include"
     fi
 
@@ -39,5 +39,5 @@
 
     lx_soplex_test_prog='
-      #include <soplex.h>
+      #include <soplex/soplex.h>
 
       int main(int argc, char** argv)
Index: test/CMakeLists.txt
===================================================================
--- test/CMakeLists.txt	(revision 513)
+++ test/CMakeLists.txt	(revision 531)
@@ -22,4 +22,5 @@
   error_test
   euler_test
+  gomory_hu_test
   graph_copy_test
   graph_test
Index: test/Makefile.am
===================================================================
--- test/Makefile.am	(revision 513)
+++ test/Makefile.am	(revision 531)
@@ -18,4 +18,5 @@
 	test/error_test \
 	test/euler_test \
+	test/gomory_hu_test \
 	test/graph_copy_test \
 	test/graph_test \
@@ -58,4 +59,5 @@
 test_error_test_SOURCES = test/error_test.cc
 test_euler_test_SOURCES = test/euler_test.cc
+test_gomory_hu_test_SOURCES = test/gomory_hu_test.cc
 test_graph_copy_test_SOURCES = test/graph_copy_test.cc
 test_graph_test_SOURCES = test/graph_test.cc
Index: test/gomory_hu_test.cc
===================================================================
--- test/gomory_hu_test.cc	(revision 531)
+++ test/gomory_hu_test.cc	(revision 531)
@@ -0,0 +1,85 @@
+#include <iostream>
+
+#include "test_tools.h"
+#include <lemon/smart_graph.h>
+#include <lemon/adaptors.h>
+#include <lemon/lgf_reader.h>
+#include <lemon/lgf_writer.h>
+#include <lemon/dimacs.h>
+#include <lemon/time_measure.h>
+#include <lemon/gomory_hu_tree.h>
+#include <cstdlib>
+
+using namespace std;
+using namespace lemon;
+
+typedef SmartGraph Graph;
+
+char test_lgf[] =
+  "@nodes\n"
+  "label\n"
+  "0\n"
+  "1\n"
+  "2\n"
+  "3\n"
+  "4\n"
+  "@arcs\n"
+  "     label capacity\n"
+  "0 1  0     1\n"
+  "1 2  1     1\n"
+  "2 3  2     1\n"
+  "0 3  4     5\n"
+  "0 3  5     10\n"
+  "0 3  6     7\n"
+  "4 2  7     1\n"
+  "@attributes\n"
+  "source 0\n"
+  "target 3\n";
+  
+GRAPH_TYPEDEFS(Graph);
+typedef Graph::EdgeMap<int> IntEdgeMap;
+typedef Graph::NodeMap<bool> BoolNodeMap;
+
+int cutValue(const Graph& graph, const BoolNodeMap& cut,
+	     const IntEdgeMap& capacity) {
+
+  int sum = 0;
+  for (EdgeIt e(graph); e != INVALID; ++e) {
+    Node s = graph.u(e);
+    Node t = graph.v(e);
+
+    if (cut[s] != cut[t]) {
+      sum += capacity[e];
+    }
+  }
+  return sum;
+}
+
+
+int main() {
+  Graph graph;
+  IntEdgeMap capacity(graph);
+
+  std::istringstream input(test_lgf);
+  GraphReader<Graph>(graph, input).
+    edgeMap("capacity", capacity).run();
+
+  GomoryHuTree<Graph> ght(graph, capacity);
+  ght.init();
+  ght.run();
+
+  for (NodeIt u(graph); u != INVALID; ++u) {
+    for (NodeIt v(graph); v != u; ++v) {
+      Preflow<Graph, IntEdgeMap> pf(graph, capacity, u, v);
+      pf.runMinCut();
+      BoolNodeMap cm(graph);
+      ght.minCutMap(u, v, cm);
+      check(pf.flowValue() == ght.minCutValue(u, v), "Wrong cut 1");
+      check(cm[u] != cm[v], "Wrong cut 3");
+      check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 2");
+      
+    }
+  }
+  
+  return 0;
+}
Index: test/lp_test.cc
===================================================================
--- test/lp_test.cc	(revision 530)
+++ test/lp_test.cc	(revision 462)
@@ -198,9 +198,4 @@
     check(const_cast<const LpSolver::Expr&>(e)[p2]==0, buf.str());
 
-    //Test for clone/new
-    LP* lpnew = lp.newSolver();
-    LP* lpclone = lp.cloneSolver();
-    delete lpnew;
-    delete lpclone;
 
   }
@@ -253,6 +248,5 @@
   if (stat ==  LpSolver::OPTIMAL) {
     std::ostringstream sbuf;
-    sbuf << "Wrong optimal value (" << lp.primal() <<") with "
-         << lp.solverName() <<"\n     the right optimum is " << exp_opt;
+    sbuf << "Wrong optimal value: the right optimum is " << exp_opt;
     check(std::abs(lp.primal()-exp_opt) < 1e-3, sbuf.str());
   }
@@ -362,17 +356,4 @@
 }
 
-template<class LP>
-void cloneTest()
-{
-  //Test for clone/new
-  
-  LP* lp = new LP();
-  LP* lpnew = lp->newSolver();
-  LP* lpclone = lp->cloneSolver();
-  delete lp;
-  delete lpnew;
-  delete lpclone;
-}
-
 int main()
 {
@@ -385,5 +366,4 @@
     lpTest(lp_glpk1);
     aTest(lp_glpk2);
-    cloneTest<GlpkLp>();
   }
 #endif
@@ -402,5 +382,4 @@
 #endif
   }
-    cloneTest<CplexLp>();
 #endif
 
@@ -410,5 +389,4 @@
     lpTest(lp_soplex1);
     aTest(lp_soplex2);
-    cloneTest<SoplexLp>();
   }
 #endif
@@ -419,5 +397,4 @@
     lpTest(lp_clp1);
     aTest(lp_clp2);
-    cloneTest<ClpLp>();
   }
 #endif
Index: test/mip_test.cc
===================================================================
--- test/mip_test.cc	(revision 530)
+++ test/mip_test.cc	(revision 462)
@@ -107,15 +107,4 @@
 }
 
-template<class MIP>
-void cloneTest()
-{
-  
-  MIP* mip = new MIP();
-  MIP* mipnew = mip->newSolver();
-  MIP* mipclone = mip->cloneSolver();
-  delete mip;
-  delete mipnew;
-  delete mipclone;
-}
 
 int main()
@@ -126,5 +115,4 @@
     GlpkMip mip1;
     aTest(mip1);
-    cloneTest<GlpkMip>();
   }
 #endif
@@ -142,5 +130,4 @@
 #endif
   }
-  cloneTest<CplexMip>();
 #endif
 
