Python method for returning all possible paths in a graph class (DAG)-CodePudding

I have a question surrounding find all the paths in a directed acyclic graph from a source to a destination. For this, I made two custom classes that act as Node and Graph. The Graph class reads a proximity matrix to create the nodes and add the connections in a dictionary.
After this, I want to be able to find all the possible paths from a source to a destination using a recursion and returning them with a generator but I am having problems with the recursive call, as its not properly navigating the paths.
The AllPathUtils method is not moving past the first method call. This is pretty much my code and I would really appreciate if one of you could point the dumb mistake that Im missing. At the bottom I will leave some example inputs, so you can check the exact behaviour. Thanks a lot.

class Node:
    def __init__(self, identity):
       self.name = identity

    def get_name(self):
        return self.name

    def __hash__(self):
        return hash(self.get_name())

    def __eq__(self, other):
       return self.get_name() == other.get_name()

    def __ne__(self, other):
        return not self == other

    def __str__(self):
        return f"Node -> {self.get_name()}"

    def __repr__(self):
        return f"Node -> {self.get_name()}"


class Graph:
    def __init__(self, matrix_graph):
        self.graph = {}
        self.V = len(matrix_graph)
        i = 0
        for node in matrix_graph:
            x = Node(i)
            self.graph[x] = []
            j = 0
            for adj in node:
                if matrix_graph[i][j] != 0:
                    self.graph[x].append(Node(j))
                j  = 1
            i  = 1

    def AllPathsUtil(self, u, d, visited, path):
        visited[u.get_name()] = True
        path.append(u)
        if u == d:
            yield path
        else:
            for i in self.graph[u]:
                if visited[i.get_name()] is False:
                    self.AllPathsUtil(i, d, visited, path)
        path.pop()
        visited[u.get_name()] = False

    def printAllPaths(self, s, d):
        visited = [False] * (self.V)
        path = []
        for el in self.AllPathsUtil(s, d, visited, path):
            print(el)



matrix2 = [[0, 1, 0, 0, 0, 0],
       [0, 0, 1, 1, 0, 0],
       [0, 0, 0, 0, 1, 0],
       [0, 0, 0, 0, 1, 0],
       [0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 1, 0]]

z = Graph(matrix2)
z.printAllPaths(Node(0), Node(4))

CodePudding user response：

For anyone having the same problem as me, the mistake was that I needed to yield from the recursive call, otherwise it wouldnt work. This was the problematic line:

self.AllPathsUtil(i, d, visited, path)

While this is the correct one:

yield from self.AllPathsUtil(i, d, visited, path)