Recursively traverse and build a nested dictionary of relationships-CodePudding

I have a set of objects ("A", "B", "C", "D" in example code), each of which can have relationships to other objects. I want to build a nested dictionary of those relationships.

The code below works, but is restricted to three layers of relationships. In reality I don't know the contents of rel_dict and am retrieving the relationships for e.g. object A from outside of the system (rel_dict is used to create self contained example).

I could add more for loops to assess each layer of the dictionary as its retrieved, but I don't know how many layers are required.

How could I convert this into a recursive function that will retrieve the relationships for an unknown number of layers?

# these relationships are not known, this is provided to mimic results retrieved external from system
rel_dict = {"A": ["B"], "B": ["C", "D"], "C": ["D"], "D": []}


def get_relationships(k):
    rels = rel_dict[k]
    res_dict = {}
    for r in rels:
        res_dict[r] = {}
    return res_dict


def get_relationship_dict(m):
    res_dict = {}
    res_dict[m] = {}
    res_dict[m] = get_relationships(m)

    for m2 in res_dict[m]:
        res_dict[m][m2] = get_relationships(m2)
        for m3 in res_dict[m][m2]:
            res_dict[m][m2][m3] = get_relationships(m3)

    return res_dict

Expected output

dep_dict = get_relationship_dict("B")
print(dep_dict)
{'B': {'C': {'D': {}}, 'D': {}}}

CodePudding user response：

def unpack_tree(root, dag):
    return {node: unpack_tree(node, dag) for node in dag[root]}

def get_relationship_dict(m, dag):
    return {m: unpack_tree(m, dag)}

And with your example:

>>> get_relationship_dict("B", rel_dict)
{'B': {'C': {'D': {}}, 'D': {}}}
>>>

Beware that, if your relationship has a cycle, this code would logically never end, but in practice in it will raise an exception.

Besides that, here is a utility class that you can use to mimic a dictionary interface even though you don't actually get your data as a dictionary. It's efficient, in the sense that it will only query the information it needs, and it will do that at most once.

class ExternalDict(dict):
    def __init__(self, f):
        super().__init__()
        self._f = f
    def __getitem__(self, key):
        if key not in self:
            self[key] = self._f(key)
        return super().__getitem__(key)

This is to be used like that:

>>> def fetch_relationship(k):
...     return rel_dict[k] # in reality, something else
>>> get_relationship_dict(ExternalDict(fetch_relationship))
{'B': {'C': {'D': {}}, 'D': {}}}
>>>