Boost logo

Boost :

From: Dietmar Kuehl (dietmar_kuehl_at_[hidden])
Date: 2000-07-07 06:29:11


Hi,

--- "Michael S. Tsirkin" <mtsirkin_at_[hidden]> wrote:
> Are you talking about interface, or implementation?

Both: Using a property accessor for the union/find stuff defines the
interface to be used (for details on property accessors see
<http://www.egroups.com/files/boost/graphs/property_accessor.html>).
The corresponding interface follows naturally.

> Changing property on each element for sets being merged
> will talke you all the way to N^2 ...

This is not what I was proposing! When merging two sets you only change
the property of one node, namely of one of the representatives.

> Some special structure (tree-like) was used in all books that
> I have seen.

The "standard" approach is to use a tree where only references to the
parent node are stored (that is, basically one node). This way you can
efficiently determine whether two nodes are in the same set: You just
determine the representatives of the sets the two nodes are in. The
representatives are just the roots of the trees. The basic trick is
that the parent nodes are updated whenever the representative of a node
is determined: In this case, the parent is modified to become the
representative.

> > I think the best algorithm (which also happens to be *much* simpler
> > than a splay tree) uses O(n * inverse(Ackermann(n))) or something
> > like this (don't nail me down on the details).

Someone else pointed out that this is not correct: I'm doing this from
memory and can only remember the algorithm. The complexity may be
amortized for a specific use (basically Kruskal's minimum spanning
tree) or something like this. I would have to read it up to find out
for sure.

> Maybe the textbook that I used was not very good, but
> 1- it gave a much more complex algorithm ( I do not understand
> exactly what you write, but it took more than two lines :) )
> and there was more memory overhead than splay trees, where
> you pay only for 3 pointers per value stored.

Maybe you want to do something different than union/find...? My
understanding of union/find is that you want to determine whether two
objects are in the same set. ... and this efficiently. With the
algorithm (or data structure) given above, you cannot efficiently
determine the elements in a set: To do this, you need to investigate
all elements and determine whether the elements happen to be in the set
you are interested.
 
> All in all, memory overhead is (at least) twice as much as that of
> splay tree implementation.

The overhead of the union/find data structure mentioned above is just
one pointer or integer or whatever per element. I don't think you can
get below this...

> > I can probably dig up some old implementation or hack a new one if
> > there is interest...

> Please do,

I have pasted the code at the end of this mail. To use it, you need a
property accessor which provides you with a pointer as argument. For
details on property accessor you should really look at the
documentationed above because the union/find property accessor is
somewhat confusing.

Regards,
  Dietmar
--- CUT HERE ---
// -*-C++-*- boost/ufindPA.hpp
//
<!!---------------------------------------------------------------------->

// <!! Copyright (C) 2000 Dietmar Kuehl, Phaidros Software AG >
// <!!>
// <!! Permission to use, copy, modify, distribute and sell this >
// <!! software for any purpose is hereby granted without fee, provided
>
// <!! that the above copyright notice appears in all copies and that >

// <!! both that copyright notice and this permission notice appear in
>
// <!! supporting documentation. Dietmar Kuehl and Phaidros Software AG
make >
// <!! no representations about the suitability of this software for
any >
// <!! purpose. It is provided "as is" without express or implied
warranty. >
//
<!!---------------------------------------------------------------------->

// Author: Dietmar Kuehl dietmar_kuehl_at_[hidden]
// Title: A property accessors implementing the union find algorithm

//
--------------------------------------------------------------------------

#if !defined(BOOST_UFINDPA_HPP)
#define BOOST_UFINDPA_HPP 1

#include <boost/property_accessor.hpp>

//
--------------------------------------------------------------------------
// Operations:
// get(ufPA, obj) returns the representative of the union obj is in
// set(ufPA, obj, rep) unites the union represented by obj and rep
// unite(ufPA, obj, rep) same as set(ufPA, obj, rep)

// Requirements:
// - PA - is a read/write property accessor
// - the iterator type used is convertible to the value_type
// - Pred - a unary predicate taking a value type as argument
// - returns true if the passed object is a representative
// - this is passed as argument because it depends on the
// initial value accessed using the property accessors
// - by default, if the property accessed using the PA accessor
// return zero, the object is considered to be a
representative

namespace boost
{
  template <class T>
  struct ufind_is_zero
  {
    bool operator()(T const &t) { return t == 0; }
  };

  template <class PA, class Pred = ufind_is_zero<typename
PA::value_type> >
  class union_find_pa
  {
  public:
    typedef PA pa_type;
    typedef typename PA::value_type value_type;
    typedef boost::read_write_property_accessor_tag category;

    template <class PAInit>
    union_find_pa(PAInit const &pa_init, Pred const &pred_init =
Pred()):
      m_pa(pa_init),
      m_pred(pred_init)
    {}

    value_type intern_get(value_type obj)
    {
      if (m_pred(get(m_pa, obj)))
        return obj;
      else
        {
          typename PA::value_type rc = intern_get(get(m_pa, obj));
          set(m_pa, obj, rc);
          return rc;
        }
    }
    void intern_set(value_type obj, value_type rep)
    {
      set(m_pa, intern_get(obj), intern_get(rep));
    }

  private:
    PA m_pa;
    Pred m_pred;
  };

  template <class PA, class Pred>
  inline typename PA::value_type
    get(union_find_pa<PA, Pred> &pa, typename PA::value_type obj)
  {
    return pa.intern_get(obj);
  }

  template <class PA, class Pred>
  inline void
    set(union_find_pa<PA, Pred> &pa, typename PA::value_type obj,
        typename PA::value_type rep)
  {
    pa.intern_set(obj, rep);
  }

  template <class PA, class Pred>
  inline void
    unite(union_find_pa<PA, Pred> &pa, typename PA::value_type obj,
          typename PA::value_type rep)
  {
    pa.intern_set(obj, rep);
  }
} // namespace boost

//
--------------------------------------------------------------------------

#endif /* BOOST_UFINDPA_HPP */

=====
<mailto:dietmar_kuehl_at_[hidden]>
<http://www.dietmar-kuehl.de/>

__________________________________________________
Do You Yahoo!?
Send instant messages & get email alerts with Yahoo! Messenger.
http://im.yahoo.com/


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk