BiMultimap

[Willi Schönborn]

Hi,

i came across the use case to map
districts to postal codes which is a bidirectional many-to-many
relationship.

I investigated all "map"s i know about:

java.util.Map, is many-to-one (many different keys can point the same
value),
com.google.common.collect.BiMap, is one-to-one (every key and every
value is unique),
com.google.common.collect.Multimap, is many-to-many (one key can has
many values associated).

Multimap is the closest to what i want, but i need to keep two instances
in sync
to provide the bidirectionality:

Multimap<District, Zipcode> and Multimap<Zipcode, District>

An abstraction that would fit perfectly would be "BiMultimap" which
provides an inverse method
just like BiMap does.

What do you guys think. Is there a chance to get something like that
included into Guava?

Greetings
Willi

[Jared Levy]

Actually, there is a BiMultimap in Google's internal code base. We haven't yet decided whether to open-source it.

2010/10/2 Willi Schönborn <w.scho...@googlemail.com>

--
guava-...@googlegroups.com.
http://groups.google.com/group/guava-discuss?hl=en
unsubscribe: guava-discus...@googlegroups.com

This list is for discussion; for help, post to Stack Overflow instead:
http://stackoverflow.com/questions/ask
Use the tag "guava".

[Louis Wasserman]

+1 for open-sourcing it, btw.

Louis Wasserman
wasserm...@gmail.com
http://profiles.google.com/wasserman.louis

2010/10/2 Jared Levy <jared....@gmail.com>

[Jason Bray]

Agreed - this would be a very useful addition to guava.

On Oct 2, 6:07 pm, Louis Wasserman <wasserman.lo...@gmail.com> wrote:
> +1 for open-sourcing it, btw.
>
> Louis Wasserman

> wasserman.lo...@gmail.comhttp://profiles.google.com/wasserman.louis
>
> 2010/10/2 Jared Levy <jared.l.l...@gmail.com>

>
>
>
>
>
>
>
> > Actually, there is a BiMultimap in Google's internal code base. We haven't
> > yet decided whether to open-source it.
>

> > 2010/10/2 Willi Schönborn <w.schoenb...@googlemail.com>

> >> unsubscribe: guava-discus...@googlegroups.com<guava-discuss%2Bunsubscribe@goog legroups.com>

>
> >> This list is for discussion; for help, post to Stack Overflow instead:
> >>http://stackoverflow.com/questions/ask
> >> Use the tag "guava".
>
> >  --
> > guava-...@googlegroups.com.
> >http://groups.google.com/group/guava-discuss?hl=en

> > unsubscribe: guava-discus...@googlegroups.com<guava-discuss%2Bunsubscribe@goog legroups.com>

[Dimitris Andreou]

Slightly off-topic, but let me get this right: when two googlers discuss, they say "I need a graph" -or- "I need a BiMultimap"?

[Kevin Bourrillion]

They might say those things or "relation" or who knows what.

The focus of what we're developing is: "key-value pairs, neither unique, navigable in either direction", purely as simple as that.  So BiMultimap speaks precisely to that, while any other name we might choose risks violating the expectations of users who have existing associations with that name.

--
Kevin Bourrillion @ Google
http://guava-libraries.googlecode.com

[Dimitris Andreou]

I do appreciate that there are lots of flavors of graphs, I only (mistakenly) thought that a BiMultimap would match the most common type of them (but yes, I now realize most people might think that an unqualified "graph" means a simple graph vs a multigraph). But to resemble a regular graph, that would have to be a BiMultimap<V, V> anyway, not BiMultimap<K, V> in general, so my comment was probably confusing.

By the way, +1 for getting something like this open-sourced, I would definitely find usage for it (here is some code where I manually maintain the inverse relation: http://code.google.com/p/transitivity-utils/source/browse/trunk/src/edu/bath/transitivityutils/DefaultTransitiveBiRelation.java, but using SetMultimap). 

Which brings up the issue, should a BiMultimap explicitly specify non-uniqueness of pairs? Or would it be better to be vague about it (as Multimap) and allow the possibility of something like "SetBiMultimap" (or "BiSetMultimap"), as in ListMultimap/SetMultimap. Personally, multigraphs are my bread and butter, so I can definitely see the value of what you're focused to, it would be nice though to allow the other case (simple bidirectional relations if you may) too.

[Kevin Bourrillion]

Sorry, I'm not speaking very clearly.  I didn't mean implementations wouldn't be allowed to de-dup if they want, I just meant that they don't have to, just like a regular Multimap.

Mostly I just meant to say that it's many-to-many (also like a regular multimap), and bidirectionally navigable (not like a regular multimap).

I think.  But I'm tired.

[Dimitris Andreou]

Oh, I see, thanks for clarifying! Then it should be just fine - eager to see it.

[Joshua O'Madadhain]

[slight hijack of Dimitris' hijack, apologies]

Dimitris:

If you're interested in graphs per se, take a look at JUNG
(http://jung.sf.net). If it's not what you want, feedback would be
great.

JUNG doesn't currently use Guava internally, but we're in the process
of creating a new version that does.

Joshua

--
   Joshua O'Madadhain: Information Scientist, Musician, Philosopher-At-Tall
  "It's that moment of dawning comprehension that I live for" -- Bill Watterson

[Dimitris Andreou]

You probably don't recall my name, but we should spare the list since we've had this discussion already :) I mentioned I also developed a graph library (http://code.google.com/p/flexigraph/), back in 2006, after evaluating JDSL and Jung (the first version of the latter, obviously) among others.

[Joshua O'Madadhain]

Dimitris:

Oops, that does ring a bell. Checking email archives. :P :)

Joshua