java - how to flatten a collection of sets, and should I do it in the first place?

Question

hi all,

say i have a graph, implemented with two maps (in and out) that map (source, set(edge)) and (target, set(edge)), respectively. until now, i also had allEdges set, which i decided to get rid of. returning edge set is now more difficult, as i have to flatten out the values of one of the maps. what's the best (fastest) way to do it? or should i just leave the allEdges set (i don't care much about memory, just thought having it was a bit redundant).

thanks

Answer 1

Time and space are the quintessential tradeoff. You can store your edge set explicitly, sacrificing the amount of space it takes to have it without having to calculate it, or you can reclaim that space and calculate the set of all edges when you need it.

From your post, it seems like the former is the better decision. Don't worry about "The Right Way" - worry about what makes sense for your application.

Answer 2

Note that if you use SetMultimap from google-collections, you can trivially see the collection of all edges using multimap.values(). In your case, if I understand you correctly, there will be no duplicates in that collection, but unfortunately it won't actually implement Set. To get a set, use ImmutableSet.copyOf(multimap.values()).

And yes, if you'll need it as a set often, it makes sense to keep a redundant Set around and keep updating it as you go.

Or you could scratch all this and use a full-featured graphs library such as JUNG.