Add the DisjointSet data structure

[GoogleCodeExporter]

It's a useful data structure that is not so easy to implement by itself, and 
that is very useful in algorithmics, such as in the graph theory, for instance.

Original issue reported on code.google.com by ogregoire on 12 Jan 2011 at 11:58

[GoogleCodeExporter]

Here is a straw API to play with:

https://github.com/lowasser/guava-experimental/commit/e84cb02604ca5115d76004e56c
5034b7356e5853#diff-1

To summarize: UnionFindEquivalence is an Equivalence<Object> implementation 
that starts out equivalent to Equivalence.equals(), but allows you to merge 
equivalence classes.  Internally, it holds a Map<Object, Partition> for objects 
that are in equivalence classes of size > 1.

No, it doesn't let you get the objects back out for the moment, but I've 
written a couple of algorithms using disjoint-set data structures and it's 
satisfied my needs there.  In a pinch, it could get retrofitted later for some 
of those operations, but this feels relatively neat and tidy, and addresses the 
use cases I'm aware of.

Original comment by wasserman.louis on 14 Jun 2012 at 10:21

[GoogleCodeExporter]

Personally, I would prefer an immutable Equivalence created with a builder:
UnionFind equiv = UnionFindBuilder.builder().merge(a, b).merge(c, d).build();

Original comment by thomas.a...@gmail.com on 15 Jun 2012 at 7:07

[GoogleCodeExporter]

@thomas: For all of the applications I came across, such an equivalence would 
be of little use.  Union-find data structures need to be dynamic to serve their 
traditional applications.

Original comment by wasserman.louis on 15 Jun 2012 at 2:54

[GoogleCodeExporter]

Specific examples: Kruskal's algorithm is utterly pointless without a dynamic 
union-find structure, and several variations on it are equally pointless.

Original comment by wasserman.louis on 15 Jun 2012 at 2:55

[GoogleCodeExporter]

Wouldn't 
equiv = UnionFindEquivalence.create() 
equiv.merge(a, b);
w = equiv.wrapp(a);
w.equals(equiv.wrapp(c)) -> false
equiv.merge(b, c);
w.equals(equiv.wrapp(c)) -> true
break the equals contract?

Original comment by thomas.a...@gmail.com on 16 Jun 2012 at 7:30

[GoogleCodeExporter]

Well, the Object.equals() contract specifies 

"It is consistent: for any non-null reference values x and y, multiple 
invocations of x.equals(y) consistently return true or consistently return 
false, provided no information used in equals comparisons on the objects is 
modified."

Of course, the last part is crucial: "provided no information used in equals 
comparisons on the objects is modified."

The doc for Equivalence isn't quite so specific, although it has allusions 
along the same lines, e.g. for hash: "...as long as x remains unchanged 
according to the definition of the equivalence."

Essentially, I'm suggesting that that exception apply here.  It remains the 
case that a non-dynamic version is *useless* for the traditional applications 
of this data structure...and that it makes a lot of sense to model this as an 
equivalence relation rather than a Map<E, Partition> or something along those 
lines.

Original comment by wasserman.louis on 16 Jun 2012 at 9:50

[GoogleCodeExporter]

Okay, I remembered a more strict version of the contract, i.e. I'd always 
implement equals in this way. One effect with a weaker implementation is that 
objects disappear from collections:

UnionFindEquivalence equiv = UnionFindEquivalence.create();
Wrapper<Integer> wrap = equiv.wrap(1);
HashSet<Wrapper<Integer>> set = new HashSet<Wrapper<Integer>>();
set.add(wrap);
System.out.println(set.contains(wrap));  //true
equiv.merge(1, 2);
System.out.println(set.contains(wrap));  //false

You're right that an immutable version of a UnionFindEquivalence is useless 
(unless you find a practical persistent Union-find data structure).

Original comment by thomas.a...@gmail.com on 18 Jun 2012 at 6:46

[GoogleCodeExporter]

This issue has been migrated to GitHub.

It can be found at https://github.com/google/guava/issues/<id>

Original comment by cgdecker@google.com on 1 Nov 2014 at 4:15

• Added labels: MigratedToGitHub

[GoogleCodeExporter]

Original comment by cgdecker@google.com on 1 Nov 2014 at 4:18

• Changed state: Migrated

[GoogleCodeExporter]

Original comment by cgdecker@google.com on 3 Nov 2014 at 9:09

• Added labels: Restrict-AddIssueComment-Commit