Получить возможные пути

Question

У меня есть простая структура данных, показывающая узлы в ориентированном графе:

{
    'node1': [('V1', 'R1')],
    'node2': [('R1', 'R2'), ('R1', 'R3')],
    'node3': [('R2', 'R4'), ('R2', 'R5'), ('R3', 'R4'), ('R3', 'R5')],
    'node4': [('R4', 'Z1')],
    'node5': [('R5', 'Z1')]
}

Я хотел бы получить все возможные (направленные) пути от V1 до Z. Например, путь может быть:

[
    ('V1', 'R1'),
    ('R1', 'R2'),
    ('R2', 'R4'),
    ('R4', 'Z1')
]

Тем не менее, у меня возникли проблемы с алгоритмом, основанным на принципе c, который, я считаю, включает в себя рекурсию.

for node, connections in nodes.items():
    for connection in connections:

Я начал с чего-то подобного, но думаю, что это неправильный подход. Каков был бы предложенный способ сделать это, не используя что-то вроде itertools?

Answer 1

Учитывая, что кортежи в структуре данных являются ребрами, а значения в кортежах являются узлами графа, можно реорганизовать данные таким образом, чтобы упростить алгоритм:

graph = [edge for es in source.values() for edge in es]

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

def find_path(start, end, edges, visited=None):
    if visited is None:
        visited = []
    for n1, n2, in edges:
        if n1 == start:
            if n2 == end:
                yield [n1, n2]
            elif n2 not in visited:
                for continuation in find_path(n2, end, edges, visited + [n1]):
                    yield [n1] + continuation

Все:

source = {
    'node1': [('V1', 'R1')],
    'node2': [('R1', 'R2'), ('R1', 'R3')],
    'node3': [('R2', 'R4'), ('R2', 'R5'), ('R3', 'R4'), ('R3', 'R5')],
    'node4': [('R4', 'Z1')],
    'node5': [('R5', 'Z1')]
}

graph = [edge for es in source.values() for edge in es]


def find_path(start, end, edges, visited=None):
    if visited is None:
        visited = []
    for n1, n2, in edges:
        if n1 == start:
            if n2 == end:
                yield [n1, n2]
            elif n2 not in visited:
                for continuation in find_path(n2, end, edges, visited + [n1]):
                    yield [n1] + continuation


print(list(find_path('V1', 'Z1', graph)))

Вывод:

[['V1', 'R1', 'R2', 'R4', 'Z1'], ['V1', 'R1', 'R2', 'R5', 'Z1'], ['V1', 'R1', 'R3', 'R4', 'Z1'], ['V1', 'R1', 'R3', 'R5', 'Z1']]

Обратите внимание, что результат приводится к списку, поскольку функция является генератором, она выдает решения по одному за раз. Вызов list() собирает все результаты в один вывод.

Answer 2

Вы можете использовать рекурсию с генератором:

data = {'node1': [('V1', 'R1')], 'node2': [('R1', 'R2'), ('R1', 'R3')], 'node3': [('R2', 'R4'), ('R2', 'R5'), ('R3', 'R4'), ('R3', 'R5')], 'node4': [('R4', 'Z1')], 'node5': [('R5', 'Z1')]}
new_data = [i for b in data.values() for i in b]
def lookup(start, end, seen=[], c = []):
   _r = [(a, b) for a, b in new_data if a == start and a not in seen]
   for a, b in _r:
      if b == end:
         yield c+[(a, b)]
      else:
         yield from lookup(b, end, seen=seen+[start], c=c+[(a, b)])

print(list(lookup('V1', 'Z1')))

Выход:

[
  [('V1', 'R1'), 
   ('R1', 'R2'), 
   ('R2', 'R4'), 
   ('R4', 'Z1')], 
  [('V1', 'R1'),  
   ('R1', 'R2'), 
   ('R2', 'R5'), 
   ('R5', 'Z1')], 
  [('V1', 'R1'), 
   ('R1', 'R3'), 
   ('R3', 'R4'), 
   ('R4', 'Z1')], 
  [('V1', 'R1'), 
   ('R1', 'R3'), 
   ('R3', 'R5'), 
   ('R5', 'Z1')]
]

Answer 3

Следующее решение гораздо менее элегантно и более многословно, чем два других решения, но вот пример реализации, расширяющий различные функции:

def flatten_list(l, out=None):
    """
    Flatten to get a list of all edges:

    in:  [[('V1', 'R1')], [('R1', 'R2'), ('R1', 'R3')]
    out: [('V1', 'R1'), ('R1', 'R2'), ('R1', 'R3')]
    """
    if out is None: out=[]
    for li in l:
        if not isinstance(li, list):
            out.append(li)
        else:
            flatten_list(li, out)
    return out


def get_connected_nodes_from(list_of_edges, from_node):
    """
    Given an input node (string), and list of edges (tuple),
    Return a list of all nodes (list of strings) connected to the input node.
    Note: this is a directed graph. That is, we are only grabbing descendants
          and not all (undirected) edges.

    in:  from_node='R1', list_of_edges=[('V1', 'R1'), ('R1', 'R2'), ('R1', 'R3')]
    out: ['R2', 'R3']
    """
    out = []
    for edge in list_of_edges:
        if edge[0] == from_node:
            out.append(edge[1])
        elif from_node == edge[0]:
            out.append(edge[0])
    return out


def get_all_paths(list_of_edges, node=None, current_path=None, all_paths=None):
    """
    Given a list of edges, this will return all directed paths from start to finish.
    """
    # "Initialize" things on the first time through
    if all_paths is None: all_paths = []; node = list_of_edges[0][0]; current_path = [node,]
    node_descendants = get_connected_nodes_from(list_of_edges, node) 
    if len(node_descendants) == 0:
        all_paths.append(current_path) # append the path when it is a leaf with no descendants
    else:
        [get_all_paths(list_of_edges, node, current_path + [node,], all_paths) for node in node_descendants]
    return all_paths

И использующий его:

>>> graph = {
    'node1': [('V1', 'R1')],
    'node2': [('R1', 'R2'), ('R1', 'R3')],
    'node3': [('R2', 'R4'), ('R2', 'R5'), ('R3', 'R4'), ('R3', 'R5')],
    'node4': [('R4', 'Z1')],
    'node5': [('R5', 'Z1')],
}
>>> list_of_edges = flatten_list(graph.values())
>>> print (['-->'.join(path) for path in get_all_paths(list_of_edges)])
# ['V1-->R1-->R2-->R4-->Z1', 'V1-->R1-->R2-->R5-->Z1', 'V1-->R1-->R3-->R4-->Z1', 'V1-->R1-->R3-->R5-->Z1']