how to find all children for all keys in a dictionary with Python

user_356875 0
Viewed 416

I have a dictionary like this:

{
1: [6,8,10],
2: [3,4],
5: [11],
6: [9,13],
13: [14],
}

I would like to traverse each key-value pair and for each key find all children and create this (e.g. for key=1) [6,8,10,9,13,14] (because 6->[9,13] and 13->[14]

i tried this recursion code but failed:

def get_all_children(key):
    try:
        arr = _dict[key]
    except KeyError:
        return []
    for item in arr:
        return arr + get_all_children(item)
python
4 Answers

It can be done without recursion (assuming there aren't any loops in your dictionary):

d = {
    1: [6,8,10],
    2: [3,4],
    5: [11],
    6: [9,13],
    13: [14],
}

key = 1

vals, out = d[key][:], []
while vals:
    v = vals.pop()
    out.append(v)
    vals.extend(d.pop(v, []))

print(out)

Prints:

[10, 8, 6, 13, 14, 9]

With v = vals.pop(0) the result is the same, but different order:

[6, 8, 10, 9, 13, 14]
user_100359850

You have a return in a loop. What you actually want to do is extend the result in the loop, and return it afterward.

There is another thing you should do, though, which is to prevent endless recursion, in case you graph (the dictionary with adjacency lists) has cycles. You see, what you are trying to achieve here is a well know graph algorithm call Breadth First Search (BFS). You can find canonical implementations for that all over the internet.

user_40225800

Using a graphing library, you can create a graph directly from your dict unchanged:

d = {
    1: [6,8,10],
    2: [3,4],
    5: [11],
    6: [9,13],
    13: [14],
}

Then the "find all children" you describe is usually termed the descendants of a node:

>>> import networkx as nx
>>> g = nx.Graph(d)
>>> nx.descendants(g, 1)
{6, 8, 9, 10, 13, 14}
user_6740390

you can do it with basic for loop. you dont need to use try-expect block to handle if key doesnt exist in dictionary, for that you can use get function which will return None if key doesnt exist.

data = {
1: [6,8,10],
2: [3,4],
5: [11],
6: [9,13],
13: [14],
}


for key,value in data.items():
    result = value.copy()
    for item in result:
        if data.get(item):
            result.extend(data[item])
    print (key, result)

output:

1 [6, 8, 10, 9, 13, 14]
2 [3, 4]
5 [11]
6 [9, 13, 14]
13 [14]
user_109672040
Related