Two way / reverse map [python]

Question

I'm doing this switchboard thing in python where I need to keep track of who's talking to whom, so if Alice --> Bob, then that implies that Bob --> Alice.

Yes, I could populate two hash maps, but I'm wondering if anyone has an idea to do it with one.

Or suggest another data structure.

EDIT: There are no multiple conversations. Lets say this is for a customer service call center, so when Alice dials into the switchboard, she's only going to talk to Bob. His replies also go only to her.

Answer 1

No, there is really no way to do this without creating two dictionaries. How would it be possible to implement this with just one dictionary while continuing to offer comparable performance?

You are better off creating a custom type that encapsulates two dictionaries and exposes the functionality you want.

Answer 2

Two hash maps is actually probably the fastest-performing solution assuming you can spare the memory. I would wrap those in a single class - the burden on the programmer is in ensuring that two the hash maps sync up correctly.

Answer 3

I would just populate a second hash, with

reverse_map = dict((reversed(item) for item in forward_map.items()))

Answer 4

In your special case you can store both in one dictionary:

relation = {}
relation['Alice'] = 'Bob'
relation['Bob'] = 'Alice'

Since what you are describing is a symmetric relationship. A -> B => B -> A

Answer 5

You have two separate issues.

1. You have a "Conversation" object. It refers to two Persons. Since a Person can have multiple conversations, you have a many-to-many relationship.

2. You have a Map from Person to a list of Conversations. A Conversion will have a pair of Persons.

Do something like this

from collections import defaultdict
switchboard= defaultdict( list )

x = Conversation( "Alice", "Bob" )
y = Conversation( "Alice", "Charlie" )

for c in ( x, y ):
    switchboard[c.p1].append( c )
    switchboard[c.p2].append( c )

Answer 6

Here is a simple bijective Dictionary implementation, although I don't know if it will meet your performance requirements.

(Link from this blog article on boost Bimap for Python, which has some nice discussion of the topic.)

Answer 7

The kjbuckets C extension module provides a "graph" data structure which I believe gives you what you want.