List all paths in a directed graph

Question

I have some graph where the depthFirst search I found here doesn't work. My nodes don't directly lead to another node, but look like this:

graph = {
    'type1': {'varname1': ['type2', 'comment1'], 'varname7': ['none', 'comment7']},
    'type2': {
        'varname2': ['type3', 'comment2'],
        'varname3': ['type3', 'comment3'],
        'varname4': ['none', 'comment4']
    },
    'type3': {'varname5': ['none', 'comment5']}
}

The goal is: I want to lookup a type and only get the variable names of the path back. (Let's ignore the comments now) For type1 it would be:

[
    ['varname1', 'varname2', 'varname5'],
    ['varname1', 'varname3', 'varname5'],
    ['varname1', 'varname4'],
    ['varname7']
]

Different variables can have the same type. For example varname2 and varname3 both lead to type3. That's why I need both. If a type isn't found, for example 'none', then the path should just end with that variable. The same should work for the comments, get them in the same list format as the variable names.

I tried to adapt the depth first search, but I can't get it working. Either visited contains too many elements, or not enough.

visitedList = []

def depthFirst(graph, currentVertex, visited):
    next_node = graph.get(currentVertex)
    if next_node:
        for type_name, var_name in next_node.items():
            visited.append(type_name)
            depthFirst(graph, var_name[0], visited.copy())
    else:
        visitedList.append(visited.copy())
        visited.pop()

depthFirst(graph2, 'type1', [])

The initial graph doesn't have to be in that exact format. I could structure it differently if that helps.

Answer 1

Try:

graph = {
    "type1": {"varname1": ["type2", "comment1"], "varname7": ["none", "comment7"]},
    "type2": {
        "varname2": ["type3", "comment2"],
        "varname3": ["type3", "comment3"],
        "varname4": ["none", "comment4"],
    },
    "type3": {"varname5": ["none", "comment5"]},
}


def traverse(graph, node, current=None):
    if current is None:
        current = []

    for k, (t, _) in graph.get(node, {}).items():
        if t == "none":
            yield current + [k]
        else:
            yield from traverse(graph, t, current + [k])


out = list(traverse(graph, "type1"))
print(out)

Prints:

[
    ["varname1", "varname2", "varname5"],
    ["varname1", "varname3", "varname5"],
    ["varname1", "varname4"],
    ["varname7"],
]