Merge
authorAlpar Juttner <alpar@cs.elte.hu>
Thu, 20 Mar 2008 23:06:35 +0000
changeset 1069ba2d265e191
parent 104 cdbba181b786
parent 105 e4948ef6a4ca
child 107 31a2e6d28f61
Merge
lemon/Makefile.am
test/Makefile.am
     1.1 --- a/lemon/Makefile.am	Thu Mar 20 21:59:35 2008 +0000
     1.2 +++ b/lemon/Makefile.am	Thu Mar 20 23:06:35 2008 +0000
     1.3 @@ -23,13 +23,15 @@
     1.4          lemon/dijkstra.h \
     1.5          lemon/dim2.h \
     1.6  	lemon/error.h \
     1.7 -        lemon/graph_utils.h \
     1.8 +	lemon/graph_utils.h \
     1.9 +	lemon/kruskal.h \
    1.10  	lemon/list_graph.h \
    1.11  	lemon/maps.h \
    1.12  	lemon/math.h \
    1.13  	lemon/path.h \
    1.14          lemon/random.h \
    1.15 -        lemon/tolerance.h
    1.16 +        lemon/tolerance.h \
    1.17 +	lemon/unionfind.h
    1.18  
    1.19  bits_HEADERS += \
    1.20  	lemon/bits/alteration_notifier.h \
     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/lemon/kruskal.h	Thu Mar 20 23:06:35 2008 +0000
     2.3 @@ -0,0 +1,319 @@
     2.4 +/* -*- C++ -*-
     2.5 + *
     2.6 + * This file is a part of LEMON, a generic C++ optimization library
     2.7 + *
     2.8 + * Copyright (C) 2003-2008
     2.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    2.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    2.11 + *
    2.12 + * Permission to use, modify and distribute this software is granted
    2.13 + * provided that this copyright notice appears in all copies. For
    2.14 + * precise terms see the accompanying LICENSE file.
    2.15 + *
    2.16 + * This software is provided "AS IS" with no warranty of any kind,
    2.17 + * express or implied, and with no claim as to its suitability for any
    2.18 + * purpose.
    2.19 + *
    2.20 + */
    2.21 +
    2.22 +#ifndef LEMON_KRUSKAL_H
    2.23 +#define LEMON_KRUSKAL_H
    2.24 +
    2.25 +#include <algorithm>
    2.26 +#include <vector>
    2.27 +#include <lemon/unionfind.h>
    2.28 +// #include <lemon/graph_utils.h>
    2.29 +#include <lemon/maps.h>
    2.30 +
    2.31 +// #include <lemon/radix_sort.h>
    2.32 +
    2.33 +#include <lemon/bits/utility.h>
    2.34 +#include <lemon/bits/traits.h>
    2.35 +
    2.36 +///\ingroup spantree
    2.37 +///\file
    2.38 +///\brief Kruskal's algorithm to compute a minimum cost tree
    2.39 +///
    2.40 +///Kruskal's algorithm to compute a minimum cost tree.
    2.41 +///
    2.42 +
    2.43 +namespace lemon {
    2.44 +
    2.45 +  namespace _kruskal_bits {
    2.46 +
    2.47 +    // Kruskal for directed graphs.
    2.48 +
    2.49 +    template <typename Digraph, typename In, typename Out>
    2.50 +    typename disable_if<lemon::UndirectedTagIndicator<Digraph>,
    2.51 +		       typename In::value_type::second_type >::type
    2.52 +    kruskal(const Digraph& digraph, const In& in, Out& out,dummy<0> = 0) {
    2.53 +      typedef typename In::value_type::second_type Value;
    2.54 +      typedef typename Digraph::template NodeMap<int> IndexMap;
    2.55 +      typedef typename Digraph::Node Node;
    2.56 +      
    2.57 +      IndexMap index(digraph);
    2.58 +      UnionFind<IndexMap> uf(index);
    2.59 +      for (typename Digraph::NodeIt it(digraph); it != INVALID; ++it) {
    2.60 +        uf.insert(it);
    2.61 +      }
    2.62 +      
    2.63 +      Value tree_value = 0;
    2.64 +      for (typename In::const_iterator it = in.begin(); it != in.end(); ++it) {
    2.65 +        if (uf.join(digraph.target(it->first),digraph.source(it->first))) {
    2.66 +          out.set(it->first, true);
    2.67 +          tree_value += it->second;
    2.68 +        }
    2.69 +        else {
    2.70 +          out.set(it->first, false);
    2.71 +        }
    2.72 +      }
    2.73 +      return tree_value;
    2.74 +    }
    2.75 +
    2.76 +    // Kruskal for undirected graphs.
    2.77 +
    2.78 +    template <typename Graph, typename In, typename Out>
    2.79 +    typename enable_if<lemon::UndirectedTagIndicator<Graph>,
    2.80 +		       typename In::value_type::second_type >::type
    2.81 +    kruskal(const Graph& graph, const In& in, Out& out,dummy<1> = 1) {
    2.82 +      typedef typename In::value_type::second_type Value;
    2.83 +      typedef typename Graph::template NodeMap<int> IndexMap;
    2.84 +      typedef typename Graph::Node Node;
    2.85 +      
    2.86 +      IndexMap index(graph);
    2.87 +      UnionFind<IndexMap> uf(index);
    2.88 +      for (typename Graph::NodeIt it(graph); it != INVALID; ++it) {
    2.89 +        uf.insert(it);
    2.90 +      }
    2.91 +      
    2.92 +      Value tree_value = 0;
    2.93 +      for (typename In::const_iterator it = in.begin(); it != in.end(); ++it) {
    2.94 +        if (uf.join(graph.u(it->first),graph.v(it->first))) {
    2.95 +          out.set(it->first, true);
    2.96 +          tree_value += it->second;
    2.97 +        }
    2.98 +        else {
    2.99 +          out.set(it->first, false);
   2.100 +        }
   2.101 +      }
   2.102 +      return tree_value;
   2.103 +    }
   2.104 +
   2.105 +
   2.106 +    template <typename Sequence>
   2.107 +    struct PairComp {
   2.108 +      typedef typename Sequence::value_type Value;
   2.109 +      bool operator()(const Value& left, const Value& right) {
   2.110 +	return left.second < right.second;
   2.111 +      }
   2.112 +    };
   2.113 +
   2.114 +    template <typename In, typename Enable = void>
   2.115 +    struct SequenceInputIndicator {
   2.116 +      static const bool value = false;
   2.117 +    };
   2.118 +
   2.119 +    template <typename In>
   2.120 +    struct SequenceInputIndicator<In, 
   2.121 +      typename exists<typename In::value_type::first_type>::type> {
   2.122 +      static const bool value = true;
   2.123 +    };
   2.124 +
   2.125 +    template <typename In, typename Enable = void>
   2.126 +    struct MapInputIndicator {
   2.127 +      static const bool value = false;
   2.128 +    };
   2.129 +
   2.130 +    template <typename In>
   2.131 +    struct MapInputIndicator<In, 
   2.132 +      typename exists<typename In::Value>::type> {
   2.133 +      static const bool value = true;
   2.134 +    };
   2.135 +
   2.136 +    template <typename In, typename Enable = void>
   2.137 +    struct SequenceOutputIndicator {
   2.138 +      static const bool value = false;
   2.139 +    };
   2.140 + 
   2.141 +    template <typename Out>
   2.142 +    struct SequenceOutputIndicator<Out, 
   2.143 +      typename exists<typename Out::value_type>::type> {
   2.144 +      static const bool value = true;
   2.145 +    };
   2.146 +
   2.147 +    template <typename Out, typename Enable = void>
   2.148 +    struct MapOutputIndicator {
   2.149 +      static const bool value = false;
   2.150 +    };
   2.151 +
   2.152 +    template <typename Out>
   2.153 +    struct MapOutputIndicator<Out, 
   2.154 +      typename exists<typename Out::Value>::type> {
   2.155 +      static const bool value = true;
   2.156 +    };
   2.157 +
   2.158 +    template <typename In, typename InEnable = void>
   2.159 +    struct KruskalValueSelector {};
   2.160 +
   2.161 +    template <typename In>
   2.162 +    struct KruskalValueSelector<In,
   2.163 +      typename enable_if<SequenceInputIndicator<In>, void>::type> 
   2.164 +    {
   2.165 +      typedef typename In::value_type::second_type Value;
   2.166 +    };    
   2.167 +
   2.168 +    template <typename In>
   2.169 +    struct KruskalValueSelector<In,
   2.170 +      typename enable_if<MapInputIndicator<In>, void>::type> 
   2.171 +    {
   2.172 +      typedef typename In::Value Value;
   2.173 +    };    
   2.174 +    
   2.175 +    template <typename Graph, typename In, typename Out,
   2.176 +              typename InEnable = void>
   2.177 +    struct KruskalInputSelector {};
   2.178 +
   2.179 +    template <typename Graph, typename In, typename Out,
   2.180 +              typename InEnable = void>
   2.181 +    struct KruskalOutputSelector {};
   2.182 +    
   2.183 +    template <typename Graph, typename In, typename Out>
   2.184 +    struct KruskalInputSelector<Graph, In, Out,
   2.185 +      typename enable_if<SequenceInputIndicator<In>, void>::type > 
   2.186 +    {
   2.187 +      typedef typename In::value_type::second_type Value;
   2.188 +
   2.189 +      static Value kruskal(const Graph& graph, const In& in, Out& out) {
   2.190 +        return KruskalOutputSelector<Graph, In, Out>::
   2.191 +          kruskal(graph, in, out);
   2.192 +      }
   2.193 +
   2.194 +    };
   2.195 +
   2.196 +    template <typename Graph, typename In, typename Out>
   2.197 +    struct KruskalInputSelector<Graph, In, Out,
   2.198 +      typename enable_if<MapInputIndicator<In>, void>::type > 
   2.199 +    {
   2.200 +      typedef typename In::Value Value;
   2.201 +      static Value kruskal(const Graph& graph, const In& in, Out& out) {
   2.202 +        typedef typename In::Key MapArc;
   2.203 +        typedef typename In::Value Value;
   2.204 +        typedef typename ItemSetTraits<Graph, MapArc>::ItemIt MapArcIt;
   2.205 +        typedef std::vector<std::pair<MapArc, Value> > Sequence;
   2.206 +        Sequence seq;
   2.207 +        
   2.208 +        for (MapArcIt it(graph); it != INVALID; ++it) {
   2.209 +          seq.push_back(std::make_pair(it, in[it]));
   2.210 +        }
   2.211 +
   2.212 +        std::sort(seq.begin(), seq.end(), PairComp<Sequence>());
   2.213 +        return KruskalOutputSelector<Graph, Sequence, Out>::
   2.214 +          kruskal(graph, seq, out);
   2.215 +      }
   2.216 +    };
   2.217 +
   2.218 +    template <typename Graph, typename In, typename Out>
   2.219 +    struct KruskalOutputSelector<Graph, In, Out,
   2.220 +      typename enable_if<SequenceOutputIndicator<Out>, void>::type > 
   2.221 +    {
   2.222 +      typedef typename In::value_type::second_type Value;
   2.223 +
   2.224 +      static Value kruskal(const Graph& graph, const In& in, Out& out) {
   2.225 +        typedef StoreBoolMap<Out> Map;
   2.226 +        Map map(out);
   2.227 +        return _kruskal_bits::kruskal(graph, in, map);
   2.228 +      }
   2.229 +
   2.230 +    };
   2.231 +
   2.232 +    template <typename Graph, typename In, typename Out>
   2.233 +    struct KruskalOutputSelector<Graph, In, Out,
   2.234 +      typename enable_if<MapOutputIndicator<Out>, void>::type > 
   2.235 +    {
   2.236 +      typedef typename In::value_type::second_type Value;
   2.237 +
   2.238 +      static Value kruskal(const Graph& graph, const In& in, Out& out) {
   2.239 +        return _kruskal_bits::kruskal(graph, in, out);
   2.240 +      }
   2.241 +    };
   2.242 +
   2.243 +  }
   2.244 +
   2.245 +  /// \ingroup spantree
   2.246 +  ///
   2.247 +  /// \brief Kruskal's algorithm to find a minimum cost tree of a graph.
   2.248 +  ///
   2.249 +  /// This function runs Kruskal's algorithm to find a minimum cost tree.
   2.250 +  /// Due to some C++ hacking, it accepts various input and output types.
   2.251 +  ///
   2.252 +  /// \param g The graph the algorithm runs on.
   2.253 +  /// It can be either \ref concepts::Digraph "directed" or 
   2.254 +  /// \ref concepts::Graph "undirected".
   2.255 +  /// If the graph is directed, the algorithm consider it to be 
   2.256 +  /// undirected by disregarding the direction of the arcs.
   2.257 +  ///
   2.258 +  /// \param in This object is used to describe the arc costs. It can be one
   2.259 +  /// of the following choices.
   2.260 +  /// - An STL compatible 'Forward Container' with
   2.261 +  /// <tt>std::pair<GR::Edge,X></tt> or
   2.262 +  /// <tt>std::pair<GR::Arc,X></tt> as its <tt>value_type</tt>, where
   2.263 +  /// \c X is the type of the costs. The pairs indicates the arcs
   2.264 +  /// along with the assigned cost. <em>They must be in a
   2.265 +  /// cost-ascending order.</em>
   2.266 +  /// - Any readable Arc map. The values of the map indicate the arc costs.
   2.267 +  ///
   2.268 +  /// \retval out Here we also have a choise.
   2.269 +  /// - It can be a writable \c bool arc map.  After running the
   2.270 +  /// algorithm this will contain the found minimum cost spanning
   2.271 +  /// tree: the value of an arc will be set to \c true if it belongs
   2.272 +  /// to the tree, otherwise it will be set to \c false. The value of
   2.273 +  /// each arc will be set exactly once.
   2.274 +  /// - It can also be an iteraror of an STL Container with
   2.275 +  /// <tt>GR::Edge</tt> or <tt>GR::Arc</tt> as its
   2.276 +  /// <tt>value_type</tt>.  The algorithm copies the elements of the
   2.277 +  /// found tree into this sequence.  For example, if we know that the
   2.278 +  /// spanning tree of the graph \c g has say 53 arcs, then we can
   2.279 +  /// put its arcs into an STL vector \c tree with a code like this.
   2.280 +  ///\code
   2.281 +  /// std::vector<Arc> tree(53);
   2.282 +  /// kruskal(g,cost,tree.begin());
   2.283 +  ///\endcode
   2.284 +  /// Or if we don't know in advance the size of the tree, we can
   2.285 +  /// write this.  
   2.286 +  ///\code std::vector<Arc> tree;
   2.287 +  /// kruskal(g,cost,std::back_inserter(tree)); 
   2.288 +  ///\endcode
   2.289 +  ///
   2.290 +  /// \return The total cost of the found tree.
   2.291 +  ///
   2.292 +  /// \warning If kruskal runs on an be consistent of using the same
   2.293 +  /// Arc type for input and output.
   2.294 +  ///
   2.295 +
   2.296 +#ifdef DOXYGEN
   2.297 +  template <class Graph, class In, class Out>
   2.298 +  Value kruskal(GR const& g, const In& in, Out& out)
   2.299 +#else 
   2.300 +  template <class Graph, class In, class Out>
   2.301 +  inline typename _kruskal_bits::KruskalValueSelector<In>::Value 
   2.302 +  kruskal(const Graph& graph, const In& in, Out& out) 
   2.303 +#endif
   2.304 +  {
   2.305 +    return _kruskal_bits::KruskalInputSelector<Graph, In, Out>::
   2.306 +      kruskal(graph, in, out);
   2.307 +  }
   2.308 +
   2.309 + 
   2.310 +  
   2.311 +
   2.312 +  template <class Graph, class In, class Out>
   2.313 +  inline typename _kruskal_bits::KruskalValueSelector<In>::Value
   2.314 +  kruskal(const Graph& graph, const In& in, const Out& out)
   2.315 +  {
   2.316 +    return _kruskal_bits::KruskalInputSelector<Graph, In, const Out>::
   2.317 +      kruskal(graph, in, out);
   2.318 +  }  
   2.319 +
   2.320 +} //namespace lemon
   2.321 +
   2.322 +#endif //LEMON_KRUSKAL_H
     3.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.2 +++ b/lemon/unionfind.h	Thu Mar 20 23:06:35 2008 +0000
     3.3 @@ -0,0 +1,1796 @@
     3.4 +/* -*- C++ -*-
     3.5 + *
     3.6 + * This file is a part of LEMON, a generic C++ optimization library
     3.7 + *
     3.8 + * Copyright (C) 2003-2008
     3.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    3.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    3.11 + *
    3.12 + * Permission to use, modify and distribute this software is granted
    3.13 + * provided that this copyright notice appears in all copies. For
    3.14 + * precise terms see the accompanying LICENSE file.
    3.15 + *
    3.16 + * This software is provided "AS IS" with no warranty of any kind,
    3.17 + * express or implied, and with no claim as to its suitability for any
    3.18 + * purpose.
    3.19 + *
    3.20 + */
    3.21 +
    3.22 +#ifndef LEMON_UNION_FIND_H
    3.23 +#define LEMON_UNION_FIND_H
    3.24 +
    3.25 +//!\ingroup auxdat
    3.26 +//!\file
    3.27 +//!\brief Union-Find data structures.
    3.28 +//!
    3.29 +
    3.30 +#include <vector>
    3.31 +#include <list>
    3.32 +#include <utility>
    3.33 +#include <algorithm>
    3.34 +#include <functional>
    3.35 +
    3.36 +#include <lemon/bits/invalid.h>
    3.37 +
    3.38 +namespace lemon {
    3.39 +
    3.40 +  /// \ingroup auxdat
    3.41 +  ///
    3.42 +  /// \brief A \e Union-Find data structure implementation
    3.43 +  ///
    3.44 +  /// The class implements the \e Union-Find data structure. 
    3.45 +  /// The union operation uses rank heuristic, while
    3.46 +  /// the find operation uses path compression.
    3.47 +  /// This is a very simple but efficient implementation, providing 
    3.48 +  /// only four methods: join (union), find, insert and size.
    3.49 +  /// For more features see the \ref UnionFindEnum class.
    3.50 +  ///
    3.51 +  /// It is primarily used in Kruskal algorithm for finding minimal
    3.52 +  /// cost spanning tree in a graph.
    3.53 +  /// \sa kruskal()
    3.54 +  ///
    3.55 +  /// \pre You need to add all the elements by the \ref insert()
    3.56 +  /// method.  
    3.57 +  template <typename _ItemIntMap>
    3.58 +  class UnionFind {
    3.59 +  public:
    3.60 +
    3.61 +    typedef _ItemIntMap ItemIntMap;
    3.62 +    typedef typename ItemIntMap::Key Item;
    3.63 +
    3.64 +  private:
    3.65 +    // If the items vector stores negative value for an item then
    3.66 +    // that item is root item and it has -items[it] component size.
    3.67 +    // Else the items[it] contains the index of the parent.
    3.68 +    std::vector<int> items;
    3.69 +    ItemIntMap& index;
    3.70 +
    3.71 +    bool rep(int idx) const {
    3.72 +      return items[idx] < 0;
    3.73 +    }
    3.74 +
    3.75 +    int repIndex(int idx) const {
    3.76 +      int k = idx;
    3.77 +      while (!rep(k)) {
    3.78 +        k = items[k] ;
    3.79 +      }
    3.80 +      while (idx != k) {
    3.81 +        int next = items[idx];
    3.82 +        const_cast<int&>(items[idx]) = k;
    3.83 +        idx = next;
    3.84 +      }
    3.85 +      return k;
    3.86 +    }
    3.87 +
    3.88 +  public:
    3.89 +
    3.90 +    /// \brief Constructor
    3.91 +    ///
    3.92 +    /// Constructor of the UnionFind class. You should give an item to
    3.93 +    /// integer map which will be used from the data structure. If you
    3.94 +    /// modify directly this map that may cause segmentation fault,
    3.95 +    /// invalid data structure, or infinite loop when you use again
    3.96 +    /// the union-find.
    3.97 +    UnionFind(ItemIntMap& m) : index(m) {}
    3.98 +
    3.99 +    /// \brief Returns the index of the element's component.
   3.100 +    ///
   3.101 +    /// The method returns the index of the element's component.
   3.102 +    /// This is an integer between zero and the number of inserted elements.
   3.103 +    ///
   3.104 +    int find(const Item& a) {
   3.105 +      return repIndex(index[a]);
   3.106 +    }
   3.107 +
   3.108 +    /// \brief Clears the union-find data structure
   3.109 +    ///
   3.110 +    /// Erase each item from the data structure.
   3.111 +    void clear() {
   3.112 +      items.clear();
   3.113 +    }
   3.114 +
   3.115 +    /// \brief Inserts a new element into the structure.
   3.116 +    ///
   3.117 +    /// This method inserts a new element into the data structure. 
   3.118 +    ///
   3.119 +    /// The method returns the index of the new component.
   3.120 +    int insert(const Item& a) {
   3.121 +      int n = items.size();
   3.122 +      items.push_back(-1);
   3.123 +      index.set(a,n);
   3.124 +      return n;
   3.125 +    }
   3.126 +
   3.127 +    /// \brief Joining the components of element \e a and element \e b.
   3.128 +    ///
   3.129 +    /// This is the \e union operation of the Union-Find structure. 
   3.130 +    /// Joins the component of element \e a and component of
   3.131 +    /// element \e b. If \e a and \e b are in the same component then
   3.132 +    /// it returns false otherwise it returns true.
   3.133 +    bool join(const Item& a, const Item& b) {
   3.134 +      int ka = repIndex(index[a]);
   3.135 +      int kb = repIndex(index[b]);
   3.136 +
   3.137 +      if ( ka == kb ) 
   3.138 +	return false;
   3.139 +
   3.140 +      if (items[ka] < items[kb]) {
   3.141 +	items[ka] += items[kb];
   3.142 +	items[kb] = ka;
   3.143 +      } else {
   3.144 +	items[kb] += items[ka];
   3.145 +	items[ka] = kb;
   3.146 +      }
   3.147 +      return true;
   3.148 +    }
   3.149 +
   3.150 +    /// \brief Returns the size of the component of element \e a.
   3.151 +    ///
   3.152 +    /// Returns the size of the component of element \e a.
   3.153 +    int size(const Item& a) {
   3.154 +      int k = repIndex(index[a]);
   3.155 +      return - items[k];
   3.156 +    }
   3.157 +
   3.158 +  };
   3.159 +
   3.160 +  /// \ingroup auxdat
   3.161 +  ///
   3.162 +  /// \brief A \e Union-Find data structure implementation which
   3.163 +  /// is able to enumerate the components.
   3.164 +  ///
   3.165 +  /// The class implements a \e Union-Find data structure
   3.166 +  /// which is able to enumerate the components and the items in
   3.167 +  /// a component. If you don't need this feature then perhaps it's
   3.168 +  /// better to use the \ref UnionFind class which is more efficient.
   3.169 +  ///
   3.170 +  /// The union operation uses rank heuristic, while
   3.171 +  /// the find operation uses path compression.
   3.172 +  ///
   3.173 +  /// \pre You need to add all the elements by the \ref insert()
   3.174 +  /// method.
   3.175 +  ///
   3.176 +  template <typename _ItemIntMap>
   3.177 +  class UnionFindEnum {
   3.178 +  public:
   3.179 +    
   3.180 +    typedef _ItemIntMap ItemIntMap;
   3.181 +    typedef typename ItemIntMap::Key Item;
   3.182 +
   3.183 +  private:
   3.184 +    
   3.185 +    ItemIntMap& index;
   3.186 +
   3.187 +    // If the parent stores negative value for an item then that item
   3.188 +    // is root item and it has ~(items[it].parent) component id.  Else
   3.189 +    // the items[it].parent contains the index of the parent.
   3.190 +    //
   3.191 +    // The \c next and \c prev provides the double-linked
   3.192 +    // cyclic list of one component's items.
   3.193 +    struct ItemT {
   3.194 +      int parent;
   3.195 +      Item item;
   3.196 +
   3.197 +      int next, prev;
   3.198 +    };
   3.199 +
   3.200 +    std::vector<ItemT> items;
   3.201 +    int firstFreeItem;
   3.202 +
   3.203 +    struct ClassT {
   3.204 +      int size;
   3.205 +      int firstItem;
   3.206 +      int next, prev;
   3.207 +    };
   3.208 +    
   3.209 +    std::vector<ClassT> classes;
   3.210 +    int firstClass, firstFreeClass;
   3.211 +
   3.212 +    int newClass() {
   3.213 +      if (firstFreeClass == -1) {
   3.214 +	int cdx = classes.size();
   3.215 +	classes.push_back(ClassT());
   3.216 +	return cdx;
   3.217 +      } else {
   3.218 +	int cdx = firstFreeClass;
   3.219 +	firstFreeClass = classes[firstFreeClass].next;
   3.220 +	return cdx;
   3.221 +      }
   3.222 +    }
   3.223 +
   3.224 +    int newItem() {
   3.225 +      if (firstFreeItem == -1) {
   3.226 +	int idx = items.size();
   3.227 +	items.push_back(ItemT());
   3.228 +	return idx;
   3.229 +      } else {
   3.230 +	int idx = firstFreeItem;
   3.231 +	firstFreeItem = items[firstFreeItem].next;
   3.232 +	return idx;
   3.233 +      }
   3.234 +    }
   3.235 +
   3.236 +
   3.237 +    bool rep(int idx) const {
   3.238 +      return items[idx].parent < 0;
   3.239 +    }
   3.240 +
   3.241 +    int repIndex(int idx) const {
   3.242 +      int k = idx;
   3.243 +      while (!rep(k)) {
   3.244 +        k = items[k].parent;
   3.245 +      }
   3.246 +      while (idx != k) {
   3.247 +        int next = items[idx].parent;
   3.248 +        const_cast<int&>(items[idx].parent) = k;
   3.249 +        idx = next;
   3.250 +      }
   3.251 +      return k;
   3.252 +    }
   3.253 +
   3.254 +    int classIndex(int idx) const {
   3.255 +      return ~(items[repIndex(idx)].parent);
   3.256 +    }
   3.257 +
   3.258 +    void singletonItem(int idx) {
   3.259 +      items[idx].next = idx;
   3.260 +      items[idx].prev = idx;
   3.261 +    }
   3.262 +
   3.263 +    void laceItem(int idx, int rdx) {
   3.264 +      items[idx].prev = rdx;
   3.265 +      items[idx].next = items[rdx].next;
   3.266 +      items[items[rdx].next].prev = idx;
   3.267 +      items[rdx].next = idx;
   3.268 +    }
   3.269 +
   3.270 +    void unlaceItem(int idx) {
   3.271 +      items[items[idx].prev].next = items[idx].next;
   3.272 +      items[items[idx].next].prev = items[idx].prev;
   3.273 +      
   3.274 +      items[idx].next = firstFreeItem;
   3.275 +      firstFreeItem = idx;
   3.276 +    }
   3.277 +
   3.278 +    void spliceItems(int ak, int bk) {
   3.279 +      items[items[ak].prev].next = bk;
   3.280 +      items[items[bk].prev].next = ak;
   3.281 +      int tmp = items[ak].prev;
   3.282 +      items[ak].prev = items[bk].prev;
   3.283 +      items[bk].prev = tmp;
   3.284 +        
   3.285 +    }
   3.286 +
   3.287 +    void laceClass(int cls) {
   3.288 +      if (firstClass != -1) {
   3.289 +        classes[firstClass].prev = cls;
   3.290 +      }
   3.291 +      classes[cls].next = firstClass;
   3.292 +      classes[cls].prev = -1;
   3.293 +      firstClass = cls;
   3.294 +    } 
   3.295 +
   3.296 +    void unlaceClass(int cls) {
   3.297 +      if (classes[cls].prev != -1) {
   3.298 +        classes[classes[cls].prev].next = classes[cls].next;
   3.299 +      } else {
   3.300 +        firstClass = classes[cls].next;
   3.301 +      }
   3.302 +      if (classes[cls].next != -1) {
   3.303 +        classes[classes[cls].next].prev = classes[cls].prev;
   3.304 +      }
   3.305 +      
   3.306 +      classes[cls].next = firstFreeClass;
   3.307 +      firstFreeClass = cls;
   3.308 +    } 
   3.309 +
   3.310 +  public:
   3.311 +
   3.312 +    UnionFindEnum(ItemIntMap& _index) 
   3.313 +      : index(_index), items(), firstFreeItem(-1), 
   3.314 +	firstClass(-1), firstFreeClass(-1) {}
   3.315 +    
   3.316 +    /// \brief Inserts the given element into a new component.
   3.317 +    ///
   3.318 +    /// This method creates a new component consisting only of the
   3.319 +    /// given element.
   3.320 +    ///
   3.321 +    int insert(const Item& item) {
   3.322 +      int idx = newItem();
   3.323 +
   3.324 +      index.set(item, idx);
   3.325 +
   3.326 +      singletonItem(idx);
   3.327 +      items[idx].item = item;
   3.328 +
   3.329 +      int cdx = newClass();
   3.330 +
   3.331 +      items[idx].parent = ~cdx;
   3.332 +
   3.333 +      laceClass(cdx);
   3.334 +      classes[cdx].size = 1;
   3.335 +      classes[cdx].firstItem = idx;
   3.336 +
   3.337 +      firstClass = cdx;
   3.338 +      
   3.339 +      return cdx;
   3.340 +    }
   3.341 +
   3.342 +    /// \brief Inserts the given element into the component of the others.
   3.343 +    ///
   3.344 +    /// This methods inserts the element \e a into the component of the
   3.345 +    /// element \e comp. 
   3.346 +    void insert(const Item& item, int cls) {
   3.347 +      int rdx = classes[cls].firstItem;
   3.348 +      int idx = newItem();
   3.349 +
   3.350 +      index.set(item, idx);
   3.351 +
   3.352 +      laceItem(idx, rdx);
   3.353 +
   3.354 +      items[idx].item = item;
   3.355 +      items[idx].parent = rdx;
   3.356 +
   3.357 +      ++classes[~(items[rdx].parent)].size;
   3.358 +    }
   3.359 +
   3.360 +    /// \brief Clears the union-find data structure
   3.361 +    ///
   3.362 +    /// Erase each item from the data structure.
   3.363 +    void clear() {
   3.364 +      items.clear();
   3.365 +      firstClass = -1;
   3.366 +      firstFreeItem = -1;
   3.367 +    }
   3.368 +
   3.369 +    /// \brief Finds the component of the given element.
   3.370 +    ///
   3.371 +    /// The method returns the component id of the given element.
   3.372 +    int find(const Item &item) const {
   3.373 +      return ~(items[repIndex(index[item])].parent);
   3.374 +    }
   3.375 +
   3.376 +    /// \brief Joining the component of element \e a and element \e b.
   3.377 +    ///
   3.378 +    /// This is the \e union operation of the Union-Find structure. 
   3.379 +    /// Joins the component of element \e a and component of
   3.380 +    /// element \e b. If \e a and \e b are in the same component then
   3.381 +    /// returns -1 else returns the remaining class.
   3.382 +    int join(const Item& a, const Item& b) {
   3.383 +
   3.384 +      int ak = repIndex(index[a]);
   3.385 +      int bk = repIndex(index[b]);
   3.386 +
   3.387 +      if (ak == bk) {
   3.388 +	return -1;
   3.389 +      }
   3.390 +
   3.391 +      int acx = ~(items[ak].parent);
   3.392 +      int bcx = ~(items[bk].parent);
   3.393 +
   3.394 +      int rcx;
   3.395 +
   3.396 +      if (classes[acx].size > classes[bcx].size) {
   3.397 +	classes[acx].size += classes[bcx].size;
   3.398 +	items[bk].parent = ak;
   3.399 +        unlaceClass(bcx);
   3.400 +	rcx = acx;
   3.401 +      } else {
   3.402 +	classes[bcx].size += classes[acx].size;
   3.403 +	items[ak].parent = bk;
   3.404 +        unlaceClass(acx);
   3.405 +	rcx = bcx;
   3.406 +      }
   3.407 +      spliceItems(ak, bk);
   3.408 +
   3.409 +      return rcx;
   3.410 +    }
   3.411 +
   3.412 +    /// \brief Returns the size of the class.
   3.413 +    ///
   3.414 +    /// Returns the size of the class.
   3.415 +    int size(int cls) const {
   3.416 +      return classes[cls].size;
   3.417 +    }
   3.418 +
   3.419 +    /// \brief Splits up the component. 
   3.420 +    ///
   3.421 +    /// Splitting the component into singleton components (component
   3.422 +    /// of size one).
   3.423 +    void split(int cls) {
   3.424 +      int fdx = classes[cls].firstItem;
   3.425 +      int idx = items[fdx].next;
   3.426 +      while (idx != fdx) {
   3.427 +        int next = items[idx].next;
   3.428 +
   3.429 +	singletonItem(idx);
   3.430 +
   3.431 +	int cdx = newClass();        
   3.432 +        items[idx].parent = ~cdx;
   3.433 +
   3.434 +	laceClass(cdx);
   3.435 +	classes[cdx].size = 1;
   3.436 +	classes[cdx].firstItem = idx;
   3.437 +        
   3.438 +        idx = next;
   3.439 +      }
   3.440 +
   3.441 +      items[idx].prev = idx;
   3.442 +      items[idx].next = idx;
   3.443 +
   3.444 +      classes[~(items[idx].parent)].size = 1;
   3.445 +      
   3.446 +    }
   3.447 +
   3.448 +    /// \brief Removes the given element from the structure.
   3.449 +    ///
   3.450 +    /// Removes the element from its component and if the component becomes
   3.451 +    /// empty then removes that component from the component list.
   3.452 +    ///
   3.453 +    /// \warning It is an error to remove an element which is not in
   3.454 +    /// the structure.
   3.455 +    /// \warning This running time of this operation is proportional to the
   3.456 +    /// number of the items in this class.
   3.457 +    void erase(const Item& item) {
   3.458 +      int idx = index[item];
   3.459 +      int fdx = items[idx].next;
   3.460 +
   3.461 +      int cdx = classIndex(idx);
   3.462 +      if (idx == fdx) {
   3.463 +	unlaceClass(cdx);
   3.464 +	items[idx].next = firstFreeItem;
   3.465 +	firstFreeItem = idx;
   3.466 +	return;
   3.467 +      } else {
   3.468 +	classes[cdx].firstItem = fdx;
   3.469 +	--classes[cdx].size;
   3.470 +	items[fdx].parent = ~cdx;
   3.471 +
   3.472 +	unlaceItem(idx);
   3.473 +	idx = items[fdx].next;
   3.474 +	while (idx != fdx) {
   3.475 +	  items[idx].parent = fdx;
   3.476 +	  idx = items[idx].next;
   3.477 +	}
   3.478 +          
   3.479 +      }
   3.480 +
   3.481 +    }
   3.482 +
   3.483 +    /// \brief Gives back a representant item of the component.
   3.484 +    ///
   3.485 +    /// Gives back a representant item of the component.
   3.486 +    Item item(int cls) const {
   3.487 +      return items[classes[cls].firstItem].item;
   3.488 +    }
   3.489 +
   3.490 +    /// \brief Removes the component of the given element from the structure.
   3.491 +    ///
   3.492 +    /// Removes the component of the given element from the structure.
   3.493 +    ///
   3.494 +    /// \warning It is an error to give an element which is not in the
   3.495 +    /// structure.
   3.496 +    void eraseClass(int cls) {
   3.497 +      int fdx = classes[cls].firstItem;
   3.498 +      unlaceClass(cls);
   3.499 +      items[items[fdx].prev].next = firstFreeItem;
   3.500 +      firstFreeItem = fdx;
   3.501 +    }
   3.502 +
   3.503 +    /// \brief Lemon style iterator for the representant items.
   3.504 +    ///
   3.505 +    /// ClassIt is a lemon style iterator for the components. It iterates
   3.506 +    /// on the ids of the classes.
   3.507 +    class ClassIt {
   3.508 +    public:
   3.509 +      /// \brief Constructor of the iterator
   3.510 +      ///
   3.511 +      /// Constructor of the iterator
   3.512 +      ClassIt(const UnionFindEnum& ufe) : unionFind(&ufe) {
   3.513 +        cdx = unionFind->firstClass;
   3.514 +      }
   3.515 +
   3.516 +      /// \brief Constructor to get invalid iterator
   3.517 +      ///
   3.518 +      /// Constructor to get invalid iterator
   3.519 +      ClassIt(Invalid) : unionFind(0), cdx(-1) {}
   3.520 +      
   3.521 +      /// \brief Increment operator
   3.522 +      ///
   3.523 +      /// It steps to the next representant item.
   3.524 +      ClassIt& operator++() {
   3.525 +        cdx = unionFind->classes[cdx].next;
   3.526 +        return *this;
   3.527 +      }
   3.528 +      
   3.529 +      /// \brief Conversion operator
   3.530 +      ///
   3.531 +      /// It converts the iterator to the current representant item.
   3.532 +      operator int() const {
   3.533 +        return cdx;
   3.534 +      }
   3.535 +
   3.536 +      /// \brief Equality operator
   3.537 +      ///
   3.538 +      /// Equality operator
   3.539 +      bool operator==(const ClassIt& i) { 
   3.540 +        return i.cdx == cdx;
   3.541 +      }
   3.542 +
   3.543 +      /// \brief Inequality operator
   3.544 +      ///
   3.545 +      /// Inequality operator
   3.546 +      bool operator!=(const ClassIt& i) { 
   3.547 +        return i.cdx != cdx;
   3.548 +      }
   3.549 +      
   3.550 +    private:
   3.551 +      const UnionFindEnum* unionFind;
   3.552 +      int cdx;
   3.553 +    };
   3.554 +
   3.555 +    /// \brief Lemon style iterator for the items of a component.
   3.556 +    ///
   3.557 +    /// ClassIt is a lemon style iterator for the components. It iterates
   3.558 +    /// on the items of a class. By example if you want to iterate on
   3.559 +    /// each items of each classes then you may write the next code.
   3.560 +    ///\code
   3.561 +    /// for (ClassIt cit(ufe); cit != INVALID; ++cit) {
   3.562 +    ///   std::cout << "Class: ";
   3.563 +    ///   for (ItemIt iit(ufe, cit); iit != INVALID; ++iit) {
   3.564 +    ///     std::cout << toString(iit) << ' ' << std::endl;
   3.565 +    ///   }
   3.566 +    ///   std::cout << std::endl;
   3.567 +    /// }
   3.568 +    ///\endcode
   3.569 +    class ItemIt {
   3.570 +    public:
   3.571 +      /// \brief Constructor of the iterator
   3.572 +      ///
   3.573 +      /// Constructor of the iterator. The iterator iterates
   3.574 +      /// on the class of the \c item.
   3.575 +      ItemIt(const UnionFindEnum& ufe, int cls) : unionFind(&ufe) {
   3.576 +        fdx = idx = unionFind->classes[cls].firstItem;
   3.577 +      }
   3.578 +
   3.579 +      /// \brief Constructor to get invalid iterator
   3.580 +      ///
   3.581 +      /// Constructor to get invalid iterator
   3.582 +      ItemIt(Invalid) : unionFind(0), idx(-1) {}
   3.583 +      
   3.584 +      /// \brief Increment operator
   3.585 +      ///
   3.586 +      /// It steps to the next item in the class.
   3.587 +      ItemIt& operator++() {
   3.588 +        idx = unionFind->items[idx].next;
   3.589 +        if (idx == fdx) idx = -1;
   3.590 +        return *this;
   3.591 +      }
   3.592 +      
   3.593 +      /// \brief Conversion operator
   3.594 +      ///
   3.595 +      /// It converts the iterator to the current item.
   3.596 +      operator const Item&() const {
   3.597 +        return unionFind->items[idx].item;
   3.598 +      }
   3.599 +
   3.600 +      /// \brief Equality operator
   3.601 +      ///
   3.602 +      /// Equality operator
   3.603 +      bool operator==(const ItemIt& i) { 
   3.604 +        return i.idx == idx;
   3.605 +      }
   3.606 +
   3.607 +      /// \brief Inequality operator
   3.608 +      ///
   3.609 +      /// Inequality operator
   3.610 +      bool operator!=(const ItemIt& i) { 
   3.611 +        return i.idx != idx;
   3.612 +      }
   3.613 +      
   3.614 +    private:
   3.615 +      const UnionFindEnum* unionFind;
   3.616 +      int idx, fdx;
   3.617 +    };
   3.618 +
   3.619 +  };
   3.620 +
   3.621 +  /// \ingroup auxdat
   3.622 +  ///
   3.623 +  /// \brief A \e Extend-Find data structure implementation which
   3.624 +  /// is able to enumerate the components.
   3.625 +  ///
   3.626 +  /// The class implements an \e Extend-Find data structure which is
   3.627 +  /// able to enumerate the components and the items in a
   3.628 +  /// component. The data structure is a simplification of the
   3.629 +  /// Union-Find structure, and it does not allow to merge two components.
   3.630 +  ///
   3.631 +  /// \pre You need to add all the elements by the \ref insert()
   3.632 +  /// method.
   3.633 +  template <typename _ItemIntMap>
   3.634 +  class ExtendFindEnum {
   3.635 +  public:
   3.636 +    
   3.637 +    typedef _ItemIntMap ItemIntMap;
   3.638 +    typedef typename ItemIntMap::Key Item;
   3.639 +
   3.640 +  private:
   3.641 +    
   3.642 +    ItemIntMap& index;
   3.643 +
   3.644 +    struct ItemT {
   3.645 +      int cls;
   3.646 +      Item item;
   3.647 +      int next, prev;
   3.648 +    };
   3.649 +
   3.650 +    std::vector<ItemT> items;
   3.651 +    int firstFreeItem;
   3.652 +
   3.653 +    struct ClassT {
   3.654 +      int firstItem;
   3.655 +      int next, prev;
   3.656 +    };
   3.657 +
   3.658 +    std::vector<ClassT> classes;
   3.659 +
   3.660 +    int firstClass, firstFreeClass;
   3.661 +
   3.662 +    int newClass() {
   3.663 +      if (firstFreeClass != -1) {
   3.664 +	int cdx = firstFreeClass;
   3.665 +	firstFreeClass = classes[cdx].next;
   3.666 +	return cdx;
   3.667 +      } else {
   3.668 +	classes.push_back(ClassT());
   3.669 +	return classes.size() - 1;
   3.670 +      }
   3.671 +    }
   3.672 +
   3.673 +    int newItem() {
   3.674 +      if (firstFreeItem != -1) {
   3.675 +	int idx = firstFreeItem;
   3.676 +	firstFreeItem = items[idx].next;
   3.677 +	return idx;
   3.678 +      } else {
   3.679 +	items.push_back(ItemT());
   3.680 +	return items.size() - 1;
   3.681 +      }
   3.682 +    }
   3.683 +
   3.684 +  public:
   3.685 +
   3.686 +    /// \brief Constructor
   3.687 +    ExtendFindEnum(ItemIntMap& _index) 
   3.688 +      : index(_index), items(), firstFreeItem(-1), 
   3.689 +	classes(), firstClass(-1), firstFreeClass(-1) {}
   3.690 +    
   3.691 +    /// \brief Inserts the given element into a new component.
   3.692 +    ///
   3.693 +    /// This method creates a new component consisting only of the
   3.694 +    /// given element.
   3.695 +    int insert(const Item& item) {
   3.696 +      int cdx = newClass();
   3.697 +      classes[cdx].prev = -1;
   3.698 +      classes[cdx].next = firstClass;
   3.699 +      if (firstClass != -1) {
   3.700 +	classes[firstClass].prev = cdx;
   3.701 +      }
   3.702 +      firstClass = cdx;
   3.703 +      
   3.704 +      int idx = newItem();
   3.705 +      items[idx].item = item;
   3.706 +      items[idx].cls = cdx;
   3.707 +      items[idx].prev = idx;
   3.708 +      items[idx].next = idx;
   3.709 +
   3.710 +      classes[cdx].firstItem = idx;
   3.711 +
   3.712 +      index.set(item, idx);
   3.713 +      
   3.714 +      return cdx;
   3.715 +    }
   3.716 +
   3.717 +    /// \brief Inserts the given element into the given component.
   3.718 +    ///
   3.719 +    /// This methods inserts the element \e item a into the \e cls class.
   3.720 +    void insert(const Item& item, int cls) {
   3.721 +      int idx = newItem();
   3.722 +      int rdx = classes[cls].firstItem;
   3.723 +      items[idx].item = item;
   3.724 +      items[idx].cls = cls;
   3.725 +
   3.726 +      items[idx].prev = rdx;
   3.727 +      items[idx].next = items[rdx].next;
   3.728 +      items[items[rdx].next].prev = idx;
   3.729 +      items[rdx].next = idx;
   3.730 +
   3.731 +      index.set(item, idx);
   3.732 +    }
   3.733 +
   3.734 +    /// \brief Clears the union-find data structure
   3.735 +    ///
   3.736 +    /// Erase each item from the data structure.
   3.737 +    void clear() {
   3.738 +      items.clear();
   3.739 +      classes.clear;
   3.740 +      firstClass = firstFreeClass = firstFreeItem = -1;
   3.741 +    }
   3.742 +
   3.743 +    /// \brief Gives back the class of the \e item.
   3.744 +    ///
   3.745 +    /// Gives back the class of the \e item.
   3.746 +    int find(const Item &item) const {
   3.747 +      return items[index[item]].cls;
   3.748 +    }
   3.749 +
   3.750 +    /// \brief Gives back a representant item of the component.
   3.751 +    ///
   3.752 +    /// Gives back a representant item of the component.
   3.753 +    Item item(int cls) const {
   3.754 +      return items[classes[cls].firstItem].item;
   3.755 +    }
   3.756 +    
   3.757 +    /// \brief Removes the given element from the structure.
   3.758 +    ///
   3.759 +    /// Removes the element from its component and if the component becomes
   3.760 +    /// empty then removes that component from the component list.
   3.761 +    ///
   3.762 +    /// \warning It is an error to remove an element which is not in
   3.763 +    /// the structure.
   3.764 +    void erase(const Item &item) {
   3.765 +      int idx = index[item];
   3.766 +      int cdx = items[idx].cls;
   3.767 +      
   3.768 +      if (idx == items[idx].next) {
   3.769 +	if (classes[cdx].prev != -1) {
   3.770 +	  classes[classes[cdx].prev].next = classes[cdx].next; 
   3.771 +	} else {
   3.772 +	  firstClass = classes[cdx].next;
   3.773 +	}
   3.774 +	if (classes[cdx].next != -1) {
   3.775 +	  classes[classes[cdx].next].prev = classes[cdx].prev; 
   3.776 +	}
   3.777 +	classes[cdx].next = firstFreeClass;
   3.778 +	firstFreeClass = cdx;
   3.779 +      } else {
   3.780 +	classes[cdx].firstItem = items[idx].next;
   3.781 +	items[items[idx].next].prev = items[idx].prev;
   3.782 +	items[items[idx].prev].next = items[idx].next;
   3.783 +      }
   3.784 +      items[idx].next = firstFreeItem;
   3.785 +      firstFreeItem = idx;
   3.786 +	
   3.787 +    }    
   3.788 +
   3.789 +    
   3.790 +    /// \brief Removes the component of the given element from the structure.
   3.791 +    ///
   3.792 +    /// Removes the component of the given element from the structure.
   3.793 +    ///
   3.794 +    /// \warning It is an error to give an element which is not in the
   3.795 +    /// structure.
   3.796 +    void eraseClass(int cdx) {
   3.797 +      int idx = classes[cdx].firstItem;
   3.798 +      items[items[idx].prev].next = firstFreeItem;
   3.799 +      firstFreeItem = idx;
   3.800 +
   3.801 +      if (classes[cdx].prev != -1) {
   3.802 +	classes[classes[cdx].prev].next = classes[cdx].next; 
   3.803 +      } else {
   3.804 +	firstClass = classes[cdx].next;
   3.805 +      }
   3.806 +      if (classes[cdx].next != -1) {
   3.807 +	classes[classes[cdx].next].prev = classes[cdx].prev; 
   3.808 +      }
   3.809 +      classes[cdx].next = firstFreeClass;
   3.810 +      firstFreeClass = cdx;
   3.811 +    }
   3.812 +
   3.813 +    /// \brief Lemon style iterator for the classes.
   3.814 +    ///
   3.815 +    /// ClassIt is a lemon style iterator for the components. It iterates
   3.816 +    /// on the ids of classes.
   3.817 +    class ClassIt {
   3.818 +    public:
   3.819 +      /// \brief Constructor of the iterator
   3.820 +      ///
   3.821 +      /// Constructor of the iterator
   3.822 +      ClassIt(const ExtendFindEnum& ufe) : extendFind(&ufe) {
   3.823 +        cdx = extendFind->firstClass;
   3.824 +      }
   3.825 +
   3.826 +      /// \brief Constructor to get invalid iterator
   3.827 +      ///
   3.828 +      /// Constructor to get invalid iterator
   3.829 +      ClassIt(Invalid) : extendFind(0), cdx(-1) {}
   3.830 +      
   3.831 +      /// \brief Increment operator
   3.832 +      ///
   3.833 +      /// It steps to the next representant item.
   3.834 +      ClassIt& operator++() {
   3.835 +        cdx = extendFind->classes[cdx].next;
   3.836 +        return *this;
   3.837 +      }
   3.838 +      
   3.839 +      /// \brief Conversion operator
   3.840 +      ///
   3.841 +      /// It converts the iterator to the current class id.
   3.842 +      operator int() const {
   3.843 +        return cdx;
   3.844 +      }
   3.845 +
   3.846 +      /// \brief Equality operator
   3.847 +      ///
   3.848 +      /// Equality operator
   3.849 +      bool operator==(const ClassIt& i) { 
   3.850 +        return i.cdx == cdx;
   3.851 +      }
   3.852 +
   3.853 +      /// \brief Inequality operator
   3.854 +      ///
   3.855 +      /// Inequality operator
   3.856 +      bool operator!=(const ClassIt& i) { 
   3.857 +        return i.cdx != cdx;
   3.858 +      }
   3.859 +      
   3.860 +    private:
   3.861 +      const ExtendFindEnum* extendFind;
   3.862 +      int cdx;
   3.863 +    };
   3.864 +
   3.865 +    /// \brief Lemon style iterator for the items of a component.
   3.866 +    ///
   3.867 +    /// ClassIt is a lemon style iterator for the components. It iterates
   3.868 +    /// on the items of a class. By example if you want to iterate on
   3.869 +    /// each items of each classes then you may write the next code.
   3.870 +    ///\code
   3.871 +    /// for (ClassIt cit(ufe); cit != INVALID; ++cit) {
   3.872 +    ///   std::cout << "Class: ";
   3.873 +    ///   for (ItemIt iit(ufe, cit); iit != INVALID; ++iit) {
   3.874 +    ///     std::cout << toString(iit) << ' ' << std::endl;
   3.875 +    ///   }
   3.876 +    ///   std::cout << std::endl;
   3.877 +    /// }
   3.878 +    ///\endcode
   3.879 +    class ItemIt {
   3.880 +    public:
   3.881 +      /// \brief Constructor of the iterator
   3.882 +      ///
   3.883 +      /// Constructor of the iterator. The iterator iterates
   3.884 +      /// on the class of the \c item.
   3.885 +      ItemIt(const ExtendFindEnum& ufe, int cls) : extendFind(&ufe) {
   3.886 +        fdx = idx = extendFind->classes[cls].firstItem;
   3.887 +      }
   3.888 +
   3.889 +      /// \brief Constructor to get invalid iterator
   3.890 +      ///
   3.891 +      /// Constructor to get invalid iterator
   3.892 +      ItemIt(Invalid) : extendFind(0), idx(-1) {}
   3.893 +      
   3.894 +      /// \brief Increment operator
   3.895 +      ///
   3.896 +      /// It steps to the next item in the class.
   3.897 +      ItemIt& operator++() {
   3.898 +        idx = extendFind->items[idx].next;
   3.899 +	if (fdx == idx) idx = -1;
   3.900 +        return *this;
   3.901 +      }
   3.902 +      
   3.903 +      /// \brief Conversion operator
   3.904 +      ///
   3.905 +      /// It converts the iterator to the current item.
   3.906 +      operator const Item&() const {
   3.907 +        return extendFind->items[idx].item;
   3.908 +      }
   3.909 +
   3.910 +      /// \brief Equality operator
   3.911 +      ///
   3.912 +      /// Equality operator
   3.913 +      bool operator==(const ItemIt& i) { 
   3.914 +        return i.idx == idx;
   3.915 +      }
   3.916 +
   3.917 +      /// \brief Inequality operator
   3.918 +      ///
   3.919 +      /// Inequality operator
   3.920 +      bool operator!=(const ItemIt& i) { 
   3.921 +        return i.idx != idx;
   3.922 +      }
   3.923 +      
   3.924 +    private:
   3.925 +      const ExtendFindEnum* extendFind;
   3.926 +      int idx, fdx;
   3.927 +    };
   3.928 +
   3.929 +  };
   3.930 +
   3.931 +  /// \ingroup auxdat
   3.932 +  ///
   3.933 +  /// \brief A \e Union-Find data structure implementation which
   3.934 +  /// is able to store a priority for each item and retrieve the minimum of
   3.935 +  /// each class.
   3.936 +  ///
   3.937 +  /// A \e Union-Find data structure implementation which is able to
   3.938 +  /// store a priority for each item and retrieve the minimum of each
   3.939 +  /// class. In addition, it supports the joining and splitting the
   3.940 +  /// components. If you don't need this feature then you makes
   3.941 +  /// better to use the \ref UnionFind class which is more efficient.
   3.942 +  ///
   3.943 +  /// The union-find data strcuture based on a (2, 16)-tree with a
   3.944 +  /// tournament minimum selection on the internal nodes. The insert
   3.945 +  /// operation takes O(1), the find, set, decrease and increase takes
   3.946 +  /// O(log(n)), where n is the number of nodes in the current
   3.947 +  /// component.  The complexity of join and split is O(log(n)*k),
   3.948 +  /// where n is the sum of the number of the nodes and k is the
   3.949 +  /// number of joined components or the number of the components
   3.950 +  /// after the split.
   3.951 +  ///
   3.952 +  /// \pre You need to add all the elements by the \ref insert()
   3.953 +  /// method.
   3.954 +  ///
   3.955 +  template <typename _Value, typename _ItemIntMap, 
   3.956 +            typename _Comp = std::less<_Value> >
   3.957 +  class HeapUnionFind {
   3.958 +  public:
   3.959 +    
   3.960 +    typedef _Value Value;
   3.961 +    typedef typename _ItemIntMap::Key Item;
   3.962 +
   3.963 +    typedef _ItemIntMap ItemIntMap;
   3.964 +
   3.965 +    typedef _Comp Comp;
   3.966 +
   3.967 +  private:
   3.968 +
   3.969 +    static const int cmax = 16;
   3.970 +
   3.971 +    ItemIntMap& index;
   3.972 +
   3.973 +    struct ClassNode {
   3.974 +      int parent;
   3.975 +      int depth;
   3.976 +
   3.977 +      int left, right;
   3.978 +      int next, prev;
   3.979 +    };
   3.980 +
   3.981 +    int first_class;
   3.982 +    int first_free_class;
   3.983 +    std::vector<ClassNode> classes;
   3.984 +
   3.985 +    int newClass() {
   3.986 +      if (first_free_class < 0) {
   3.987 +        int id = classes.size();
   3.988 +        classes.push_back(ClassNode());
   3.989 +        return id;
   3.990 +      } else {
   3.991 +        int id = first_free_class;
   3.992 +        first_free_class = classes[id].next;
   3.993 +        return id;
   3.994 +      }
   3.995 +    }
   3.996 +
   3.997 +    void deleteClass(int id) {
   3.998 +      classes[id].next = first_free_class;
   3.999 +      first_free_class = id;
  3.1000 +    }
  3.1001 +
  3.1002 +    struct ItemNode {
  3.1003 +      int parent;
  3.1004 +      Item item;
  3.1005 +      Value prio;
  3.1006 +      int next, prev;
  3.1007 +      int left, right;
  3.1008 +      int size;
  3.1009 +    };
  3.1010 +
  3.1011 +    int first_free_node;
  3.1012 +    std::vector<ItemNode> nodes;
  3.1013 +
  3.1014 +    int newNode() {
  3.1015 +      if (first_free_node < 0) {
  3.1016 +        int id = nodes.size();
  3.1017 +        nodes.push_back(ItemNode());
  3.1018 +        return id;
  3.1019 +      } else {
  3.1020 +        int id = first_free_node;
  3.1021 +        first_free_node = nodes[id].next;
  3.1022 +        return id;
  3.1023 +      }
  3.1024 +    }
  3.1025 +
  3.1026 +    void deleteNode(int id) {
  3.1027 +      nodes[id].next = first_free_node;
  3.1028 +      first_free_node = id;
  3.1029 +    }
  3.1030 +
  3.1031 +    Comp comp;
  3.1032 +
  3.1033 +    int findClass(int id) const {
  3.1034 +      int kd = id;
  3.1035 +      while (kd >= 0) {
  3.1036 +        kd = nodes[kd].parent;
  3.1037 +      }
  3.1038 +      return ~kd;
  3.1039 +    }
  3.1040 +
  3.1041 +    int leftNode(int id) const {
  3.1042 +      int kd = ~(classes[id].parent);
  3.1043 +      for (int i = 0; i < classes[id].depth; ++i) {
  3.1044 +        kd = nodes[kd].left;
  3.1045 +      }
  3.1046 +      return kd;
  3.1047 +    }
  3.1048 +
  3.1049 +    int nextNode(int id) const {
  3.1050 +      int depth = 0;
  3.1051 +      while (id >= 0 && nodes[id].next == -1) {
  3.1052 +        id = nodes[id].parent;
  3.1053 +        ++depth;
  3.1054 +      }
  3.1055 +      if (id < 0) {
  3.1056 +        return -1;
  3.1057 +      }
  3.1058 +      id = nodes[id].next;
  3.1059 +      while (depth--) {
  3.1060 +        id = nodes[id].left;      
  3.1061 +      }
  3.1062 +      return id;
  3.1063 +    }
  3.1064 +
  3.1065 +
  3.1066 +    void setPrio(int id) {
  3.1067 +      int jd = nodes[id].left;
  3.1068 +      nodes[id].prio = nodes[jd].prio;
  3.1069 +      nodes[id].item = nodes[jd].item;
  3.1070 +      jd = nodes[jd].next;
  3.1071 +      while (jd != -1) {
  3.1072 +        if (comp(nodes[jd].prio, nodes[id].prio)) {
  3.1073 +          nodes[id].prio = nodes[jd].prio;
  3.1074 +          nodes[id].item = nodes[jd].item;
  3.1075 +        }
  3.1076 +        jd = nodes[jd].next;
  3.1077 +      }
  3.1078 +    }
  3.1079 +
  3.1080 +    void push(int id, int jd) {
  3.1081 +      nodes[id].size = 1;
  3.1082 +      nodes[id].left = nodes[id].right = jd;
  3.1083 +      nodes[jd].next = nodes[jd].prev = -1;
  3.1084 +      nodes[jd].parent = id;
  3.1085 +    }
  3.1086 +
  3.1087 +    void pushAfter(int id, int jd) {
  3.1088 +      int kd = nodes[id].parent;
  3.1089 +      if (nodes[id].next != -1) {
  3.1090 +        nodes[nodes[id].next].prev = jd;
  3.1091 +        if (kd >= 0) {
  3.1092 +          nodes[kd].size += 1;
  3.1093 +        }
  3.1094 +      } else {
  3.1095 +        if (kd >= 0) {
  3.1096 +          nodes[kd].right = jd;
  3.1097 +          nodes[kd].size += 1;
  3.1098 +        }
  3.1099 +      }
  3.1100 +      nodes[jd].next = nodes[id].next;
  3.1101 +      nodes[jd].prev = id;
  3.1102 +      nodes[id].next = jd;
  3.1103 +      nodes[jd].parent = kd;
  3.1104 +    }
  3.1105 +
  3.1106 +    void pushRight(int id, int jd) {
  3.1107 +      nodes[id].size += 1;
  3.1108 +      nodes[jd].prev = nodes[id].right;
  3.1109 +      nodes[jd].next = -1;
  3.1110 +      nodes[nodes[id].right].next = jd;
  3.1111 +      nodes[id].right = jd;
  3.1112 +      nodes[jd].parent = id;
  3.1113 +    }
  3.1114 +
  3.1115 +    void popRight(int id) {
  3.1116 +      nodes[id].size -= 1;
  3.1117 +      int jd = nodes[id].right;
  3.1118 +      nodes[nodes[jd].prev].next = -1;
  3.1119 +      nodes[id].right = nodes[jd].prev;
  3.1120 +    }
  3.1121 +
  3.1122 +    void splice(int id, int jd) {
  3.1123 +      nodes[id].size += nodes[jd].size;
  3.1124 +      nodes[nodes[id].right].next = nodes[jd].left;
  3.1125 +      nodes[nodes[jd].left].prev = nodes[id].right;
  3.1126 +      int kd = nodes[jd].left;
  3.1127 +      while (kd != -1) {
  3.1128 +        nodes[kd].parent = id;
  3.1129 +        kd = nodes[kd].next;
  3.1130 +      }
  3.1131 +      nodes[id].right = nodes[jd].right;
  3.1132 +    }
  3.1133 +
  3.1134 +    void split(int id, int jd) {
  3.1135 +      int kd = nodes[id].parent;
  3.1136 +      nodes[kd].right = nodes[id].prev;
  3.1137 +      nodes[nodes[id].prev].next = -1;
  3.1138 +      
  3.1139 +      nodes[jd].left = id;
  3.1140 +      nodes[id].prev = -1;
  3.1141 +      int num = 0;
  3.1142 +      while (id != -1) {
  3.1143 +        nodes[id].parent = jd;
  3.1144 +        nodes[jd].right = id;
  3.1145 +        id = nodes[id].next;
  3.1146 +        ++num;
  3.1147 +      }      
  3.1148 +      nodes[kd].size -= num;
  3.1149 +      nodes[jd].size = num;
  3.1150 +    }
  3.1151 +
  3.1152 +    void pushLeft(int id, int jd) {
  3.1153 +      nodes[id].size += 1;
  3.1154 +      nodes[jd].next = nodes[id].left;
  3.1155 +      nodes[jd].prev = -1;
  3.1156 +      nodes[nodes[id].left].prev = jd;
  3.1157 +      nodes[id].left = jd;
  3.1158 +      nodes[jd].parent = id;
  3.1159 +    }
  3.1160 +
  3.1161 +    void popLeft(int id) {
  3.1162 +      nodes[id].size -= 1;
  3.1163 +      int jd = nodes[id].left;
  3.1164 +      nodes[nodes[jd].next].prev = -1;
  3.1165 +      nodes[id].left = nodes[jd].next;
  3.1166 +    }
  3.1167 +
  3.1168 +    void repairLeft(int id) {
  3.1169 +      int jd = ~(classes[id].parent);
  3.1170 +      while (nodes[jd].left != -1) {
  3.1171 +	int kd = nodes[jd].left;
  3.1172 +	if (nodes[jd].size == 1) {
  3.1173 +	  if (nodes[jd].parent < 0) {
  3.1174 +	    classes[id].parent = ~kd;
  3.1175 +	    classes[id].depth -= 1;
  3.1176 +	    nodes[kd].parent = ~id;
  3.1177 +	    deleteNode(jd);
  3.1178 +	    jd = kd;
  3.1179 +	  } else {
  3.1180 +	    int pd = nodes[jd].parent;
  3.1181 +	    if (nodes[nodes[jd].next].size < cmax) {
  3.1182 +	      pushLeft(nodes[jd].next, nodes[jd].left);
  3.1183 +	      if (less(nodes[jd].left, nodes[jd].next)) {
  3.1184 +		nodes[nodes[jd].next].prio = nodes[nodes[jd].left].prio;
  3.1185 +		nodes[nodes[jd].next].item = nodes[nodes[jd].left].item;
  3.1186 +	      } 
  3.1187 +	      popLeft(pd);
  3.1188 +	      deleteNode(jd);
  3.1189 +	      jd = pd;
  3.1190 +	    } else {
  3.1191 +	      int ld = nodes[nodes[jd].next].left;
  3.1192 +	      popLeft(nodes[jd].next);
  3.1193 +	      pushRight(jd, ld);
  3.1194 +	      if (less(ld, nodes[jd].left)) {
  3.1195 +		nodes[jd].item = nodes[ld].item;
  3.1196 +		nodes[jd].prio = nodes[jd].prio;
  3.1197 +	      }
  3.1198 +	      if (nodes[nodes[jd].next].item == nodes[ld].item) {
  3.1199 +		setPrio(nodes[jd].next);
  3.1200 +	      }
  3.1201 +	      jd = nodes[jd].left;
  3.1202 +	    }
  3.1203 +	  }
  3.1204 +	} else {
  3.1205 +	  jd = nodes[jd].left;
  3.1206 +	}
  3.1207 +      }
  3.1208 +    }    
  3.1209 +
  3.1210 +    void repairRight(int id) {
  3.1211 +      int jd = ~(classes[id].parent);
  3.1212 +      while (nodes[jd].right != -1) {
  3.1213 +	int kd = nodes[jd].right;
  3.1214 +	if (nodes[jd].size == 1) {
  3.1215 +	  if (nodes[jd].parent < 0) {
  3.1216 +	    classes[id].parent = ~kd;
  3.1217 +	    classes[id].depth -= 1;
  3.1218 +	    nodes[kd].parent = ~id;
  3.1219 +	    deleteNode(jd);
  3.1220 +	    jd = kd;
  3.1221 +	  } else {
  3.1222 +	    int pd = nodes[jd].parent;
  3.1223 +	    if (nodes[nodes[jd].prev].size < cmax) {
  3.1224 +	      pushRight(nodes[jd].prev, nodes[jd].right);
  3.1225 +	      if (less(nodes[jd].right, nodes[jd].prev)) {
  3.1226 +		nodes[nodes[jd].prev].prio = nodes[nodes[jd].right].prio;
  3.1227 +		nodes[nodes[jd].prev].item = nodes[nodes[jd].right].item;
  3.1228 +	      } 
  3.1229 +	      popRight(pd);
  3.1230 +	      deleteNode(jd);
  3.1231 +	      jd = pd;
  3.1232 +	    } else {
  3.1233 +	      int ld = nodes[nodes[jd].prev].right;
  3.1234 +	      popRight(nodes[jd].prev);
  3.1235 +	      pushLeft(jd, ld);
  3.1236 +	      if (less(ld, nodes[jd].right)) {
  3.1237 +		nodes[jd].item = nodes[ld].item;
  3.1238 +		nodes[jd].prio = nodes[jd].prio;
  3.1239 +	      }
  3.1240 +	      if (nodes[nodes[jd].prev].item == nodes[ld].item) {
  3.1241 +		setPrio(nodes[jd].prev);
  3.1242 +	      }
  3.1243 +	      jd = nodes[jd].right;
  3.1244 +	    }
  3.1245 +	  }
  3.1246 +	} else {
  3.1247 +	  jd = nodes[jd].right;
  3.1248 +	}
  3.1249 +      }
  3.1250 +    }
  3.1251 +
  3.1252 +
  3.1253 +    bool less(int id, int jd) const {
  3.1254 +      return comp(nodes[id].prio, nodes[jd].prio);
  3.1255 +    }
  3.1256 +
  3.1257 +    bool equal(int id, int jd) const {
  3.1258 +      return !less(id, jd) && !less(jd, id);
  3.1259 +    }
  3.1260 +
  3.1261 +
  3.1262 +  public:
  3.1263 +
  3.1264 +    /// \brief Returns true when the given class is alive.
  3.1265 +    ///
  3.1266 +    /// Returns true when the given class is alive, ie. the class is
  3.1267 +    /// not nested into other class.
  3.1268 +    bool alive(int cls) const {
  3.1269 +      return classes[cls].parent < 0;
  3.1270 +    }
  3.1271 +
  3.1272 +    /// \brief Returns true when the given class is trivial.
  3.1273 +    ///
  3.1274 +    /// Returns true when the given class is trivial, ie. the class
  3.1275 +    /// contains just one item directly.
  3.1276 +    bool trivial(int cls) const {
  3.1277 +      return classes[cls].left == -1;
  3.1278 +    }
  3.1279 +
  3.1280 +    /// \brief Constructs the union-find.
  3.1281 +    ///
  3.1282 +    /// Constructs the union-find.  
  3.1283 +    /// \brief _index The index map of the union-find. The data
  3.1284 +    /// structure uses internally for store references.
  3.1285 +    HeapUnionFind(ItemIntMap& _index) 
  3.1286 +      : index(_index), first_class(-1), 
  3.1287 +	first_free_class(-1), first_free_node(-1) {}
  3.1288 +
  3.1289 +    /// \brief Insert a new node into a new component.
  3.1290 +    ///
  3.1291 +    /// Insert a new node into a new component.
  3.1292 +    /// \param item The item of the new node.
  3.1293 +    /// \param prio The priority of the new node.
  3.1294 +    /// \return The class id of the one-item-heap.
  3.1295 +    int insert(const Item& item, const Value& prio) {
  3.1296 +      int id = newNode();
  3.1297 +      nodes[id].item = item;
  3.1298 +      nodes[id].prio = prio;
  3.1299 +      nodes[id].size = 0;
  3.1300 +
  3.1301 +      nodes[id].prev = -1;
  3.1302 +      nodes[id].next = -1;
  3.1303 +
  3.1304 +      nodes[id].left = -1;
  3.1305 +      nodes[id].right = -1;
  3.1306 +
  3.1307 +      nodes[id].item = item;
  3.1308 +      index[item] = id;
  3.1309 +      
  3.1310 +      int class_id = newClass();
  3.1311 +      classes[class_id].parent = ~id;
  3.1312 +      classes[class_id].depth = 0;
  3.1313 +
  3.1314 +      classes[class_id].left = -1;
  3.1315 +      classes[class_id].right = -1;
  3.1316 +      
  3.1317 +      if (first_class != -1) {
  3.1318 +        classes[first_class].prev = class_id;
  3.1319 +      }
  3.1320 +      classes[class_id].next = first_class;
  3.1321 +      classes[class_id].prev = -1;
  3.1322 +      first_class = class_id;
  3.1323 +
  3.1324 +      nodes[id].parent = ~class_id;
  3.1325 +      
  3.1326 +      return class_id;
  3.1327 +    }
  3.1328 +
  3.1329 +    /// \brief The class of the item.
  3.1330 +    ///
  3.1331 +    /// \return The alive class id of the item, which is not nested into
  3.1332 +    /// other classes.
  3.1333 +    ///
  3.1334 +    /// The time complexity is O(log(n)).
  3.1335 +    int find(const Item& item) const {
  3.1336 +      return findClass(index[item]);
  3.1337 +    }
  3.1338 +    
  3.1339 +    /// \brief Joins the classes.
  3.1340 +    ///
  3.1341 +    /// The current function joins the given classes. The parameter is
  3.1342 +    /// an STL range which should be contains valid class ids. The
  3.1343 +    /// time complexity is O(log(n)*k) where n is the overall number
  3.1344 +    /// of the joined nodes and k is the number of classes.
  3.1345 +    /// \return The class of the joined classes.
  3.1346 +    /// \pre The range should contain at least two class ids.
  3.1347 +    template <typename Iterator>
  3.1348 +    int join(Iterator begin, Iterator end) {
  3.1349 +      std::vector<int> cs;
  3.1350 +      for (Iterator it = begin; it != end; ++it) {
  3.1351 +        cs.push_back(*it);
  3.1352 +      }
  3.1353 +
  3.1354 +      int class_id = newClass();
  3.1355 +      { // creation union-find
  3.1356 +
  3.1357 +        if (first_class != -1) {
  3.1358 +          classes[first_class].prev = class_id;
  3.1359 +        }
  3.1360 +        classes[class_id].next = first_class;
  3.1361 +        classes[class_id].prev = -1;
  3.1362 +        first_class = class_id;
  3.1363 +
  3.1364 +        classes[class_id].depth = classes[cs[0]].depth;
  3.1365 +        classes[class_id].parent = classes[cs[0]].parent;
  3.1366 +        nodes[~(classes[class_id].parent)].parent = ~class_id;
  3.1367 +
  3.1368 +        int l = cs[0];
  3.1369 +
  3.1370 +        classes[class_id].left = l;
  3.1371 +        classes[class_id].right = l;
  3.1372 +
  3.1373 +        if (classes[l].next != -1) {
  3.1374 +          classes[classes[l].next].prev = classes[l].prev;
  3.1375 +        }
  3.1376 +        classes[classes[l].prev].next = classes[l].next;
  3.1377 +        
  3.1378 +        classes[l].prev = -1;
  3.1379 +        classes[l].next = -1;
  3.1380 +
  3.1381 +        classes[l].depth = leftNode(l);
  3.1382 +        classes[l].parent = class_id;
  3.1383 +        
  3.1384 +      }
  3.1385 +
  3.1386 +      { // merging of heap
  3.1387 +        int l = class_id;
  3.1388 +        for (int ci = 1; ci < int(cs.size()); ++ci) {
  3.1389 +          int r = cs[ci];
  3.1390 +          int rln = leftNode(r);
  3.1391 +          if (classes[l].depth > classes[r].depth) {
  3.1392 +            int id = ~(classes[l].parent);
  3.1393 +            for (int i = classes[r].depth + 1; i < classes[l].depth; ++i) {
  3.1394 +              id = nodes[id].right;
  3.1395 +            }
  3.1396 +            while (id >= 0 && nodes[id].size == cmax) {
  3.1397 +              int new_id = newNode();
  3.1398 +              int right_id = nodes[id].right;
  3.1399 +
  3.1400 +              popRight(id);
  3.1401 +              if (nodes[id].item == nodes[right_id].item) {
  3.1402 +                setPrio(id);
  3.1403 +              }
  3.1404 +              push(new_id, right_id);
  3.1405 +              pushRight(new_id, ~(classes[r].parent));
  3.1406 +              setPrio(new_id);
  3.1407 +
  3.1408 +              id = nodes[id].parent;
  3.1409 +              classes[r].parent = ~new_id;
  3.1410 +            }
  3.1411 +            if (id < 0) {
  3.1412 +              int new_parent = newNode();
  3.1413 +              nodes[new_parent].next = -1;
  3.1414 +              nodes[new_parent].prev = -1;
  3.1415 +              nodes[new_parent].parent = ~l;
  3.1416 +
  3.1417 +              push(new_parent, ~(classes[l].parent));
  3.1418 +              pushRight(new_parent, ~(classes[r].parent));
  3.1419 +              setPrio(new_parent);
  3.1420 +
  3.1421 +              classes[l].parent = ~new_parent;
  3.1422 +              classes[l].depth += 1;
  3.1423 +            } else {
  3.1424 +              pushRight(id, ~(classes[r].parent));
  3.1425 +              while (id >= 0 && less(~(classes[r].parent), id)) {
  3.1426 +                nodes[id].prio = nodes[~(classes[r].parent)].prio;
  3.1427 +                nodes[id].item = nodes[~(classes[r].parent)].item;
  3.1428 +                id = nodes[id].parent;
  3.1429 +              }
  3.1430 +            }
  3.1431 +          } else if (classes[r].depth > classes[l].depth) {
  3.1432 +            int id = ~(classes[r].parent);
  3.1433 +            for (int i = classes[l].depth + 1; i < classes[r].depth; ++i) {
  3.1434 +              id = nodes[id].left;
  3.1435 +            }
  3.1436 +            while (id >= 0 && nodes[id].size == cmax) {
  3.1437 +              int new_id = newNode();
  3.1438 +              int left_id = nodes[id].left;
  3.1439 +
  3.1440 +              popLeft(id);
  3.1441 +              if (nodes[id].prio == nodes[left_id].prio) {
  3.1442 +                setPrio(id);
  3.1443 +              }
  3.1444 +              push(new_id, left_id);
  3.1445 +              pushLeft(new_id, ~(classes[l].parent));
  3.1446 +              setPrio(new_id);
  3.1447 +
  3.1448 +              id = nodes[id].parent;
  3.1449 +              classes[l].parent = ~new_id;
  3.1450 +
  3.1451 +            }
  3.1452 +            if (id < 0) {
  3.1453 +              int new_parent = newNode();
  3.1454 +              nodes[new_parent].next = -1;
  3.1455 +              nodes[new_parent].prev = -1;
  3.1456 +              nodes[new_parent].parent = ~l;
  3.1457 +
  3.1458 +              push(new_parent, ~(classes[r].parent));
  3.1459 +              pushLeft(new_parent, ~(classes[l].parent));
  3.1460 +              setPrio(new_parent);
  3.1461 +              
  3.1462 +              classes[r].parent = ~new_parent;
  3.1463 +              classes[r].depth += 1;
  3.1464 +            } else {
  3.1465 +              pushLeft(id, ~(classes[l].parent));
  3.1466 +              while (id >= 0 && less(~(classes[l].parent), id)) {
  3.1467 +                nodes[id].prio = nodes[~(classes[l].parent)].prio;
  3.1468 +                nodes[id].item = nodes[~(classes[l].parent)].item;
  3.1469 +                id = nodes[id].parent;
  3.1470 +              }
  3.1471 +            }
  3.1472 +            nodes[~(classes[r].parent)].parent = ~l;
  3.1473 +            classes[l].parent = classes[r].parent;
  3.1474 +            classes[l].depth = classes[r].depth;
  3.1475 +          } else {
  3.1476 +            if (classes[l].depth != 0 && 
  3.1477 +                nodes[~(classes[l].parent)].size + 
  3.1478 +                nodes[~(classes[r].parent)].size <= cmax) {
  3.1479 +              splice(~(classes[l].parent), ~(classes[r].parent));
  3.1480 +              deleteNode(~(classes[r].parent));
  3.1481 +              if (less(~(classes[r].parent), ~(classes[l].parent))) {
  3.1482 +                nodes[~(classes[l].parent)].prio = 
  3.1483 +                  nodes[~(classes[r].parent)].prio;
  3.1484 +                nodes[~(classes[l].parent)].item = 
  3.1485 +                  nodes[~(classes[r].parent)].item;
  3.1486 +              }
  3.1487 +            } else {
  3.1488 +              int new_parent = newNode();
  3.1489 +              nodes[new_parent].next = nodes[new_parent].prev = -1;
  3.1490 +              push(new_parent, ~(classes[l].parent));
  3.1491 +              pushRight(new_parent, ~(classes[r].parent));
  3.1492 +              setPrio(new_parent);
  3.1493 +            
  3.1494 +              classes[l].parent = ~new_parent;
  3.1495 +              classes[l].depth += 1;
  3.1496 +              nodes[new_parent].parent = ~l;
  3.1497 +            }
  3.1498 +          }
  3.1499 +          if (classes[r].next != -1) {
  3.1500 +            classes[classes[r].next].prev = classes[r].prev;
  3.1501 +          }
  3.1502 +          classes[classes[r].prev].next = classes[r].next;
  3.1503 +
  3.1504 +          classes[r].prev = classes[l].right;
  3.1505 +          classes[classes[l].right].next = r;
  3.1506 +          classes[l].right = r;
  3.1507 +          classes[r].parent = l;
  3.1508 +
  3.1509 +          classes[r].next = -1;
  3.1510 +          classes[r].depth = rln;
  3.1511 +        }
  3.1512 +      }
  3.1513 +      return class_id;
  3.1514 +    }
  3.1515 +
  3.1516 +    /// \brief Split the class to subclasses.
  3.1517 +    ///
  3.1518 +    /// The current function splits the given class. The join, which
  3.1519 +    /// made the current class, stored a reference to the
  3.1520 +    /// subclasses. The \c splitClass() member restores the classes
  3.1521 +    /// and creates the heaps. The parameter is an STL output iterator
  3.1522 +    /// which will be filled with the subclass ids. The time
  3.1523 +    /// complexity is O(log(n)*k) where n is the overall number of
  3.1524 +    /// nodes in the splitted classes and k is the number of the
  3.1525 +    /// classes.
  3.1526 +    template <typename Iterator>
  3.1527 +    void split(int cls, Iterator out) {
  3.1528 +      std::vector<int> cs;
  3.1529 +      { // splitting union-find
  3.1530 +        int id = cls;
  3.1531 +        int l = classes[id].left;
  3.1532 +
  3.1533 +        classes[l].parent = classes[id].parent;
  3.1534 +        classes[l].depth = classes[id].depth;
  3.1535 +
  3.1536 +        nodes[~(classes[l].parent)].parent = ~l;
  3.1537 +
  3.1538 +        *out++ = l;
  3.1539 +
  3.1540 +        while (l != -1) {
  3.1541 +          cs.push_back(l);
  3.1542 +          l = classes[l].next;
  3.1543 +        }
  3.1544 +
  3.1545 +        classes[classes[id].right].next = first_class;
  3.1546 +        classes[first_class].prev = classes[id].right;
  3.1547 +        first_class = classes[id].left;
  3.1548 +        
  3.1549 +        if (classes[id].next != -1) {
  3.1550 +          classes[classes[id].next].prev = classes[id].prev;
  3.1551 +        }
  3.1552 +        classes[classes[id].prev].next = classes[id].next;
  3.1553 +        
  3.1554 +        deleteClass(id);
  3.1555 +      }
  3.1556 +
  3.1557 +      {
  3.1558 +        for (int i = 1; i < int(cs.size()); ++i) {
  3.1559 +          int l = classes[cs[i]].depth;
  3.1560 +          while (nodes[nodes[l].parent].left == l) {
  3.1561 +            l = nodes[l].parent;
  3.1562 +          }
  3.1563 +          int r = l;    
  3.1564 +          while (nodes[l].parent >= 0) {
  3.1565 +            l = nodes[l].parent;
  3.1566 +            int new_node = newNode();
  3.1567 +
  3.1568 +            nodes[new_node].prev = -1;
  3.1569 +            nodes[new_node].next = -1;
  3.1570 +
  3.1571 +            split(r, new_node);
  3.1572 +            pushAfter(l, new_node);
  3.1573 +            setPrio(l);
  3.1574 +            setPrio(new_node);
  3.1575 +            r = new_node;
  3.1576 +          }
  3.1577 +          classes[cs[i]].parent = ~r;
  3.1578 +          classes[cs[i]].depth = classes[~(nodes[l].parent)].depth;
  3.1579 +          nodes[r].parent = ~cs[i];
  3.1580 +
  3.1581 +          nodes[l].next = -1;
  3.1582 +          nodes[r].prev = -1;
  3.1583 +
  3.1584 +          repairRight(~(nodes[l].parent));
  3.1585 +          repairLeft(cs[i]);
  3.1586 +          
  3.1587 +          *out++ = cs[i];
  3.1588 +        }
  3.1589 +      }
  3.1590 +    }
  3.1591 +
  3.1592 +    /// \brief Gives back the priority of the current item.
  3.1593 +    ///
  3.1594 +    /// \return Gives back the priority of the current item.
  3.1595 +    const Value& operator[](const Item& item) const {
  3.1596 +      return nodes[index[item]].prio;
  3.1597 +    }
  3.1598 +
  3.1599 +    /// \brief Sets the priority of the current item.
  3.1600 +    ///
  3.1601 +    /// Sets the priority of the current item.
  3.1602 +    void set(const Item& item, const Value& prio) {
  3.1603 +      if (comp(prio, nodes[index[item]].prio)) {
  3.1604 +        decrease(item, prio);
  3.1605 +      } else if (!comp(prio, nodes[index[item]].prio)) {
  3.1606 +        increase(item, prio);
  3.1607 +      }
  3.1608 +    }
  3.1609 +      
  3.1610 +    /// \brief Increase the priority of the current item.
  3.1611 +    ///
  3.1612 +    /// Increase the priority of the current item.
  3.1613 +    void increase(const Item& item, const Value& prio) {
  3.1614 +      int id = index[item];
  3.1615 +      int kd = nodes[id].parent;
  3.1616 +      nodes[id].prio = prio;
  3.1617 +      while (kd >= 0 && nodes[kd].item == item) {
  3.1618 +        setPrio(kd);
  3.1619 +        kd = nodes[kd].parent;
  3.1620 +      }
  3.1621 +    }
  3.1622 +
  3.1623 +    /// \brief Increase the priority of the current item.
  3.1624 +    ///
  3.1625 +    /// Increase the priority of the current item.
  3.1626 +    void decrease(const Item& item, const Value& prio) {
  3.1627 +      int id = index[item];
  3.1628 +      int kd = nodes[id].parent;
  3.1629 +      nodes[id].prio = prio;
  3.1630 +      while (kd >= 0 && less(id, kd)) {
  3.1631 +        nodes[kd].prio = prio;
  3.1632 +        nodes[kd].item = item;
  3.1633 +        kd = nodes[kd].parent;
  3.1634 +      }
  3.1635 +    }
  3.1636 +    
  3.1637 +    /// \brief Gives back the minimum priority of the class.
  3.1638 +    ///
  3.1639 +    /// \return Gives back the minimum priority of the class.
  3.1640 +    const Value& classPrio(int cls) const {
  3.1641 +      return nodes[~(classes[cls].parent)].prio;
  3.1642 +    }
  3.1643 +
  3.1644 +    /// \brief Gives back the minimum priority item of the class.
  3.1645 +    ///
  3.1646 +    /// \return Gives back the minimum priority item of the class.
  3.1647 +    const Item& classTop(int cls) const {
  3.1648 +      return nodes[~(classes[cls].parent)].item;
  3.1649 +    }
  3.1650 +
  3.1651 +    /// \brief Gives back a representant item of the class.
  3.1652 +    /// 
  3.1653 +    /// The representant is indpendent from the priorities of the
  3.1654 +    /// items. 
  3.1655 +    /// \return Gives back a representant item of the class.
  3.1656 +    const Item& classRep(int id) const {
  3.1657 +      int parent = classes[id].parent;
  3.1658 +      return nodes[parent >= 0 ? classes[id].depth : leftNode(id)].item;
  3.1659 +    }
  3.1660 +
  3.1661 +    /// \brief Lemon style iterator for the items of a class.
  3.1662 +    ///
  3.1663 +    /// ClassIt is a lemon style iterator for the components. It iterates
  3.1664 +    /// on the items of a class. By example if you want to iterate on
  3.1665 +    /// each items of each classes then you may write the next code.
  3.1666 +    ///\code
  3.1667 +    /// for (ClassIt cit(huf); cit != INVALID; ++cit) {
  3.1668 +    ///   std::cout << "Class: ";
  3.1669 +    ///   for (ItemIt iit(huf, cit); iit != INVALID; ++iit) {
  3.1670 +    ///     std::cout << toString(iit) << ' ' << std::endl;
  3.1671 +    ///   }
  3.1672 +    ///   std::cout << std::endl;
  3.1673 +    /// }
  3.1674 +    ///\endcode
  3.1675 +    class ItemIt {
  3.1676 +    private:
  3.1677 +
  3.1678 +      const HeapUnionFind* _huf;
  3.1679 +      int _id, _lid;
  3.1680 +      
  3.1681 +    public:
  3.1682 +
  3.1683 +      /// \brief Default constructor 
  3.1684 +      ///
  3.1685 +      /// Default constructor 
  3.1686 +      ItemIt() {}
  3.1687 +
  3.1688 +      ItemIt(const HeapUnionFind& huf, int cls) : _huf(&huf) {
  3.1689 +        int id = cls;
  3.1690 +        int parent = _huf->classes[id].parent;
  3.1691 +        if (parent >= 0) {
  3.1692 +          _id = _huf->classes[id].depth;
  3.1693 +          if (_huf->classes[id].next != -1) {
  3.1694 +            _lid = _huf->classes[_huf->classes[id].next].depth;
  3.1695 +          } else {
  3.1696 +            _lid = -1;
  3.1697 +          }
  3.1698 +        } else {
  3.1699 +          _id = _huf->leftNode(id);
  3.1700 +          _lid = -1;
  3.1701 +        } 
  3.1702 +      }
  3.1703 +      
  3.1704 +      /// \brief Increment operator
  3.1705 +      ///
  3.1706 +      /// It steps to the next item in the class.
  3.1707 +      ItemIt& operator++() {
  3.1708 +        _id = _huf->nextNode(_id);
  3.1709 +        return *this;
  3.1710 +      }
  3.1711 +
  3.1712 +      /// \brief Conversion operator
  3.1713 +      ///
  3.1714 +      /// It converts the iterator to the current item.
  3.1715 +      operator const Item&() const {
  3.1716 +        return _huf->nodes[_id].item;
  3.1717 +      }
  3.1718 +      
  3.1719 +      /// \brief Equality operator
  3.1720 +      ///
  3.1721 +      /// Equality operator
  3.1722 +      bool operator==(const ItemIt& i) { 
  3.1723 +        return i._id == _id;
  3.1724 +      }
  3.1725 +
  3.1726 +      /// \brief Inequality operator
  3.1727 +      ///
  3.1728 +      /// Inequality operator
  3.1729 +      bool operator!=(const ItemIt& i) { 
  3.1730 +        return i._id != _id;
  3.1731 +      }
  3.1732 +
  3.1733 +      /// \brief Equality operator
  3.1734 +      ///
  3.1735 +      /// Equality operator
  3.1736 +      bool operator==(Invalid) { 
  3.1737 +        return _id == _lid;
  3.1738 +      }
  3.1739 +
  3.1740 +      /// \brief Inequality operator
  3.1741 +      ///
  3.1742 +      /// Inequality operator
  3.1743 +      bool operator!=(Invalid) { 
  3.1744 +        return _id != _lid;
  3.1745 +      }
  3.1746 +      
  3.1747 +    };
  3.1748 +
  3.1749 +    /// \brief Class iterator
  3.1750 +    ///
  3.1751 +    /// The iterator stores 
  3.1752 +    class ClassIt {
  3.1753 +    private:
  3.1754 +
  3.1755 +      const HeapUnionFind* _huf;
  3.1756 +      int _id;
  3.1757 +
  3.1758 +    public:
  3.1759 +
  3.1760 +      ClassIt(const HeapUnionFind& huf) 
  3.1761 +        : _huf(&huf), _id(huf.first_class) {}
  3.1762 +
  3.1763 +      ClassIt(const HeapUnionFind& huf, int cls) 
  3.1764 +        : _huf(&huf), _id(huf.classes[cls].left) {}
  3.1765 +
  3.1766 +      ClassIt(Invalid) : _huf(0), _id(-1) {}
  3.1767 +      
  3.1768 +      const ClassIt& operator++() {
  3.1769 +        _id = _huf->classes[_id].next;
  3.1770 +	return *this;
  3.1771 +      }
  3.1772 +
  3.1773 +      /// \brief Equality operator
  3.1774 +      ///
  3.1775 +      /// Equality operator
  3.1776 +      bool operator==(const ClassIt& i) { 
  3.1777 +        return i._id == _id;
  3.1778 +      }
  3.1779 +
  3.1780 +      /// \brief Inequality operator
  3.1781 +      ///
  3.1782 +      /// Inequality operator
  3.1783 +      bool operator!=(const ClassIt& i) { 
  3.1784 +        return i._id != _id;
  3.1785 +      }      
  3.1786 +      
  3.1787 +      operator int() const {
  3.1788 +	return _id;
  3.1789 +      }
  3.1790 +            
  3.1791 +    };
  3.1792 +
  3.1793 +  };
  3.1794 +
  3.1795 +  //! @}
  3.1796 +
  3.1797 +} //namespace lemon
  3.1798 +
  3.1799 +#endif //LEMON_UNION_FIND_H
     4.1 --- a/test/Makefile.am	Thu Mar 20 21:59:35 2008 +0000
     4.2 +++ b/test/Makefile.am	Thu Mar 20 23:06:35 2008 +0000
     4.3 @@ -13,11 +13,13 @@
     4.4  	test/digraph_test \
     4.5          test/dim_test \
     4.6  	test/graph_test \
     4.7 +	test/kruskal_test \
     4.8          test/maps_test \
     4.9          test/random_test \
    4.10          test/path_test \
    4.11          test/test_tools_fail \
    4.12 -        test/test_tools_pass
    4.13 +        test/test_tools_pass \
    4.14 +	test/unionfind_test
    4.15  
    4.16  TESTS += $(check_PROGRAMS)
    4.17  XFAIL_TESTS += test/test_tools_fail$(EXEEXT)
    4.18 @@ -29,8 +31,10 @@
    4.19  #test_error_test_SOURCES = test/error_test.cc
    4.20  test_graph_test_SOURCES = test/graph_test.cc
    4.21  # test_heap_test_SOURCES = test/heap_test.cc
    4.22 +test_kruskal_test_SOURCES = test/kruskal_test.cc
    4.23  test_maps_test_SOURCES = test/maps_test.cc
    4.24  test_path_test_SOURCES = test/path_test.cc
    4.25  test_random_test_SOURCES = test/random_test.cc
    4.26  test_test_tools_fail_SOURCES = test/test_tools_fail.cc
    4.27  test_test_tools_pass_SOURCES = test/test_tools_pass.cc
    4.28 +test_unionfind_test_SOURCES = test/unionfind_test.cc
     5.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     5.2 +++ b/test/kruskal_test.cc	Thu Mar 20 23:06:35 2008 +0000
     5.3 @@ -0,0 +1,149 @@
     5.4 +/* -*- C++ -*-
     5.5 + *
     5.6 + * This file is a part of LEMON, a generic C++ optimization library
     5.7 + *
     5.8 + * Copyright (C) 2003-2008
     5.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    5.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    5.11 + *
    5.12 + * Permission to use, modify and distribute this software is granted
    5.13 + * provided that this copyright notice appears in all copies. For
    5.14 + * precise terms see the accompanying LICENSE file.
    5.15 + *
    5.16 + * This software is provided "AS IS" with no warranty of any kind,
    5.17 + * express or implied, and with no claim as to its suitability for any
    5.18 + * purpose.
    5.19 + *
    5.20 + */
    5.21 +
    5.22 +#include <iostream>
    5.23 +#include <vector>
    5.24 +
    5.25 +#include "test_tools.h"
    5.26 +#include <lemon/maps.h>
    5.27 +#include <lemon/kruskal.h>
    5.28 +#include <lemon/list_graph.h>
    5.29 +
    5.30 +#include <lemon/concepts/maps.h>
    5.31 +#include <lemon/concepts/digraph.h>
    5.32 +#include <lemon/concepts/graph.h>
    5.33 +
    5.34 +
    5.35 +using namespace std;
    5.36 +using namespace lemon;
    5.37 +
    5.38 +void checkCompileKruskal()
    5.39 +{
    5.40 +  concepts::WriteMap<concepts::Digraph::Arc,bool> w;
    5.41 +  concepts::WriteMap<concepts::Graph::Edge,bool> uw;
    5.42 +
    5.43 +  concepts::ReadMap<concepts::Digraph::Arc,int> r;
    5.44 +  concepts::ReadMap<concepts::Graph::Edge,int> ur;
    5.45 +
    5.46 +  concepts::Digraph g;
    5.47 +  concepts::Graph ug;
    5.48 +
    5.49 +  kruskal(g, r, w);
    5.50 +  kruskal(ug, ur, uw);
    5.51 +
    5.52 +  std::vector<std::pair<concepts::Digraph::Arc, int> > rs;
    5.53 +  std::vector<std::pair<concepts::Graph::Edge, int> > urs;
    5.54 +
    5.55 +  kruskal(g, rs, w);
    5.56 +  kruskal(ug, urs, uw);
    5.57 +
    5.58 +  std::vector<concepts::Digraph::Arc> ws;
    5.59 +  std::vector<concepts::Graph::Edge> uws;
    5.60 +
    5.61 +  kruskal(g, r, ws.begin());
    5.62 +  kruskal(ug, ur, uws.begin());
    5.63 +
    5.64 +}
    5.65 +
    5.66 +int main() {
    5.67 +
    5.68 +  typedef ListGraph::Node Node;
    5.69 +  typedef ListGraph::Edge Edge;
    5.70 +  typedef ListGraph::NodeIt NodeIt;
    5.71 +  typedef ListGraph::ArcIt ArcIt;
    5.72 +
    5.73 +  ListGraph G;
    5.74 +
    5.75 +  Node s=G.addNode();
    5.76 +  Node v1=G.addNode();
    5.77 +  Node v2=G.addNode();
    5.78 +  Node v3=G.addNode();
    5.79 +  Node v4=G.addNode();
    5.80 +  Node t=G.addNode();
    5.81 +  
    5.82 +  Edge e1 = G.addEdge(s, v1);
    5.83 +  Edge e2 = G.addEdge(s, v2);
    5.84 +  Edge e3 = G.addEdge(v1, v2);
    5.85 +  Edge e4 = G.addEdge(v2, v1);
    5.86 +  Edge e5 = G.addEdge(v1, v3);
    5.87 +  Edge e6 = G.addEdge(v3, v2);
    5.88 +  Edge e7 = G.addEdge(v2, v4);
    5.89 +  Edge e8 = G.addEdge(v4, v3);
    5.90 +  Edge e9 = G.addEdge(v3, t);
    5.91 +  Edge e10 = G.addEdge(v4, t);
    5.92 +
    5.93 +  typedef ListGraph::EdgeMap<int> ECostMap;
    5.94 +  typedef ListGraph::EdgeMap<bool> EBoolMap;
    5.95 +
    5.96 +  ECostMap edge_cost_map(G, 2);
    5.97 +  EBoolMap tree_map(G);
    5.98 +  
    5.99 +
   5.100 +  //Test with const map.
   5.101 +  check(kruskal(G, ConstMap<ListGraph::Edge,int>(2), tree_map)==10,
   5.102 +	"Total cost should be 10");
   5.103 +  //Test with a edge map (filled with uniform costs).
   5.104 +  check(kruskal(G, edge_cost_map, tree_map)==10,
   5.105 +	"Total cost should be 10");
   5.106 +
   5.107 +  edge_cost_map.set(e1, -10);
   5.108 +  edge_cost_map.set(e2, -9);
   5.109 +  edge_cost_map.set(e3, -8);
   5.110 +  edge_cost_map.set(e4, -7);
   5.111 +  edge_cost_map.set(e5, -6);
   5.112 +  edge_cost_map.set(e6, -5);
   5.113 +  edge_cost_map.set(e7, -4);
   5.114 +  edge_cost_map.set(e8, -3);
   5.115 +  edge_cost_map.set(e9, -2);
   5.116 +  edge_cost_map.set(e10, -1);
   5.117 +
   5.118 +  vector<Edge> tree_edge_vec(5);
   5.119 +
   5.120 +  //Test with a edge map and inserter.
   5.121 +  check(kruskal(G, edge_cost_map,
   5.122 +		 tree_edge_vec.begin())
   5.123 +	==-31,
   5.124 +	"Total cost should be -31.");
   5.125 +  
   5.126 +  tree_edge_vec.clear();
   5.127 +
   5.128 +  check(kruskal(G, edge_cost_map,
   5.129 +		back_inserter(tree_edge_vec))
   5.130 +	==-31,
   5.131 +	"Total cost should be -31.");
   5.132 +  
   5.133 +//   tree_edge_vec.clear();
   5.134 +  
   5.135 +//   //The above test could also be coded like this:
   5.136 +//   check(kruskal(G,
   5.137 +// 		makeKruskalMapInput(G, edge_cost_map),
   5.138 +// 		makeKruskalSequenceOutput(back_inserter(tree_edge_vec)))
   5.139 +// 	==-31,
   5.140 +// 	"Total cost should be -31.");
   5.141 +
   5.142 +  check(tree_edge_vec.size()==5,"The tree should have 5 edges.");
   5.143 +
   5.144 +  check(tree_edge_vec[0]==e1 &&
   5.145 +	tree_edge_vec[1]==e2 &&
   5.146 +	tree_edge_vec[2]==e5 &&
   5.147 +	tree_edge_vec[3]==e7 &&
   5.148 +	tree_edge_vec[4]==e9,
   5.149 +	"Wrong tree.");
   5.150 +
   5.151 +  return 0;
   5.152 +}
     6.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     6.2 +++ b/test/unionfind_test.cc	Thu Mar 20 23:06:35 2008 +0000
     6.3 @@ -0,0 +1,104 @@
     6.4 +/* -*- C++ -*-
     6.5 + *
     6.6 + * This file is a part of LEMON, a generic C++ optimization library
     6.7 + *
     6.8 + * Copyright (C) 2003-2008
     6.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    6.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    6.11 + *
    6.12 + * Permission to use, modify and distribute this software is granted
    6.13 + * provided that this copyright notice appears in all copies. For
    6.14 + * precise terms see the accompanying LICENSE file.
    6.15 + *
    6.16 + * This software is provided "AS IS" with no warranty of any kind,
    6.17 + * express or implied, and with no claim as to its suitability for any
    6.18 + * purpose.
    6.19 + *
    6.20 + */
    6.21 +
    6.22 +#include <iostream>
    6.23 +
    6.24 +#include <lemon/list_graph.h>
    6.25 +#include <lemon/maps.h>
    6.26 +#include <lemon/unionfind.h>
    6.27 +#include "test_tools.h"
    6.28 +
    6.29 +using namespace lemon;
    6.30 +using namespace std;
    6.31 +
    6.32 +typedef UnionFindEnum<ListGraph::NodeMap<int> > UFE;
    6.33 +
    6.34 +int main() {
    6.35 +  ListGraph g;
    6.36 +  ListGraph::NodeMap<int> base(g);
    6.37 +  UFE U(base);
    6.38 +  vector<ListGraph::Node> n;
    6.39 +  
    6.40 +  for(int i=0;i<20;i++) n.push_back(g.addNode());
    6.41 +
    6.42 +  U.insert(n[1]);
    6.43 +  U.insert(n[2]);
    6.44 +
    6.45 +  check(U.join(n[1],n[2]) != -1,"Test failed.");
    6.46 +
    6.47 +  U.insert(n[3]);
    6.48 +  U.insert(n[4]);
    6.49 +  U.insert(n[5]);
    6.50 +  U.insert(n[6]);
    6.51 +  U.insert(n[7]);
    6.52 +
    6.53 +
    6.54 +  check(U.join(n[1],n[4]) != -1,"Test failed.");
    6.55 +  check(U.join(n[2],n[4]) == -1,"Test failed.");
    6.56 +  check(U.join(n[3],n[5]) != -1,"Test failed.");
    6.57 +
    6.58 +
    6.59 +  U.insert(n[8],U.find(n[5]));
    6.60 +
    6.61 +
    6.62 +  check(U.size(U.find(n[4])) == 3,"Test failed.");
    6.63 +  check(U.size(U.find(n[5])) == 3,"Test failed.");
    6.64 +  check(U.size(U.find(n[6])) == 1,"Test failed.");
    6.65 +  check(U.size(U.find(n[2])) == 3,"Test failed.");
    6.66 +
    6.67 +
    6.68 +  U.insert(n[9]);
    6.69 +  U.insert(n[10],U.find(n[9]));
    6.70 +
    6.71 +
    6.72 +  check(U.join(n[8],n[10]) != -1,"Test failed.");
    6.73 +
    6.74 +
    6.75 +  check(U.size(U.find(n[4])) == 3,"Test failed.");
    6.76 +  check(U.size(U.find(n[9])) == 5,"Test failed.");
    6.77 +
    6.78 +  check(U.size(U.find(n[8])) == 5,"Test failed.");
    6.79 +
    6.80 +  U.erase(n[9]);
    6.81 +  U.erase(n[1]);
    6.82 +
    6.83 +  check(U.size(U.find(n[10])) == 4,"Test failed.");
    6.84 +  check(U.size(U.find(n[2])) == 2,"Test failed.");
    6.85 +
    6.86 +  U.erase(n[6]);
    6.87 +  U.split(U.find(n[8]));
    6.88 +
    6.89 +
    6.90 +  check(U.size(U.find(n[4])) == 2,"Test failed.");
    6.91 +  check(U.size(U.find(n[3])) == 1,"Test failed.");
    6.92 +  check(U.size(U.find(n[2])) == 2,"Test failed.");
    6.93 +
    6.94 +
    6.95 +  check(U.join(n[3],n[4]) != -1,"Test failed.");
    6.96 +  check(U.join(n[2],n[4]) == -1,"Test failed.");
    6.97 +
    6.98 +
    6.99 +  check(U.size(U.find(n[4])) == 3,"Test failed.");
   6.100 +  check(U.size(U.find(n[3])) == 3,"Test failed.");
   6.101 +  check(U.size(U.find(n[2])) == 3,"Test failed.");
   6.102 +
   6.103 +  U.eraseClass(U.find(n[4]));
   6.104 +  U.eraseClass(U.find(n[7]));
   6.105 +
   6.106 +  return 0;
   6.107 +}