Collapsing dictionary by merging matching keys and key,value pairs

Question

So I am trying to find a way to "merge" a dependency list which is in the form of a dictionary in python, and I haven't been able to come up with a solution. So imagine a graph along the lines of this: (all of the lines are downward pointing arrows in this directed graph)

1   2   4
 \ /   / \
  3   5   8
   \ / \   \
    6   7   9

this graph would produce a dependency dictionary that looks like this:

{3:[1,2], 5:[4], 6:[3,5], 7:[5], 8:[4], 9:[8], 1:[], 2:[], 4:[]}

such that keys are nodes in the graph, and their values are the nodes they are dependent on. I am trying to convert this into a total ancestry list in terms of a tree, so that each node is a key, and its value is a list of ALL nodes that lead to it, not just it's immediate parents. The resulting dictionary would be:

{3:[1,2], 5:[4], 6:[3, 5, 1, 2, 4], 7:[5, 4], 8:[4], 9:[8, 4], 1:[], 2:[], 3:[]}

Any suggestions on how to solve this? I have been banging my head into it for a while, tried a recursive solution that I haven't been able to get working.

Answer 1

You can use a chained dict comprehension with list comprehension for up to two nodes.

>>> {k: v + [item for i in v for item in d.get(i, [])] for k,v in d.items()}

{3: [1, 2],
 5: [4],
 6: [3, 5, 1, 2, 4],
 7: [5, 4],
 8: [4],
 9: [8, 4],
 1: [],
 2: [],
 4: []}

---

For unlimited depth, you can use a recursive approach

def get_ant(node, d):
    if node:
        return d.get(node,[]) + [item for x in d.get(node, []) for item in get_ant(x, d) ]
    return []

Then,

>>> get_ant(6, d)
[3, 5, 1, 2, 10, 4]

To get all cases:

>>> {k: get_ant(k, d) for k in d.keys()}

{3: [1, 2, 10],
 5: [4],
 6: [3, 5, 1, 2, 10, 4],
 7: [5, 4],
 8: [4],
 9: [8, 4],
 1: [10],
 2: [],
 4: []}

Answer 2

Here's a really simple way to do it.

In [22]: a
Out[22]: {1: [], 2: [], 3: [1, 2], 4: [], 5: [4], 6: [3, 5], 7: [5], 8: [4], 9: [8]}

In [23]: final = {}

In [24]: for key in a:   
    ...:     nodes = set()
    ...:         
    ...:     for val in a[key]:
    ...:         nodes.add(val)
    ...:         if val in a:
    ...:             nodes.update(set(a[val]))
    ...:             
    ...:     final[key] = list(nodes)

In [25]: final
Out[25]: 
{1: [],
 2: [],
 3: [1, 2],
 4: [],
 5: [4],
 6: [3, 1, 2, 5, 4],
 7: [5, 4],
 8: [4],
 9: [8, 4]}