Calculating Source Path based on source-destination dictionary

Question

I have an input dictionary - dict_input that has destinations as keys and sources as values. One destination can have one or more sources.

dict_input = {'C411':['C052'],'C052':['C001','C002'], 'C001':['9001'], 'C002':['9002']}

In above dict_input, the terminal destination is C411 whereas the initial sources are 9001 and 9002. I am trying to come up with source paths for the terminal destination C411. Expected output in the form of list -

[['C411', 'C052', 'C001', '9001'], ['C411', 'C052','C002', '9002']]

I have this code:

def get_source(node, dict_input, source=[]):
    if node in dict_input:
        source.append(node)
        for i in dict_input[node]:
            if i != node:
                get_source(i, dict_input, source)
            else:
                source.append(node)
    else:
        source.append(node)
        return source
    return source

dict_input = {'C052':['C001','C002'], 'C411':['C052'], 'C001':['9001'], 'C002':['9002']} 

print(get_source('C411', dict_input, []))

The output is the two source paths clubed into a single list -

['C411', 'C052', 'C001', '9001', 'C002', '9002']

How do I modify my code to get separate list of each source path?

Answer 1

• Don't forget to pop from the current path when you have finished visiting a node
• If you come across a "leaf" (a node ID which is not a key), store a copy of the current path in output list
• Be wary of corrupt data e.g. cyclic links - would be useful to keep a set of visited nodes

Sample implementation of the above:

def get_source(root, dict_input):

    # output list
    path_list = []

    # current path
    cur_path = []

    # visited set
    visited = set()

    # internal recursive helper function
    def helper(node):
        cur_path.append(node)

        # normal node
        if node in dict_input:
            if not node in visited:
                visited.add(node)
                for child in dict_input[node]:
                    helper(child)

            # else: cycle detected, raise an exception?

        # leaf node
        else:
            # important: must be a copy of the current path
            path_list.append(list(cur_path))

        cur_path.pop()

    # call this helper function on the root node
    helper(root)

    return path_list

Test:

>>> dict_input = {'C411':['C052'],'C052':['C001','C002'], 'C001':['9001'], 'C002':['9002']}

>>> get_source('C411', dict_input)
[['C411', 'C052', 'C001', '9001'], ['C411', 'C052', 'C002', '9002']]