Bidirectional Dict In Python

GOAL

Today’s goal is discuss the method of implementing bidirectional dictionary in Python.

Environment

Windows 10
Python 3.8.7

What is bidirectional dictionary?

Dictionary or hash table is a data structure composed of a collection of (key, map) pair where keys are unique, which is known as an associative array, map, symbol table, or dictionary. The advantage of dictionary is its small time complexity O(1).

job_dict = {"John":"director", "Mike":"designer", "Anna":"designer", "Lisa":"engineer"}
# job_dict["Mike"] returns "designer"

Bidirectional dictionary I’d like is the dictionary that return the value when the key is given and return keys when the value is given.

# what I'd like to do
job_bidict = {"John":"director", "Mike":"designer", "Anna":"designer", "Lisa":"engineer"}
# job_bidict["Mike"] returns "designer"
# job_bidict["designer"] returns "Mike", "Anna" or ["Mike", "Anna"]

Method

I introduces 3 methods and pros and cons of them.

<!--more-->

Method 1. Use bidict library

Install and import bidict library according to bidict documentation.

pip install bidict

from bidict import bidict
job_bidict = bidict({"John":"director", "Mike":"designer", "Lisa":"engineer"}) # The values should be unique

print(job_bidict["Mike"])
# output => designer
print(job_bidict.inverse["designer"])
# output => Mike

• Advantage
  • It’s easy to implement.
  • The library has many useful functions
• Disadvantage
  • The values of bidict should be unique.
  • The file size grows when the program is distributed.

Advantage: It’s easy to implement.
Disadvantage: The file size grows when you distribute the program.

Method 2. Use 2 dicts in a class

class MyBidict:
  def __init__(self, init_dict):
    self.dict_normal = {} # normal dict to store (key, values)
    self.dict_inverse = {} # normal dict to store (value. keys)
    for key in init_dict.keys():
      self.add_item(key, init_dict[key])
  def add_item(self, key, value):
    if key in self.dict_normal:
      self.dict_normal[key].append(value)
    else:
      self.dict_normal[key] = [value]
    if value in self.dict_inverse:
      self.dict_inverse[value].append(key)
    else:
      self.dict_inverse[value] = [key]
  def get_item(self, key):
    return self.dict_normal[key]
  def get_item_inverse(self, value):
    return self.dict_inverse[value] 

job_bidict = MyBidict({"John":"director", "Mike":"designer", "Anna":"designer", "Lisa":"engineer"})

print(job_bidict.get_item("Mike"))
# output => ['designer']
print(job_bidict.get_item_inverse("designer"))
# output => ['Mike', 'Anna']

• Advantage
  • You can customize the specification of the dict such as whether it allows duplicate values or not.
  • You can add functions you need.
• Disadvantage
  • It takes time and effort to implement.
  • The specification is sometimes different from the built-in dict.

Method 3. Implement Bidict class as a subclass of dict

class MyBidict(dict):
  def __init__(self, init_dict):
    self.inverse = {}
    dict.__init__(self, init_dict)
    for key, value in init_dict.items():
      self.inverse[value] = key
  def __setitem__(self, key, value):
    dict.__setitem__(self, key, value)
    self.inverse.__setitem__(value, key)

job_bidict = MyBidict({"John":"director", "Mike":"designer", "Anna":"designer", "Lisa":"engineer"})

print(job_bidict["Mike"])
# output => designer 
print(job_bidict.inverse["designer"])
# output => Anna

• Advantage
  • It’s relatively easy to implement.
  • You can customize the specification of the dict such as whether it allows duplicate values or not.
  • The functions of built-in dict can be still used.
• Disadvantage
  • It takes a little time and effort to implement.
  • The original function can destroy the specifications of built-in dict.

Union-Find in Python

GOAL

To understand and to implement union-find in Python.

Example of problems using union-find algorithm

Dividing clusters

There is a list of friends from N people. Divide them in cluster.

n = 6
friendship = [(1, 2), (3, 4), (1, 6)]