Python code: Nested dictionary with lambda functions (revisited)

1 minute read

Published:

Previously in the post about Python code: Nested dictionary with lambda functions the nested dictionary was introduced, such that no prior knoedge of keys is required, only the number of levels.

This post extends the previous post for a specific, but quite common user-oriented example.

Motivation: Lets have a user interacting with a graph. Graphs are usually built from data and stored as adjancency matrix. But what is the graph is too sparse and there are no data, only the users input?

In such case, the interaction of the user with the graph is easier through a list representation of the graph. Rather than a large matrix, the list stores only the vertices and edges. From the user perspective, the ideally simplified input requires only a pairs of nodes, which are connected by a vertex.

user_input = [	[1,2], # vertex between node #1 and node #2
		[2,3], # vertex between node #2 and node #3
		[3,1]] # vertex between node #3 and node #1

Notice, the user specifies the existance of the edge with single direction only and requiring the user to specify the other direction is error-prone and essentially doubles the work on the user side.

Question: How to translate the user_input into a list representation of bidirectional graph?

from collections import defaultdict
# two levels deep nested dictionary with empty list at the end
graph_list = defaultdict( list )

for edge in user_input:
	node_0 = edge[0]
	node_1 = edge[1]
	# define bidirectional edge as 2 opposing unidirectional
	graph_list[node_0].append(node_1) # unidirectional edge
	graph_list[node_1].append(node_0) # unidirectional edge

Lets see the output using pretty() defined in the previous post, which yields the following list representation of bidirectional graph:

1
	[2, 3]
2
	[1, 3]
3
	[2, 1]