Original comment posted by jim.andreou on 2010-08-10 at 10:10 PM

In other words, (and assuming you want to access the relationships bidirectionally,) you look for a BiMultimap<K, V>.

For reference, this is the API surface that BiMap takes:
http://guava-libraries.googlecode.com/svn/trunk/javadoc/com/google/common/collect/class-use/BiMap.html

In the meantime, it can't be that hard to maintain a Multimap<K, V> along with the inverse Multimap<V, K>, if offer just a tiny API for updates. It would be a mess if you wanted to expose these as mutable multimaps to users - you would have to wrap them in ForwardingMultimaps and intercept all kind of methods, returning ForwardingXXX (key sets, values, iterators...). This is a big implementation investment.

Much simpler if you only expose unmodifiable Multimaps, and have just one method that does the updates (perhaps its inverse too).

For another reference, here is the API I designed for many-to-many relations by the way (not for your case, only meant for transitive relations) - it was easy to offer bidirectionality with only a couple of methods for updates, not the myriads of ways a Map or a Multimap can be updated.
https://alis.cs.bath.ac.uk/hudson/job/transitivity-utils/javadoc/edu/bath/transitivityutils/TransitiveBiRelation.html
(It's from this project, sorry for the plug: http://code.google.com/p/transitivity-utils/ )

Original comment posted by Lord.Quackstar on 2010-08-21 at 03:52 PM

@jim.andreou

I think this is such a unique problem that implementing ForwardMultimaps and Multimaps would just make a mess of code. A simpler independent class thats would be mutable is a much more viable alternative, and would actually get people to write the initial code

One way to implement this is have 2 HashMaps with HashSets as their values. One map would be for keys and one map would be for values. This is how it would work

Definition
 - Instead of key-value pairs, it would be called A B or something else that isn't confusing. Key-value pair imply's a 1 to 1 relationship

Requirements
 - Must support A or B not having corresponding values (in above book-author example, eg Author with no books or book with no authors).
 - Must have good performance, especially with large maps. (maps with a few thousand A and B entries
 - Should have as small as possible memory footprint
 - Must keep internal synchronization of the internal maps, so an update in one map is immediately reflected in the other
 - Should have external synchronization wrapper, or be synchronized internally so its not needed
 - Should be simple internally and externally
 - For returned Sets, there should be a wrapper of HashSet on methods like add and remove to create the necessary values. Until this is created all returned HashSets should be wrapped in an immutable set from Collections.immutableSet

Examples
 - User adds an A or B entry - Added to A entry map, new set created
 - User adds an A and B entry - Added to respective maps as keys. B entry is added to A's Hashset, and vise versa
 - User requests A or B entry - Simply returns corresponding HashSet. The returned HashSet should follow the requirement listed above
 - User deletes A or B entry - This would be somewhat time consuming. First, the entry is removed from its Map. Then in the other map, iterate over all the HashSets removing the entry to break all associations
 - User iterates A or B entries - Delegates to appropriate map iterator
 - User iterates over entire map - This should generate an iterator using Map.Entry or a similar pair class where each pair is a relationship. This should go over all the relationships in the map without duplication (IE anAEntry -> aBentry is the same as aBentry -> anAEntry). This should also include orphaned entries. Since this a complex problem to code and would be strange, this is a low priority task

How long would such a thing take?

Original comment posted by boppenheim@google.com on 2010-09-23 at 05:09 AM

I could actually use something like this in some code I'm writing (outside of Google). It does, however, seem like it could be the type of thing that will take a lot of work to get right (in terms of both performance and corectness).

Original comment posted by Lord.Quackstar on 2010-09-23 at 11:43 AM

@boppenheim

I do have a simple implementation that I wrote here:

http://code.google.com/p/pircbotx/source/browse/trunk/src/main/java/org/pircbotx/ManyToManyMap.java

If you want, you can use it. Its pretty basic, not worrying about iterators or merged datasets. Just copy and go.

Original comment posted by jim.andreou on 2010-09-23 at 07:42 PM

@LordQuackstar, a simple implementation is pretty trivial to do, designing and supporting the most useful API is not :) btw, you forgot to synchronize a couple of methods (removeA, removeB).

Original comment posted by boppenheim@google.com on 2010-09-23 at 08:09 PM

Thanks for letting me know about your implementation. Thankfully in my application, I never need to take the map as an argument, return it from a method, or do anything fancy; it's completely private to one class. So for my use, two maps is okay.

Original comment posted by fry@google.com on 2011-01-28 at 04:59 PM

(No comment entered for this change.)

Status: Accepted
Labels: Type-Enhancement

Original comment posted by kevinb@google.com on 2011-07-13 at 06:18 PM

(No comment entered for this change.)

Status: Triaged

Original comment posted by fry@google.com on 2011-12-10 at 03:47 PM

(No comment entered for this change.)

Labels: Package-Collect

Original comment posted by wasserman.louis on 2012-01-10 at 04:15 PM

Does the new inverse() method in ImmutableMultimap help?

Original comment posted by fry@google.com on 2012-02-16 at 07:17 PM

(No comment entered for this change.)

Status: Acknowledged

Original comment posted by kevinb@google.com on 2012-05-30 at 07:43 PM

(No comment entered for this change.)

Labels: -Type-Enhancement, Type-Addition

Original comment posted by kevinb@google.com on 2012-06-22 at 06:16 PM

(No comment entered for this change.)

Status: Research

Original comment posted by knightofiam on 2013-02-24 at 09:22 PM

I would like to see this implemented because I am looking for a one-to-many bidirectional multimap, which is a special case. There is already a request for this in the guava forums, which also links back to this issue. See:

https://groups.google.com/forum/?fromgroups=#!topic/guava-discuss/K0edXSa3k7A

ImmutableMultimap.inverse() doesn't work well for me because I have to do something ugly like:

// Loop up the Continent of a specific Country:
return Iterables.getOnlyElement (countriesInContinent.inverse().get (country));

where countriesInContinent is an ImmutableMultimap <Continent, Country>.

I don't want to store a continent reference inside of a Country because I don't want Countries to need to know about Continents. ImmutableMultimap.inverse() could work if there was a way to guarantee only unique values in the multimap, thus allowing the return type of the inverse method to be a simple map rather than a multimap.

Original comment posted by cpovirk@google.com on 2013-02-25 at 12:56 AM

If you can build the Country->Continent mapping first and if you can wait for release 14 (or use 14.0-rc3), you can this:

ImmutableMap<Country, Continent> continentForCountry = ...;
ImmutableSetMultimap<Continent, Country> countriesForContinents =
    continentForCountry.asMultimap().inverse();

https://google.github.io/guava/releases/v14.0/apidocs/com/google/common/collect/ImmutableMap.html#asMultimap%28%29

Original comment posted by knightofiam on 2013-02-25 at 05:27 PM

That's ingenious. Thanks!

Original comment posted by greg.briggs on 2013-05-13 at 11:08 PM

My application could make use of a mutable bidirectional multimap. Note that, compared to Multimap, I would suggest using Set instead of Collection, for reverse lookup to make sense. In other words, I am hoping for a BiMultimap that would replace this pair of variables:

Map<X,Set<Y>> forward;
Map<Y,Set<X>> backward;

Also, a total count of all the X-Y pairs would be great. Thanks!

Original comment posted by xaerxess on 2014-07-27 at 09:18 AM

Any chance of open-sourcing BiMultimap? There's some demand for it (26 stars, also see this SO question: http://stackoverflow.com/questions/24850359/bidirectional-multimap-equivalent-data-structure).

Maybe you should release BiMulimaps only with BiMultimapBuilder, but without "standard" implementations?

Original comment posted by kevinb@google.com on 2014-07-27 at 05:38 PM

The star count and the SO post tell us nothing about how many users actually need mutability. The closest I see to that is comment 18 declaring "we could make use of it."

Unless we get clear evidence of a widespread need that ImmutableMultimap.inverse() won't satisfy, adding this feature would be a betrayal of Guava's focus on "power-to-weight ratio".

Status: WontFix