List of linked tuple to nested dict-CodePudding

I have a list of tuples. This could look like this:

tuple_list = [
             ('species',  'flower'),
             ('flower', 'dorsal flower'),
             ('dorsal flower', 'pink'),
             ('pink', 'white'),
             ('pink', 'greenish'),
             ('species', 'branch'), 
    ]

Note: The tuples are not in order and in this example, they could also vary in order. The 'deepness' can also vary.

I would like to create a dict of dict that would look like this:

dod = {'species': {'branch':{},'flower': {'dorsal flower':{'pink': {'white':{}}, 'greenish':{}}}}}

In this case I want the species at top level, as it has no items that 'contain' species'. E.g. species contains 'flower' and 'branch' and so on.

I feel this entire process can be wrapped in a simple recursive function (e.g. yield from) instead of writing an elaborative for loop that iterates over all values.

In the end, I want to use this function to create a list of lists that contains the proper values as a list (Kudos to @Stef for this function):

def undict_to_lists(d, acc = []):
    if d == {}:
        yield acc
    else:
        for k, v in d.items():
            yield from undict_to_tuples(v, acc   [k,])

This would result in the following:

print(list(undict_to_lists(dod)))
[['species', 'branch'],
 ['species', 'flower', 'dorsal flower', 'pink', 'white'],
 ['species', 'flower', 'dorsal flower', 'greenish']]

Thanks for thinking along! All suggestions are welcome.

CodePudding user response：

You could first create a dictionary key (with {} as value) for each key that occurs in the input. Then iterate those tuples to find the value that corresponds to the start key, and populate the sub dictionary with the end key, and the subdictionary that corresponds to that end key.

Finally, derive which is the root by excluding all those nodes that are children.

tuple_list = [('species',  'flower'), ('flower', 'dorsal flower'), ('dorsal flower', 'pink'),('pink', 'white'),('pink', 'greenish'),('species', 'branch')]

d = { key: {} for pair in tuple_list for key in pair }
for start, end in tuple_list:
    d[start][end] = d[end]

root = None
for key in set(d.keys()).difference(end for _, end in tuple_list):
    root = d[key]

print(root)

CodePudding user response：

tuple_list = [
    ('species',  'flower'),
    ('flower', 'dorsal flower'),
    ('dorsal flower', 'pink'),
    ('pink', 'white'),
    ('pink', 'greenish'),
    ('species', 'branch'), 
]

# Create the nested dict,  using a "master" dict 
# to quickly look up nodes in the nested dict.
nested_dict, master_dict = {}, {}
for a, b in tuple_list:
    if a not in master_dict:
        nested_dict[a] = master_dict[a] = {}
    master_dict[a][b] = master_dict[b] = {}

# Flatten into lists.
def flatten_dict(d):
    if not d:
        return [[]]
    return [[k]   f for k, v in d.items() for f in flatten_dict(v)]

print(flatten_dict(nested_dict))
#[['species', 'flower', 'dorsal flower', 'pink', 'white'], 
# ['species', 'flower', 'dorsal flower', 'pink', 'greenish'],
# ['species', 'branch']]

CodePudding user response：

Alternative :

def find_node( tree, parent, child ):
    if parent in tree:
        tree[parent][child] = {}
        return True

    for node in tree.values():
        if find_node( node, parent, child ):
            return True
    
    # new node
    tree[parent] = { child : {} }
    
root = {}
for parent, child in tuple_list:
    find_node( root, parent, child )