Extract all chains from a tree data structure

Question

I have a data dictionary like this:

dic = '{"data":"Harry", 
        "children":[{"data":"Bill",
                     "children":[]},
                    {"data":"Jane",
                     "children":[{"data":"Diane",
                                  "children":[]},
                                 {"data":"Mark",
                                  "children":[]}]
                    }
                   ]
       }'

I want to extract all the chains included in the tree hierarchy separately i.e. all the complete paths from the first node to every last node:

• Harry -> Bill
• Harry -> Jane -> Diana
• Harry -> Jane -> Mark

I extracted the tree edges from the dictionary using this code:

from __future__ import print_function
import json
import sys
from treelib import Node, Tree

data = '{"data":"Harry", "children":[{"data":"Bill","children":[]},{"data":"Jane","children":[{"data":"Diane","children":[]},{"data":"Mark","children":[]}]}]}'
data = json.loads(data)

# Extract tree edges from the dict
edges = []
tree = Tree()
added = set()

def get_edges(treedict, parent=None):
    name = treedict['data']
    added.add(name)

    if parent is not None:
        edges.append((parent, name))

    for item in treedict["children"]:
        if isinstance(item, dict):
            get_edges(item, parent=name)

get_edges(data)

#Dump edge list in Graphviz DOT format
print('strict digraph tree {')
for row in edges:
    print('    {0} -> {1};'.format(*row))
print('}')

The tree edges list looks like this:

[(u'Harry', u'Bill'), (u'Harry', u'Jane'), (u'Jane', u'Diane'), (u'Jane', u'Mark')]

It can be used to print the tree.

Is there anyway to get the chains using the data dictionary or the tree edges list?

Answer 1

Instead of passing one parent pass a tuple of parents:

    from __future__ import print_function
    import json
    import sys
    from treelib import Node, Tree

    data = '{"data":"Harry", "children":[{"data":"Bill","children":[]},{"data":"Jane","children":[{"data":"Diane","children":[]},{"data":"Mark","children":[]}]}]}'
    data = json.loads(data)

    # Extract tree edges from the dict
    edges = []
    tree = Tree()
    added = set()


    def get_edges(treedict, parent=()):
        name = treedict['data']
        added.add(name)

        if parent is not None and not treedict["children"]:
            edges.append((parent)+(name,))

        for item in treedict["children"]:
            if isinstance(item, dict):
                get_edges(item, parent=parent + (name,))

    get_edges(data)

    #Dump edge list in Graphviz DOT format
    print('strict digraph tree {')
    for row in edges:
        print('-->'.join(row))
    print('}')

output:

strict digraph tree {
    Harry-->Bill
    Harry-->Jane-->Diane
    Harry-->Jane-->Mark
}