3
$\begingroup$

In the beginning of the Princeton algorithms course the Dynamic connectivity problem is presented (quick-find, quick-union). Here is how it's described:

The input is a sequence of pairs of integers, where each integer represents an object of some type and we are to interpret the pair p q as meaning “p is connected to q.” We assume that “is connected to” is an equivalence relation, which means that it is

  • Reflexive : p is connected to p.
  • Symmetric : If p is connected to q, then q is connected to p.
  • Transitive : If p is connected to q and q is connected to r, then p is connected to r.

And it has one simple implementation called quick-find:

One approach is to maintain the invariant that p and q are connected if and only if id[p] is equal to id[q]. In other words, all sites in a component must have the same value in id[].This method is called quick-find because find(p) just returns id[p], which immediately implies that connected(p, q) reduces to just the test id[p] == id[q] and returns true if and only if p and q are in the same component...To combine the two components into one, we have to make all of the id[] entries corresponding to both sets of sites the same value, as shown in the example at right.

My question is how can this be used for real objects? It works for integers, but what if I need to know whether the object A is connected to the object B, not if 3 is connected to 5? One solution I can think of is to have an array of objects where each object's index in the array corresponds to the index of the array used for connectivity. For example:

   1   2   3   4   5
[ { } { } {A} { } {B} ]   <---- real data

   1   2   3   4   5
[  1   2   3   4   3 ]    <---- connections (3 and 5 have the same group id 3)

Is that how it's applied?

$\endgroup$
4
$\begingroup$

Short answer: indirection.

For instance, each object could have a field that contains an index into the id array.

Or, you could use pointers. Standard union-find data structures often use pointers instead of integers/indices/arrays. Thus, each object has a pointer to another object in the same equivalence class. See, e.g., https://en.wikipedia.org/wiki/Disjoint-set_data_structure or other standard presentations of union-find data structures.

$\endgroup$
3
$\begingroup$

You don't say which union-find implementation you are talking about. On the abstract level, all is good; in the first quote, the authors already state that integers represent arbitrary objects!

In OOP-speak, as long as your objects have unique integer identifiers, you can immediately apply the material. In many languages, object identity will suffice.

In implementations, a union-find data structure may define an internal element wrapper (as lists and trees do as well), that is something like:

struct Element<T> {
    id: Int
    value: T
}

You would use id for managing the union-find business, and all get-style operations would return (sets of) values.

That all said, none if this changes the concepts; they carry over to all countable (well, recursively enumerable, I guess) sets/types. That's why algorithms textbooks typically only deal with integers: it makes for simpler notation (and code).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.