Graph challenge: Get adjacency list from list of children nodes

Question

I have a graph which has the following structure:

{'a':['b','c','d','e'],
'b':['d'],
'c':['d','e'],
'd':[],
'e':[],
'f':['i','j','c','e','d'],
'i':['c','e','d']
'j':['e']}

This list is not an adjacency list as it contains all the children of a node. Not the direct children.

the graph is supposed to look like this:

        a       f     
       / \     / \
      b   \   i   j
       \   \ /   /    
        \   c   /
         \ / \ /
          d   e

So the adjacecy list would look like:

{'a':['b','c'],
'b':['d'],
'c':['d','e'],
'd':[],
'e':[],
'f':['i','j'],
'i':['c'],
'j':['e']}

I need an algorithm to do this. The algorithm should be as fast as can be using minimum extra space. Anybody who can solve this?

Thanks!

Answer 1

Not quite recursive, but you could iterate through each child, look it up, and remove all of its children from the current node:

def get_adjacency(graph):
    graph = {node: set(children) for node, children in graph.items()}

    for node, children in graph.items():
        for child in children:
            children = children - graph[child]
        graph[node] = children

    return {node: list(children) for node, children in graph.items()}

c = {
    'a': ['b','c','d','e'],
    'b': ['d'],
    'c': ['d','e'],
    'd': [],
    'e': [],
    'f': ['i','j','c','e','d'],
    'i': ['c','e','d'],
    'j': ['e']
}

print get_adjacency(c)