Путь между двумя узлами

Question

Я использую networkx для работы с графиками. У меня довольно большой график (в нем около 200 узлов), и я пытаюсь найти все возможные пути между двумя узлами. Но, как я понимаю, networkx может найти только кратчайший путь. Как я могу получить не только кратчайший путь, но и все возможные пути?

UPD: путь может содержать каждый узел только один раз.

UPD2: мне нужно что-то вроде функции find_all_paths (), описанной здесь: python.org/doc/essays/graphs.html Но эта функция плохо работает с большим количеством узлов и окантована = (

Answer 1

igraph , другой графовый модуль для Python может вычислить все кратчайшие пути между данной парой узлов. Подсчет всех путей не имеет смысла, так как таких путей бесконечно много.

Пример для вычисления всех кратчайших путей из вершины 0:

>>> from igraph import Graph
>>> g = Graph.Lattice([10, 10], circular=False)
>>> g.get_all_shortest_paths(0)
[...a list of 3669 shortest paths starting from vertex 0...]

Если у вас есть igraph 0.6 или новее (это версия для разработки на момент написания), вы можете ограничить результат get_all_shortest_paths и данной конечной вершиной:

>>> g.get_all_shortest_paths(0, 15)
[[0, 1, 2, 3, 4, 14, 15],
 [0, 1, 2, 12, 13, 14, 15],
 [0, 10, 11, 12, 13, 14, 15],
 [0, 1, 11, 12, 13, 14, 15],
 [0, 1, 2, 3, 13, 14, 15],
 [0, 1, 2, 3, 4, 5, 15]]

Конечно, вы должны быть осторожны; например, предположим, что у вас есть сеточный граф 100 x 100 (который можно легко сгенерировать с помощью Graph.Lattice([100, 100], circular=False) в igraph). Количество кратчайших путей, ведущих от верхнего левого узла к нижнему правому узлу, равно числу возможностей выбора 100 элементов из 200 (доказательство: длина кратчайшего пути там имеет 200 ребер, 100 из которых будут идти «горизонтально»). в сетке и 100 из которых пойдут "вертикально"). Это, вероятно, не умещается в вашей памяти, поэтому даже вычисление всех кратчайших путей между этими двумя узлами здесь не реально осуществимо.

Если вам действительно нужны все пути между двумя узлами, вы можете переписать функцию, указанную на веб-странице, которую вы упомянули, используя igraph, которая, вероятно, будет быстрее, чем чисто Python-решение, поскольку ядро ​​igraph реализовано в C:

def find_all_paths(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
        return [path]
    paths = []
    for node in set(graph.neighbors(start)) - set(path):
        paths.extend(find_all_paths(graph, node, end, path))
    return paths

Его можно оптимизировать больше, если сначала преобразовать граф в представление списка смежности, так как это избавит от повторных вызовов graph.neighbors:

def find_all_paths(graph, start, end):
    def find_all_paths_aux(adjlist, start, end, path):
        path = path + [start]
        if start == end:
            return [path]
        paths = []
        for node in adjlist[start] - set(path):
            paths.extend(find_all_paths_aux(adjlist, node, end, path))
        return paths

    adjlist = [set(graph.neighbors(node)) for node in xrange(graph.vcount())]
    return find_all_paths_aux(adjlist, start, end, [])

Редактировать : исправлен первый пример работы с игрой 0.5.3, а не только с игрой 0.6.

Answer 2

Этот на самом деле работает с networkx, и он не рекурсивный, что может быть хорошо для больших графиков.

def find_all_paths(graph, start, end):
    path  = []
    paths = []
    queue = [(start, end, path)]
    while queue:
        start, end, path = queue.pop()
        print 'PATH', path

        path = path + [start]
        if start == end:
            paths.append(path)
        for node in set(graph[start]).difference(path):
            queue.append((node, end, path))
    return paths

Answer 3

Алгоритм Дейкстры найдет кратчайший путь способом, подобным поиску в ширину (он заменяет приоритетную очередь, взвешенную по глубине, в граф для наивной очереди BFS). Вы можете довольно просто расширить его, чтобы получить N кратчайших путей, если вам нужно некоторое количество альтернатив, хотя если вам нужно, чтобы пути существенно отличались (например, планирование маршрутов фургонов безопасности), возможно, вам нужно быть более умным в выборе пути, которые значительно отличаются друг от друга.