Sometimes while working with Python pairs, we can have problem in which pairs represent the neighbours and we need to compute neighbors of each element. This kind of problem is quite common in competitive programming and while working with graphs. Lets discuss certain ways in which this task can be performed.
Method #1 : Using loop
This is one of the approach that can be applied to solve this problem. In this, we presume the required keys and construct the dictionary with empty lists, and iterate the pair list appending the values.
Python3
# Python3 code to demonstrate working of # Paired Neighbours to Adjacency Dictionary# Using loop# initializing listtest_list = [(1, 2), (4, 5), (1, 3), (3, 4), (5, 6), (6, 2)]# printing original listprint("The original list is : " + str(test_list))# Paired Neighbours to Adjacency Dictionary# Using loopres = {1: [], 2: [], 3: [], 4: [], 5: [], 6: []}for sub in test_list: res[sub[0]].append(sub[1]) res[sub[1]].append(sub[0]) # printing result print("The Neighbours Paired Dictionary : " + str(res)) |
The original list is : [(1, 2), (4, 5), (1, 3), (3, 4), (5, 6), (6, 2)] The Neighbours Paired Dictionary : {1: [2, 3], 2: [1, 6], 3: [1, 4], 4: [5, 3], 5: [4, 6], 6: [5, 2]}
Time Complexity: O(n) where n is the total number of values in the list “test_list”.
Auxiliary Space: O(n) where n is the total number of values in the list “test_list”.
Method #2 : Using defaultdict() + loop
The combination of above functions can also be used to solve this problem. In this, we initialize the dictionary as default set. The eliminates the problem of duplicacy and also gives more flexibility regarding more undetermined node values.
Python3
# Python3 code to demonstrate working of # Paired Neighbours to Adjacency Dictionary# Using defaultdict() + loopfrom collections import defaultdict# initializing listtest_list = [(1, 2), (4, 5), (1, 3), (3, 4), (5, 6), (6, 2)]# printing original listprint("The original list is : " + str(test_list))# Paired Neighbours to Adjacency Dictionary# Using defaultdict() + loopres = defaultdict(set)for sub in test_list: res[sub[0]].add(sub[1]) res[sub[1]].add(sub[0]) # printing result print("The Neighbours Paired Dictionary : " + str(dict(res))) |
The original list is : [(1, 2), (4, 5), (1, 3), (3, 4), (5, 6), (6, 2)] The Neighbours Paired Dictionary : {1: {2, 3}, 2: {1, 6}, 3: {1, 4}, 4: {3, 5}, 5: {4, 6}, 6: {2, 5}}
Time Complexity: O(n*n), where n is the length of the input list. This is because we’re using the using defaultdict() + loop which has a time complexity of O(n*n) in the worst case.
Auxiliary Space: O(n), as we’re using additional space res other than the input list itself with the same size of input list.
Method 3: use a dictionary comprehension to build the adjacency dictionary
Python3
# Python3 code to demonstrate working of# Paired Neighbours to Adjacency Dictionary# Using dictionary comprehension# initializing listtest_list = [(1, 2), (4, 5), (1, 3), (3, 4), (5, 6), (6, 2)]# printing original listprint("The original list is : " + str(test_list))# Paired Neighbours to Adjacency Dictionary# Using dictionary comprehensionres = {i: [] for i in set(sum(test_list, ()))}for a, b in test_list: res[a].append(b) res[b].append(a)# printing resultprint("The Neighbours Paired Dictionary : " + str(res)) |
The original list is : [(1, 2), (4, 5), (1, 3), (3, 4), (5, 6), (6, 2)]
The Neighbours Paired Dictionary : {1: [2, 3], 2: [1, 6], 3: [1, 4], 4: [5, 3], 5: [4, 6], 6: [5, 2]}
Time complexity: O(n), where n is the length of the input list.
Auxiliary space: O(n), where n is the length of the input list, because we need to store the adjacency dictionary.
