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

Question

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

Update:

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

Answer 1

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

У объекта 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) 

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

Answer 2

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

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

Итак, если у вас есть группа DAG, вы можете использовать DFS и рекурсивно рассчитать все пути (обратите внимание, что вы получите экспоненциальный график и, скорее всего, не сможете найти ответ в разумные сроки даже для достаточно большой график). Я сам не писал код, а немного искал в googled и выглядел как this guy have done what you want (в основном он делает 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) 

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

Answer 3

In this post Tamás, один из авторов igraph, представил простое рекурсивное решение. Эта функция возвращает пути без повторения, так как она выставляет set(path) (узлы уже в пути) из набора следующих следующих шагов (adjlist[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 

Answer 4

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

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'] 

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

Answer 5

Я успешно использую функцию внизу с помощью 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