i trying implement disjoint sets use in kruskal's algorithm, having trouble understanding how should done , in particular, how manage forest of trees. after reading wikipedia description of disjoint sets , after reading description in introduction algorithms (cormen et al) have come following:
class disjointset { public: class node { public: int data; int rank; node* parent; node() : data(0), rank(0), parent(this) { } // constructor makeset }; node* find(node*); node* merge(node*, node*); // union }; disjointset::node* disjointset::find(disjointset::node* n) { if (n != n->parent) { n->parent = find(n->parent); } return n->parent; } disjointset::node* disjointset::merge(disjointset::node* x, disjointset::node* y) { x = find(x); y = find(y); if (x->rank > y->rank) { y->parent = x; } else { x->parent = y; if (x->rank == y->rank) { ++(y->rank); } } }
i pretty sure incomplete though , missing something.
introduction algorithms mentions there should forest of trees, not give explanation practical implementation of forest. watched cs 61b lecture 31: disjoint sets ( http://www.youtube.com/watch?v=wspajgfdl7q ) , here lecturer uses array store both forest , trees , values. there no explicit 'node' type of class have, mentioned. have found many other sources (i cannot post more 1 link), use technique. happy this, except relies on indices of array lookup , since want store values of type other int, need use else (std::map comes mind).
another issue unsure memory allocation because using c++. storing trees of pointers , makeset operation be: new disjointset::node; . now, these nodes have pointers parents, i'm not sure how find bottom of tree. how able traverse trees deallocate them all?
i understand basic concept of data structure, i'm bit confused implementation. advice , suggestions welcome, thank you.
not perfect implementation means (i did write after all!), help?
/*** * millipede: disjointsetforest.h * copyright stuart golodetz, 2009. rights reserved. ***/ #ifndef h_millipede_disjointsetforest #define h_millipede_disjointsetforest #include <map> #include <common/exceptions/exception.h> #include <common/io/util/osswrapper.h> #include <common/util/nulltype.h> namespace mp { /** @brief disjoint set forest standard data structure used represent partition of set of elements disjoint sets in such way common operations such merging 2 sets computationally efficient. implementation uses well-known union-by-rank , path compression optimizations, yield amortised complexity key operations of o(a(n)), (extremely slow-growing) inverse of ackermann function. implementation allows clients attach arbitrary data each element, can useful algorithms. @tparam t type of data attach each element (arbitrary) */ template <typename t = nulltype> class disjointsetforest { //#################### nested classes #################### private: struct element { t m_value; int m_parent; int m_rank; element(const t& value, int parent) : m_value(value), m_parent(parent), m_rank(0) {} }; //#################### private variables #################### private: mutable std::map<int,element> m_elements; int m_setcount; //#################### constructors #################### public: /** @brief constructs empty disjoint set forest. */ disjointsetforest() : m_setcount(0) {} /** @brief constructs disjoint set forest initial set of elements , associated values. @param[in] initialelements map initial elements associated values */ explicit disjointsetforest(const std::map<int,t>& initialelements) : m_setcount(0) { add_elements(initialelements); } //#################### public methods #################### public: /** @brief adds single element x (and associated value) disjoint set forest. @param[in] x index of element @param[in] value value associate element @pre - x must not in disjoint set forest */ void add_element(int x, const t& value = t()) { m_elements.insert(std::make_pair(x, element(value, x))); ++m_setcount; } /** @brief adds multiple elements (and associated values) disjoint set forest. @param[in] elements map elements add associated values @pre - none of elements added must in disjoint set forest */ void add_elements(const std::map<int,t>& elements) { for(typename std::map<int,t>::const_iterator it=elements.begin(), iend=elements.end(); it!=iend; ++it) { m_elements.insert(std::make_pair(it->first, element(it->second, it->first))); } m_setcount += elements.size(); } /** @brief returns number of elements in disjoint set forest. @return described */ int element_count() const { return static_cast<int>(m_elements.size()); } /** @brief finds index of root element of tree containing x in disjoint set forest. @param[in] x element set determine @pre - x must element in disjoint set forest @throw exception - if precondition violated @return described */ int find_set(int x) const { element& element = get_element(x); int& parent = element.m_parent; if(parent != x) { parent = find_set(parent); } return parent; } /** @brief returns current number of disjoint sets in forest (i.e. current number of trees). @return described */ int set_count() const { return m_setcount; } /** @brief merges disjoint sets containing elements x , y. if both elements in same disjoint set, no-op. @param[in] x first element @param[in] y second element @pre - both x , y must elements in disjoint set forest @throw exception - if precondition violated */ void union_sets(int x, int y) { int setx = find_set(x); int sety = find_set(y); if(setx != sety) link(setx, sety); } /** @brief returns value associated element x. @param[in] x element value return @pre - x must element in disjoint set forest @throw exception - if precondition violated @return described */ t& value_of(int x) { return get_element(x).m_value; } /** @brief returns value associated element x. @param[in] x element value return @pre - x must element in disjoint set forest @throw exception - if precondition violated @return described */ const t& value_of(int x) const { return get_element(x).m_value; } //#################### private methods #################### private: element& get_element(int x) const { typename std::map<int,element>::iterator = m_elements.find(x); if(it != m_elements.end()) return it->second; else throw exception(osswrapper() << "no such element: " << x); } void link(int x, int y) { element& elementx = get_element(x); element& elementy = get_element(y); int& rankx = elementx.m_rank; int& ranky = elementy.m_rank; if(rankx > ranky) { elementy.m_parent = x; } else { elementx.m_parent = y; if(rankx == ranky) ++ranky; } --m_setcount; } }; } #endif
Comments
Post a Comment