Sort into sub dictionary?-CodePudding

I have an array which shows the connection between joints,
something like this:

[
("Pelvis","Torso"),
("Torso","Head"),
("Torso","Biscep.L"),
("Biscep.L","Forearm.L"),
("Forearm.L","Hand.L"),
("Pelvis","")
("Pelvis","Thigh.L"),
("Thigh.L","Shin.L"),
("Shin.L","Heel.L"),
("Heel.L","Toe.L"),
("Torso","Biscep.R"),
("Biscep.R","Forearm.R"),
("Forearm.R","Hand.R"),
("Pelvis","Thigh.R"),
("Thigh.R","Shin.R"),
("Shin.R","Heel.R"),
("Heel.R","Toe.R"),
]

I'm trying to sort it in such that the values do not repeat and are placed one within the other like this:

{
"Pelvis":{
    "Torso":{
        "Biscep.L":{
            "Forearm.L":{
                "Hand.L":{}
            }
        },
        "Head":{},
        "Thigh.L":{},
    },
...
}

How do I achieve this?

CodePudding user response：

This can be handled as a graph problem. I would use

Assuming L the input, you can build it with networkx.from_edgelist, then find the connected_components and loop over the first of all_simple_edge_paths (assuming you have no branches):

import networkx as nx

# build directed graph
G = nx.from_edgelist((t for t in L if t[0] and t[1]), # drop empty strings
                     create_using=nx.DiGraph)

# to find roots and leafs
IN = G.in_degree()
OUT = G.out_degree()

# complete dictionary
out = {}

for sub in nx.weakly_connected_components(G):
    root = next(n for n in sub if IN[n] == 0)  # get root
    leafs = [n for n in sub if OUT[n] == 0]    # get leafs
    for path in nx.all_simple_edge_paths(G, root, leafs):
        d = out
        for parent, child in path:
            d.setdefault(parent, {child: {}})
            d = d[parent]
        d.setdefault(child, {})

output dictionary (out):

{'Pelvis': {'Thigh.L': {'Shin.L': {'Heel.L': {'Toe.L': {}}}},
            'Thigh.R': {'Shin.R': {'Heel.R': {'Toe.R': {}}}},
            'Torso': {'Biscep.L': {'Forearm.L': {'Hand.L': {}}},
                      'Biscep.R': {'Forearm.R': {'Hand.R': {}}},
                      'Head': {}}}}