Найти множество путей в графе


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

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

from collections import deque
from itertools import product

def travel(graph, start, dests, count):
    queue = deque([[(start, None)]])
    paths = []
    while queue:
        path = queue.popleft()
        at = path[-1][0]
        if at in dests:
            pp = [p[1] for p in path[1:]]
            for real_path in product(*pp):
                paths.append(''.join(real_path))
                count -= 1
                if count == 0:
                    return paths
        adj = graph.get(at, {})
        for item in adj.items():
            queue.append(path + [item])
    return paths

Позвонили с образец график:

G = {
    1 : {2 : 'mqr', 3 : 't'},
    2 : {3 : 'q'},
    3 : {1 : 'S', 4 : '_'},
    4 : {3 : 't', 1 : 'xUI', 5 : '=+/'},
    5 : {4 : 'q', 6 : '1'},
    6 : {1 : '0'}
}
print(len(set(travel(G, 1, [6], 1000))))

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



Комментарии
1 ответ


  1. Нет строкой документации. Что travel делать? Какие аргументы она принимает? Какое это возвращение?

  2. Смысл структуры данных queue далеко не ясно. Вроде бы дека, элементы которого представляют пути, каждый путь представляет собой список пар (v, e) где v это вершина на пути, и e это None если это первая вершина на пути, или повторяемое из кромки, v можно было бы доехать от предыдущей вершины пути. Такая сложная структура данных-это трудно понять, и было бы понятнее, если бы он имел собственный класс, например, используя collections.namedtuple.

  3. Это будет хорошая идея, чтобы создать пути, по одному за раз с помощью yield заявление, так что если потребитель обрабатывает пути, потом весь список путей не должны быть сохранены в памяти.

  4. Генерации путей позволит нам опустить count аргумент и продолжать вырабатывать пути навсегда. Если абонент хочет более 1000 путей, они могут использовать itertools.islice:

    islice(travel(graph, start, dests), 1000)

  5. Тест if at in dests: занимает время, пропорциональное количеству направлений. Это будет работать в постоянном времени, если dests были преобразованы в набор.

  6. Было бы разумно настаивать на диаграмме, имеющих ключевое значение для каждой вершины (которых соответствующее значение является пустой словарь, если вершина раковины); это позволит вам написать graph[at] вместо graph.get(at, {}) который создает и выбрасывает пустой словарь.

  7. Осуществление магазинах path + [item] в очереди, которые отнимают много времени и пространства пропорциональна длине пути, на каждой итерации. В этом нет необходимости: многие пути будут иметь одинаковый начальный префикс, поэтому структура данных, которая хранится только последний пункт на пути, вместе с ссылкой на предыдущие структуры данных, на путь, потребуется постоянная времени на каждой итерации. Весь путь может быть восстановлен, когда достигается следующим ссылкам.

2. Пересмотренный кодекс

from collections import deque, namedtuple

# Node in the breadth-first search with fields:
# vertex -- the current vertex in the search
# edges -- iterable of edges from previous vertex (or None)
# prev -- previous Search node (or None)
SearchNode = namedtuple('SearchNode', 'vertex edges prev')

def travel(graph, start, dests):
"""Generate paths in graph beginning at the vertex start and ending at
any of the vertices in dests.

The graph must be represented as a mapping from vertex to a
mapping from neighbouring vertex to an iterable of edges.

"""
dests = set(dests)
queue = deque([SearchNode(start, None, None)])
while queue:
at = queue.popleft()
if at.vertex in dests:
edges = []
prev = at
while prev.edges is not None:
edges.append(prev.edges)
prev = prev.prev
for path in product(*reversed(edges)):
yield ''.join(path)
for v, e in graph[at.vertex].items():
queue.append(SearchNode(v, e, at))

2
ответ дан 3 февраля 2018 в 10:02 Источник Поделиться