Suggestion : Sets.partition

[GoogleCodeExporter]

A method that would partition a Set<T> with an Equivalence<T> would be useful.

Original issue reported on code.google.com by grenier...@gmail.com on 22 Jul 2012 at 9:05

[GoogleCodeExporter]

Since sets do not guarantee the order of iteration, no assumptions can be made 
about the sequence of which partitions would arrive in. As such I'd say what 
you are actually looking for here in a disjointed set.

Disjoint set is discussed here:
http://code.google.com/p/guava-libraries/issues/detail?id=521&q=disjoint&colspec
=ID%20Stars%20Type%20Status%20Package%20Summary

An alternative solution which isn't exactly purposed to sets would be 
aggregation pattern which is discussed here:
https://groups.google.com/forum/?fromgroups#!searchin/guava-discuss/aggregation/
guava-discuss/NfE09gFfPjU/ts-HY9J6yp4J

Original comment by emily@soldal.org on 23 Jul 2012 at 6:51

[GoogleCodeExporter]

Try using Multimaps.index, otherwise you've got yourself into an O(n^2) 
situation.

Do you have a specific use case in mind?

Original comment by kurt.kluever on 24 Jul 2012 at 5:13

• Changed state: Research
• Added labels: Package-Collect, Type-Addition

[GoogleCodeExporter]

It doesn't have to be O(n^2), since Equivalence does have a hash method, but 
we'd have to reimplement the hash table for internal-only use (since we've 
ruled out an externally visible one elsewhere).

Original comment by wasserman.louis on 24 Jul 2012 at 6:30

[GoogleCodeExporter]

Fantastic! I've learned about a data structure + an implementation of it is on 
the way for guava.

Thanks.

Original comment by grenier...@gmail.com on 24 Jul 2012 at 7:44

[GoogleCodeExporter]

I want to partition sets of pitch-class sets (
http://en.wikipedia.org/wiki/Pitch-class_set) for an algorithmic
composition project of mine.

I previously coded a class representing a directed graph (DiGraph). It can
create a directed graph structure with a Relation object (which is
basically a binary predicate) and a Set.

I also coded a simple relation between pitch-class sets that relates those
which have the same number of elements but which differ on a fixed number
of elements.

My principal interest was to enumerate circuits in a pitch-class sets graph
built with this relation so I implemented the algorithm described in this
article :
http://dutta.csc.ncsu.edu/csc791_spring07/wrap/circuits_johnson.pdf

It worked all right for my needs, but I recently realized that what I
really needed was some kind of undirected graph structure built with
equivalences instead of relations. So I turned my relations into
equivalences.

Now I know I am really dealing with a disjoint-set structure and I have to
rethink how my CircuitFinder fits in all of this.

I'll see if a multimap can help me with that. Thanks for the tip.

Original comment by grenier...@gmail.com on 24 Jul 2012 at 9:42

[GoogleCodeExporter]

Writing the last comment made me realize that the relation I've mentionned
is not even an equivalence since it is not transitive.

So I just need an undirected graph class...

Original comment by grenier...@gmail.com on 24 Jul 2012 at 9:50

[GoogleCodeExporter]

Graph libraries tend to be *really* specialized, just because everybody wants 
them, and all the extra features associated with them, and all the algorithms 
associated with them.

You're probably better off investigating a full Java graph library -- JUNG is 
the first one that comes to mind.

Original comment by wasserman.louis on 24 Jul 2012 at 9:56

[GoogleCodeExporter]

Yeah, JUNG does look perfect for the job.

Original comment by grenier...@gmail.com on 24 Jul 2012 at 10:15

[GoogleCodeExporter]

Just for general information, for basic graph work, SetMultimap does quite well 
at modeling unlabeled digraphs, and Table similarly for edge-labeled digraphs, 
but I still recommend a specialized library if you need something fancier.

Original comment by wasserman.louis on 26 Jul 2012 at 9:39

[GoogleCodeExporter]

It might be uncalled for, but here's the (untested, unchecked) function I
meant, if it can be of any use :

public static <T> ArrayList<TreeSet<T>> partition(TreeSet<T> s,
Equivalence<T> e)
{
ArrayList<TreeSet<T>> o = new ArrayList<>();
TreeSet<T> t = new TreeSet<>(); t.addAll(s);
 while(!t.isEmpty())
{
T elem = t.first();
t.remove(elem);
boolean found = false;
for(int i=0;i<o.size();i++)
{
if(e.equivalent(o.get(i).first(),elem))
{
o.get(i).add(elem);
found = true;
break;
}
}
 if(!found)
{
TreeSet<T> n = new TreeSet<>();
n.add(elem);
o.add(n);
}
 }
 return o;
}

Original comment by grenier...@gmail.com on 21 Aug 2012 at 6:32

[GoogleCodeExporter]

This seems to have transitioned to being about graphs.

Original comment by cpov...@google.com on 27 Feb 2014 at 8:06

• Changed state: WorkingAsIntended

[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:13

• Added labels: MigratedToGitHub

[GoogleCodeExporter]

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

• Added labels: Restrict-AddIssueComment-Commit