Python igraph: получить все возможные пути в ориентированном графе

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

Обновить:

  • From-Import при сохранении доступа по модулю
  • Моя главная цель – получить все узлы в этих путях, чтобы затем получить подграф этих узлов.

  • From-Import при сохранении доступа по модулю
  • 5 Solutions collect form web for “Python igraph: получить все возможные пути в ориентированном графе”

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

    Объект Graph в igraph имеет метод subcomponent . По умолчанию он предоставляет вам все узлы, которые находятся в одном и том же (слабо подключенном) компоненте в качестве заданного входного узла. Однако он также имеет аргумент mode . Когда вы устанавливаете mode на "out" , он даст вам все узлы, которые достижимы с определенного узла. Когда вы устанавливаете mode на "in" , он даст вам все узлы, из которых вы можете добраться до определенного узла. Таким образом, вам, вероятно, понадобится пересечение набора достижимых узлов из исходной вершины и набора узлов, которые могут достигнуть вашей целевой вершины:

     s=set(graph.subcomponent(source, mode="out")) t=set(graph.subcomponent(target, mode="in")) s.intersection(t) 

    Это, вероятно, намного быстрее, чем вычисление всех путей.

    Я не могу быть уверен, но, глядя на пару минут в документации на python igraph, похоже, что такой функции не существует. Я перестала смотреть, потому что, на мой взгляд, такая информация не очень полезна, и, по крайней мере, если бы я был разработчиком, я бы ее не создал. Вернуться к вопросу:

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

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

     from igraph import * def adjlist_find_paths(a, n, m, path=[]): "Find paths from node index n to m using adjacency list a." path = path + [n] if n == m: return [path] paths = [] for child in a[n]: if child not in path: child_paths = adjlist_find_paths(a, child, m, path) for child_path in child_paths: paths.append(child_path) return paths def paths_from_to(graph, source, dest): "Find paths in graph from vertex source to vertex dest." a = graph.get_adjlist() n = source.index m = dest.index return adjlist_find_paths(a, n, m) 

    Я не проверял, дает ли он правильный результат.

    В этой статье Тамас, один из авторов igraph, представил простое рекурсивное решение. Эта функция возвращает пути без повторения, поскольку она вытесняет set(path) (узлы уже в пути) из множества возможных последующих шагов ( adjlist[start] , где start – это узел, добавленный последним). Я изменил это решение, чтобы иметь функцию для поиска всех простых путей до maxlen длины между двумя наборами узлов. Он возвращает список путей:

     def find_all_paths(graph, start, end, mode = 'OUT', maxlen = None): def find_all_paths_aux(adjlist, start, end, path, maxlen = None): path = path + [start] if start == end: return [path] paths = [] if maxlen is None or len(path) <= maxlen: for node in adjlist[start] - set(path): paths.extend(find_all_paths_aux(adjlist, node, end, path, maxlen)) return paths adjlist = [set(graph.neighbors(node, mode = mode)) \ for node in xrange(graph.vcount())] all_paths = [] start = start if type(start) is list else [start] end = end if type(end) is list else [end] for s in start: for e in end: all_paths.extend(find_all_paths_aux(adjlist, s, e, [], maxlen)) return all_paths 

    для этого графика:

     import igraph G = ig.Graph() #ring G.add_vertices(4) G.add_edges([(0,1), (1,2),(2,3),(3,0)]) G = G.as_directed() print G.is_directed() print G 

    Если я применяю функцию сверху, https://stackoverflow.com/a/29324009/2772305

    как

     for p in find_all_paths(G,0,0): print p 

    Я получаю только

    [0] в то время как должен быть второй путь [0,1,2,3,0] imho

    Как найти все пути, если на графике есть такие кольца?

    в networkx, можно получить желаемый результат с помощью all_simple_paths:

     import networkx as nx G = nx.MultiDiGraph() G.add_path(['a','b','c','d','a']) G.add_path(['a','e','f','g']) G.add_path(['a','a']) for p in nx.all_simple_paths(G,'a','a'): print p 

    Результат:

     ['a', 'a'] ['a', 'b', 'c', 'd', 'a'] 

    Как сказано выше, функция all_simple_paths существует только в networkx, что не подходит для обработки огромных графиков из-за проблем с производительностью. Есть ли способ передать all_simple_paths из networkx в igraph?

    Я успешно использую функцию ниже с помощью python-igraph. Поскольку это узкое место для производительности в моем приложении, мне интересно, есть ли у кого-то идея, как дальше оптимизировать его по производительности.

     def find_all_paths2(G, start, end, vn = []): """ Finds all paths between nodes start and end in graph. If any node on such a path is within vn, the path is not returned. !! start and end node can't be in the vn list !! Params: -------- G : igraph graph start: start node index end : end node index vn : list of via- or stop-nodes indices Returns: -------- A list of paths (node index lists) between start and end node """ vn = vn if type(vn) is list else [vn] #vn = list(set(vn)-set([start,end])) path = [] paths = [] queue = [(start, end, path)] while queue: start, end, path = queue.pop() path = path + [start] if start not in vn: for node in set(G.neighbors(start,mode='OUT')).difference(path): queue.append((node, end, path)) if start == end and len(path) > 0: paths.append(path) else: pass else: pass return paths 
    Python - лучший язык программирования в мире.