CODEWITHSUNDEEP
python
xpanta
xpanta

Reputation: 8418

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

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)

Upvotes: 2

Views: 1048

Answers (4)

ncica
ncica

Reputation: 7206

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]

Upvotes: 1

wim
wim

Reputation: 362806

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}

Upvotes: 1

Andrej Kesely
Andrej Kesely

Reputation: 195458

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]

Upvotes: 1

Amitai Irron
Amitai Irron

Reputation: 2055

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.

Upvotes: 1

Related Questions