I'm working with a breadth-first-search algorithm (networkx) and working on analyzing the results. There are 2 dictionaries that are relevant in this situation. First contains the edges (e.g. (4, 7): connection between node 4 and 7) as keys and the levels (e.g. 1: how many steps were needed to reach this edge) as values. The second dictionary contains also the levels but as keys and the nodes as values (e.g. 1: [4, 8, 9, 6]: meaning that after 1 step the nodes 4, 8, 9 and 6 are reached).

Now my goal is to receive a dictionary with nodes as keys and nodes that are reached from that key (node) as values (like: 7: [4, 8, 9, 6], 4: [5, 3], and so on.

For better understanding:

sorted_edges = {
(4, 7): 1,
(6, 7): 1,
(7, 8): 1,
(7, 9): 1,
(3, 4): 2,
(4, 5): 2,
(8, 10): 2,
(1, 3): 3,
(2, 3): 3,
(3, 11): 3,
(2, 15): 4,
(11, 12): 4,
(11, 13): 4,
(12, 14): 5,
(15, 16): 5}

levels = {
0: [7], 1: [4, 8, 9, 6], 2: [3, 5, 10], 3: [2, 1, 11], 4: [15, 12, 13], 5: [16, 14]}

0: [7] means that node 7 is the source of the search algorithm and that is starts here.

And it should look like this:

res = 
{
7: [4, 8, 9, 6],
4: [5, 3],
8: [10],
9: [],
6: [],
10: [],
5: [],
3: [1, 2, 11],
1: [],
2: [15],
11: [12, 13],
15: [16],
12: [14],
13: []
}

I tried it with several for-loops where unfortunately 2 problems occur.

res = {}

for key, value in sorted_edges.items():

    for ki, val in levels.items():

        if value == ki:

            for i in key:

                for j in val:

                    if i == j:

                        # res.update({[{"{0}".format(value)}]: j}) # second idea
                        res["{0}".format(i)].append(j) # first idea

First problem is that with both ideas there will be the wrong key for the new dict res. Here key is a tuple of 2 numbers and the variable i is iterating through both of them, if one of them is the same like j (also one number of a 2-numbers tuple), j should be the value of the new dict res, but the problem is the key. Because that should be the other number of key and not i. Here key = (4, 7) and i equals 4, when the if statement is true than the other number (7) should be assigned to be the key of res.

Second problem is that with the first idea the error: Exception has occurred: KeyError X '4' appears. The second idea delivers the error: Exception has occurred: TypeError X unhashable type: 'list'

The dictionaries can vary for different types of graphs from the bfs.

CodePudding user response：

I might not understood your problem description exactly but if I did not miss any assumptions about input following code should work

reached = defaultdict(set)
for (a, b) in sorted_edges:
    reached[a].add(b)
    reached[b].add(a)

result = {}
for i in range(1, len(levels)):  
    for x in levels[i - 1]:
        result[x] = reached[x].intersection(set(levels[i]))