Как пройти через пути переменной длины к тому же месту назначения?

Question

У меня есть направленная сеть следующим образом.

Теперь я хотел бы получить все возможные пути 4 длины и 5 длин этогографик (где начальный и конечный пути - B)

Примеры 4 путей длины:

• B - C - B - A - B
• B - A - B - B - B
• B - A - B - C - B

Примеры 5 путей длины;

• B - C - B - A - B - B
• B - A - B - B - C - B

Я попытался использовать Breadth First Search (BFS), чтобы решить эту проблему.Похоже, большая часть кода алгоритма BFS не удовлетворяет моим требованиям.То есть

• Они не учитывают пути переменной длины
• Их начальный и конечный узлы не совпадают с моими (они разные)

Myтекущий код выглядит следующим образом:

graph = {'A': ['B'],
         'B': ['A','C', 'B'],
         'C': ['B']}

# visits all the nodes of a graph (connected component) using BFS
def bfs_connected_component(graph, start):
   # keep track of all visited nodes
   explored = []
   # keep track of nodes to be checked
   queue = [start]

   # keep looping until there are nodes still to be checked
   while queue:
       # pop shallowest node (first node) from queue
       node = queue.pop(0)
       if node not in explored:
           # add node to list of checked nodes
           explored.append(node)
           neighbours = graph[node]

           # add neighbours of node to queue
           for neighbour in neighbours:
               queue.append(neighbour)
   return explored

bfs_connected_component(graph,'A')

Я хотел бы знать, есть ли какие-либо библиотеки Python, которые я могу использовать для этого, или есть способ изменить BFS для решения этой проблемы.

Я рад предоставить больше примеров, если это необходимо:)

Answer 1

При поиске всех комбинаторных результатов я обнаружил, что рекурсивные генераторы в python предоставляют более компактный и понятный код по сравнению с другими подходами (такими как рекурсивные функции или эквиваленты на основе стека).

Здесь мы ищем все пути от node до goal фиксированных length. Список path используется в качестве аккумулятора, который в базовом случае становится префиксом прохождения 1-го пути через node.

def all_paths(graph, node, goal, length, path=[]):
    if length == 0 and node == goal:
        yield path + [node]
    elif length > 0:
        for n in graph[node]:
            yield from all_paths(graph, n, goal, length - 1, path + [node])

Дорожки длины 4:

>>> print(*all_paths(graph, 'B', 'B', 4), sep='\n')
['B', 'A', 'B', 'A', 'B']
['B', 'A', 'B', 'C', 'B']
['B', 'A', 'B', 'B', 'B']
['B', 'C', 'B', 'A', 'B']
['B', 'C', 'B', 'C', 'B']
['B', 'C', 'B', 'B', 'B']
['B', 'B', 'A', 'B', 'B']
['B', 'B', 'C', 'B', 'B']
['B', 'B', 'B', 'A', 'B']
['B', 'B', 'B', 'C', 'B']
['B', 'B', 'B', 'B', 'B']

Дорожки длиной 5:

>>> print(*all_paths(graph, 'B', 'B', 5), sep='\n')
['B', 'A', 'B', 'A', 'B', 'B']
['B', 'A', 'B', 'C', 'B', 'B']
['B', 'A', 'B', 'B', 'A', 'B']
['B', 'A', 'B', 'B', 'C', 'B']
['B', 'A', 'B', 'B', 'B', 'B']
['B', 'C', 'B', 'A', 'B', 'B']
['B', 'C', 'B', 'C', 'B', 'B']
['B', 'C', 'B', 'B', 'A', 'B']
['B', 'C', 'B', 'B', 'C', 'B']
['B', 'C', 'B', 'B', 'B', 'B']
['B', 'B', 'A', 'B', 'A', 'B']
['B', 'B', 'A', 'B', 'C', 'B']
['B', 'B', 'A', 'B', 'B', 'B']
['B', 'B', 'C', 'B', 'A', 'B']
['B', 'B', 'C', 'B', 'C', 'B']
['B', 'B', 'C', 'B', 'B', 'B']
['B', 'B', 'B', 'A', 'B', 'B']
['B', 'B', 'B', 'C', 'B', 'B']
['B', 'B', 'B', 'B', 'A', 'B']
['B', 'B', 'B', 'B', 'C', 'B']
['B', 'B', 'B', 'B', 'B', 'B']