Получить все возможные простые пути между двумя узлами (теория графов)

Question

В контексте теории графов я пытаюсь найти все возможные простые пути между двумя узлами.

Я записываю сеть, используя матрицу смежности, хранящуюся в кадре данных pandas, таким образом, что сеть [x][y] хранит значение стрелки, которое идет от x до y.

Чтобы получить пути между двумя узлами, я делаю так:

Я получаю все возможные перестановки со всеми узлами (используя it.permutations -поскольку путь прост, повторений нет). Затем я использую специальную функцию: рядом (которая дает мне соседей узла), чтобы проверить, какие из всех возможных путей являются истинными.

Это занимает слишком много времени, и это не эффективно. Вы знаете, как я могу улучшить код? Может быть с рекурсивной функцией??

По несущественной причине я не хочу использовать Networkx

def get_simple_paths(self, node, node_objective):

    # Gives you all simple path between two nodes

    #We get all possibilities and then we will filter it
    nodes = self.nodes #The list of all nodes
    possible_paths = [] #Store all possible paths
    simple_paths = [] #Store the truly paths
    l = 2        
    while l <= len(nodes):
        for x in it.permutations(nodes, l): #They are neighbourgs
            if x[0] == node and x[-1] == node_objective:
                possible_paths.append(x)
        l += 1

    # Now check which of those paths exists
    for x_pos, x in enumerate(possible_paths):
        for i_pos, i in enumerate(x): 
#We use it to check among all the path, 
#if two of the nodes are not neighbours, the loop brokes 
            if i in self.adjacencies(x[i_pos+1]):
                if i_pos+2 == len(x):
                    simple_paths.append(x)
                    break
                else:
                    continue
            else:
                break
    #Return simple paths    
    return(simple_paths)