1.1 --- a/lemon/Makefile.am Thu Feb 28 16:41:56 2008 +0100
1.2 +++ b/lemon/Makefile.am Fri Feb 29 11:01:39 2008 +0000
1.3 @@ -18,11 +18,13 @@
1.4 lemon/concept_check.h \
1.5 lemon/dim2.h \
1.6 lemon/error.h \
1.7 + lemon/kruskal.h \
1.8 lemon/list_graph.h \
1.9 lemon/maps.h \
1.10 lemon/math.h \
1.11 lemon/random.h \
1.12 - lemon/tolerance.h
1.13 + lemon/tolerance.h \
1.14 + lemon/unionfind.h
1.15
1.16 bits_HEADERS += \
1.17 lemon/bits/alteration_notifier.h \
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/lemon/kruskal.h Fri Feb 29 11:01:39 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 Fri Feb 29 11:01:39 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 Feb 28 16:41:56 2008 +0100
4.2 +++ b/test/Makefile.am Fri Feb 29 11:01:39 2008 +0000
4.3 @@ -10,10 +10,12 @@
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/test_tools_fail \
4.11 - test/test_tools_pass
4.12 + test/test_tools_pass \
4.13 + test/unionfind_test
4.14
4.15 TESTS += $(check_PROGRAMS)
4.16 XFAIL_TESTS += test/test_tools_fail$(EXEEXT)
4.17 @@ -22,7 +24,9 @@
4.18 test_dim_test_SOURCES = test/dim_test.cc
4.19 #test_error_test_SOURCES = test/error_test.cc
4.20 test_graph_test_SOURCES = test/graph_test.cc
4.21 +test_kruskal_test_SOURCES = test/kruskal_test.cc
4.22 test_maps_test_SOURCES = test/maps_test.cc
4.23 test_random_test_SOURCES = test/random_test.cc
4.24 test_test_tools_fail_SOURCES = test/test_tools_fail.cc
4.25 test_test_tools_pass_SOURCES = test/test_tools_pass.cc
4.26 +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 Fri Feb 29 11:01:39 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 Fri Feb 29 11:01:39 2008 +0000
6.3 @@ -0,0 +1,114 @@
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/maps.h>
6.25 +#include <lemon/unionfind.h>
6.26 +#include "test_tools.h"
6.27 +
6.28 +using namespace lemon;
6.29 +using namespace std;
6.30 +
6.31 +typedef UnionFindEnum<StdMap<int, int> > UFE;
6.32 +
6.33 +void print(UFE const &ufe) {
6.34 + cout << "Print the classes of the structure:" << endl;
6.35 + int i = 1;
6.36 + for (UFE::ClassIt cit(ufe); cit != INVALID; ++cit) {
6.37 + cout << " " << i << " (" << cit << "):" << flush;
6.38 + for (UFE::ItemIt iit(ufe, cit); iit != INVALID; ++iit) {
6.39 + cout << " " << iit << flush;
6.40 + }
6.41 + cout << endl;
6.42 + i++;
6.43 + }
6.44 + cout << "done" << endl;
6.45 +}
6.46 +
6.47 +
6.48 +int main() {
6.49 + StdMap<int, int> base;
6.50 + UFE U(base);
6.51 +
6.52 + U.insert(1);
6.53 + U.insert(2);
6.54 +
6.55 + check(U.join(1,2) != -1,"Test failed.");
6.56 +
6.57 + U.insert(3);
6.58 + U.insert(4);
6.59 + U.insert(5);
6.60 + U.insert(6);
6.61 + U.insert(7);
6.62 +
6.63 +
6.64 + check(U.join(1,4) != -1,"Test failed.");
6.65 + check(U.join(2,4) == -1,"Test failed.");
6.66 + check(U.join(3,5) != -1,"Test failed.");
6.67 +
6.68 +
6.69 + U.insert(8,U.find(5));
6.70 +
6.71 +
6.72 + check(U.size(U.find(4)) == 3,"Test failed.");
6.73 + check(U.size(U.find(5)) == 3,"Test failed.");
6.74 + check(U.size(U.find(6)) == 1,"Test failed.");
6.75 + check(U.size(U.find(2)) == 3,"Test failed.");
6.76 +
6.77 +
6.78 + U.insert(9);
6.79 + U.insert(10,U.find(9));
6.80 +
6.81 +
6.82 + check(U.join(8,10) != -1,"Test failed.");
6.83 +
6.84 +
6.85 + check(U.size(U.find(4)) == 3,"Test failed.");
6.86 + check(U.size(U.find(9)) == 5,"Test failed.");
6.87 +
6.88 + check(U.size(U.find(8)) == 5,"Test failed.");
6.89 +
6.90 + U.erase(9);
6.91 + U.erase(1);
6.92 +
6.93 + check(U.size(U.find(10)) == 4,"Test failed.");
6.94 + check(U.size(U.find(2)) == 2,"Test failed.");
6.95 +
6.96 + U.erase(6);
6.97 + U.split(U.find(8));
6.98 +
6.99 +
6.100 + check(U.size(U.find(4)) == 2,"Test failed.");
6.101 + check(U.size(U.find(3)) == 1,"Test failed.");
6.102 + check(U.size(U.find(2)) == 2,"Test failed.");
6.103 +
6.104 +
6.105 + check(U.join(3,4) != -1,"Test failed.");
6.106 + check(U.join(2,4) == -1,"Test failed.");
6.107 +
6.108 +
6.109 + check(U.size(U.find(4)) == 3,"Test failed.");
6.110 + check(U.size(U.find(3)) == 3,"Test failed.");
6.111 + check(U.size(U.find(2)) == 3,"Test failed.");
6.112 +
6.113 + U.eraseClass(U.find(4));
6.114 + U.eraseClass(U.find(7));
6.115 +
6.116 + return 0;
6.117 +}