Given a flat list of (parent,child), create a hierarchical dictionary tree

Question

I have a list with tuples that containing names. These names are parent and child names and I want to create a hierarchical dictionary tree with their names. For example I have the following list:

[('john','marry'),('mike','john'),('mike','hellen'),('john','elisa')]

and I want to create this:

{
    'mike':{
        'john':{
            'marry':{}
            'elisa':{}
         }
         'hellen':{}
        }
}

What should happen if there was an additional element, say `('elisa', 'mike')`? — MSeifert, Aug 02 '17 at 12:17
What have you tried so far? Where specifically are you stuck? — Cory Kramer, Aug 02 '17 at 12:19
I believe this would be wrong because mike is father of john and Hellen and john is Elisa’s father this means that Elisa is mike’s grandchildren and can't be mike's mother. — wanderer, Aug 02 '17 at 12:21
`('elisa', 'mike')` can be possible if elisa childname is mike ( new birth ) — akash karothiya, Aug 02 '17 at 12:23
I counter this exercise for a job interview and I couldn’t solve it. The exercise is exactly as I posted it ; the only thing I could think of is find the name of grandfather which in this case is mike; after that I can’t think of something to compare the rest of the names. — wanderer, Aug 02 '17 at 12:28
indeed ('elisa', 'mike') is possible, so i guess it has to go under Elisa’s name which makes it even more difficult. — wanderer, Aug 02 '17 at 12:29
Without getting into the details: Create a topological ordering of your input (the [toposort](https://pypi.python.org/pypi/toposort/1.5) package is handy for that) and walk down the `zip` of the dependency-chain and the original input to create the final output. Should take something like 20 lines. — user2722968, Aug 02 '17 at 12:44

MSeifert · Accepted Answer · 2017-08-02T12:59:37.560

Assuming it's well-behaved (no cycles, no duplicate names or multiple parents for one child) you could simply use a "directed graph" and traverse it. To find the root(s) I also used a dictionary containing a boolean that indicates if there is any parent for the name:

lst = [('john','marry'), ('mike','john'), ('mike','hellen'), ('john','elisa')]

# Build a directed graph and a list of all names that have no parent
graph = {name: set() for tup in lst for name in tup}
has_parent = {name: False for tup in lst for name in tup}
for parent, child in lst:
    graph[parent].add(child)
    has_parent[child] = True

# All names that have absolutely no parent:
roots = [name for name, parents in has_parent.items() if not parents]

# traversal of the graph (doesn't care about duplicates and cycles)
def traverse(hierarchy, graph, names):
    for name in names:
        hierarchy[name] = traverse({}, graph, graph[name])
    return hierarchy

traverse({}, graph, roots)
# {'mike': {'hellen': {}, 'john': {'elisa': {}, 'marry': {}}}}

ragardner · Answer 2 · 2017-08-02T14:14:21.403

2

alternative anyway:

data = [('john','marry'),('mike','john'),('mike','hellen'),('john','elisa')]

roots = set()
mapping = {}
for parent,child in data:
    childitem = mapping.get(child,None)
    if childitem is None:
        childitem =  {}
        mapping[child] = childitem
    else:
        roots.discard(child)
    parentitem = mapping.get(parent,None)
    if parentitem is None:
        mapping[parent] = {child:childitem}
        roots.add(parent)
    else:
        parentitem[child] = childitem

tree = {id : mapping[id] for id in roots}

print (tree)

result:

{'mike': 
        {
         'hellen': {}, 
         'john': {
                  'elisa': {}, 
                  'marry': {}}}}

Credit to @WillemVanOnsem Recursively creating a tree hierarchy without using class/object

edited Aug 02 '17 at 14:14

answered Aug 02 '17 at 13:55

ragardner

1,836
5
22
45

.mapping dict is getting updated automatically ,can you tell how its done sample : data=[['B', 'A'],['C', 'B']] 1st iteration : mapping={'B': {}, 'A': {'B': {}}} 2nd iteration : parentitem={} after last line of code was executed ,i was expecting parentitem only to change parentitem={'C': {}} The wiered behavious was mapping also got changed automatically even though the last line of code did not manully update the mapping dict how this is working ? how did the mapping dict got changed automatically ? mapping={'B': {'C': {}}, 'A': {'B': {'C': {}}}, 'C': {}} – star Jan 13 '21 at 10:57

score 1 · Answer 3 · answered Aug 02 '17 at 13:11

def get_children(parent, relations):
    children = (r[1] for r in relations if r[0] == parent)
    return {c: get_children(c, relations) for c in children}

the_list = [('john','marry'),('mike','john'),('mike','hellen'),('john','elisa')]

parents, children = map(set, zip(*the_list))
the_tree = {p: get_children(p, the_list) for p in (parents - children)}

print(the_tree)

Given a flat list of (parent,child), create a hierarchical dictionary tree

3 Answers3

Linked