Powerful Dictionaries


There are so many different kind of dictionaries. Some dictionaries help us to translate some words in another language to our language. Some dictionaries help to get the exact meaning of words. But now I’m going to talk about dictionaries in Python programming language. Actually I thought I should write this article after we compete for the IEEE Xtream 12.0 because I used python dictionaries a lot in that competition. That was our first IEEE Xtream experience and I think we performed well.

IEEE Xtream 12.0 ranking table's screen-shot is given below and you can see how we performed. Yes... It's the pizza hut number :p

Map data structures with dictionaries

We can map many complex data structures to a dictionary. As a basic example, we can take associative arrays, used in other languages like php, javascript. Some languages use a data structure called hash table similar to associative arrays. If you have learned data structures with C, C++ or Java, you must have learned about hash-maps and hash tables. By using python dictionaries we can create key value pairs like in associative arrays and hash tales. But python dictionaries are easier to add, edit, delete and to retrieve data. Below image will show you how to deal with a python dictionary.


Data types for keys and values in python dictionary

Every hash table data types can be used as keys in a python dictionary. But we can use any data type to define values in python dictionaries. I have listed down all the hashable data types in python 3.
  • Integer
  • Float
  • Complex numbers
  • String
  • Boolean
Unhashable data types are,
  • List
  • Tuple
  • Set
  • Dictionaries

Map binary trees to python dictionaries

Yes of course. Because python is an object oriented language, you can create a class called Node and create whatever you need like linked lists, trees and graphs. But you can easily map not only binary trees but also trees which have nodes with many children to a python dictionary. Below code shows how to create a binary tree with python dictionaries.


>>> a = {8:{"left":3,"right":10}, 3:{"left":1,"right":6}, 10:{"left":None,"right":14}, 1:{"left":None,"right":None}, 6:{"left":None,"right":None}, 14:{"left":13,"right":None}, 13:{"left":None,"right":None}}

Let’s do a breath first search with our created binary tree.

>>> queue = []
>>> root = 8
>>> queue.append(root)
>>> while(len(queue)>0):
parent = queue.pop() #remove and return the last element
if(a[parent]["left"] != None):
queue.insert(0,a[parent]["left"]) #insert the element to the 0th index
if(a[parent]["right"] != None):
queue.insert(0,a[parent]["right"])
print(parent) #Just to see how BFS go through nodes

See how easy it is. Try yourselves to write a depth first search code for above given tree. It will take only 2 or 3 minutes if you know the algorithm.

Map n-ary trees to python dictionaries

Here you have to create a python dictionary which have lists as values of dictionary keys. You will understand it after seeing the given example.
>>> tree = {"Animal":["Reptile", "Mammal"], "Reptile":["Lizard", "Snake", "Bird"], "Mammal":["Equine", "Bovine", "Canine"], "Lizard":["Salamander"]}

Just try to write a breath first search for this tree. Here you will need a for loop inside the while loop to go through each children lists.

Map graphs to python dictionaries

As you know, trees are also a special kind of graph. I took trees first because it's easy to understand these codes with trees first. Now we are going to map a graph, which have cycles, to a python dictionary. I have used a list to store even one child of some parents because it is the common solution.

>>> graph = {"A":["B"], "B":["C"], "C":["E"], "E":["F","D"], "D":["B"]}

If you need to map an undirected graph, then you just have to add both ways you can travel of each and every edges in the graph to the python dictionary. I have given a simple example below too.
>>> dir_graph = {"V1":["V2"], "V2":["V3"], "V3":["V1"]}
>>> undir_graph = {"V1":["V2"], "V2":["V1"], "V2":["V3"], "V3":["V2"], "V3":["V1"], "V1":["V3"]}

Map a weighted graph to a python dictionary

There is a special type of graphs called weighted graph in which have assigned a weight for each and every edges. Here we store each child with the weight, takes to go from the particular parent to that child, as another key value pair. So we are going to use a 2D dictionary now.

>>> w_graph = {"A":{"B":3}, "B":{"C":6,"D":1,"E":5}, "C":{"E":6}, "D":{"E":7}}

See how simple this is. Now you have to try to find the best path from A to E. Yes yes... You can find it just looking at the image. But you need to code an algorithm to find the best path between two given nodes in any weighted graph. Probably you may use a greedy solution with breath first search algorithm for that. After trying that, please refer the depth first search algorithm also.

Thanks for reading my article. Please leave a comment if you have any idea to improve this article and if you have any question. Good luck and happy coding!!!