I am using igraph (Python) and would like to get all possible paths between two nodes in a directed graph. I am aware of the function get_all_shortest_paths, which is for shortest paths, but could not find a general one.
Update:
My main goal is to get all nodes in these paths, so that I can then get a subgraph of these nodes.
Since you mentioned in your question that your ultimate goal is to get only the nodes that are in these paths and not the paths themselves, I think you don't even have to calculate the paths.
The Graph object in igraph has a method called subcomponent. By default, it gives you all the nodes that are in the same (weakly connected) component as a given input node. However, it also has a mode argument. When you set mode to "out", it will give you all the nodes that are reachable from a certain node. When you set mode to "in", it will give you all the nodes from where you can reach a certain node. So, you'll probably need the intersection of the set of reachable nodes from your source vertex and the set of nodes that can reach your target vertex:
s=set(graph.subcomponent(source, mode="out"))
t=set(graph.subcomponent(target, mode="in"))
s.intersection(t)
This is probably way faster than calculating all the paths anyway.
In this post Tamás, one of the authors of igraph presented a simple recursive solution. This function returns paths without repetition, as it substracts set(path) (the nodes already in the path) from the set of possible next steps (adjlist[start], where start is the node added latest).
I modified this solution to have a function for searching all simple paths up to maxlen length, between two sets of nodes. It returns a list of paths:
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
I can not be sure, but looking for a couple of minutes in python igraph documentation it looks like such a function does not exist. I stopped looking because in my opinion such information is not really useful, and at least if I would be a developer, I would not create it. Back to the question:
First of all you need to understand that for an arbitrary graph, the number of such paths would be infinite. All you need is one cycle and you can create infinite amount of paths. So in order for this number to be finite it should be directed acyclic graph.
So if you have a DAG, you can use DFS and recursively calculate all the paths (note that you will end up with exponential graph and most probably will not be able to find an answer in the reasonable time for even for a reasonably big graph). I was not writing the code by myself, and just googled a little bit and it looks like this guy have done what you want (basically he is doing 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)
I have not checked whether it produces correct result.
for this graph:
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
If I apply the function from above https://stackoverflow.com/a/29324009/2772305
like
for p in find_all_paths(G,0,0):
print p
I get only
[0] as a result, whereas there should be a second path [0,1,2,3,0] imho
How do i find all paths if there are such rings in a graph?
in networkx, it is possible to get the desired result with 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
Result:
['a', 'a']
['a', 'b', 'c', 'd', 'a']
As said in above comments , the all_simple_paths function exists only in networkx, which is not suitable to process huge graphs due to performance issues. Is there any way to bring the all_simple_paths from networkx to igraph ?
I am sucessfully using below function with python-igraph. As it is the performance bottleneck in my application, I wonder if someone has an idea how to furtherly optimize it performance-wise.
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
There is a function called get_all_simple_paths(v, to=None, mode=OUT).
Perhaps when the question was asked this was not a feature, but it does exactly what you asked.
You said:
would like to get all possible paths between two nodes in a directed graph
So, if the graph object is g, the start node is source_vertex and the end node is target_vertex you could obtain all the possible paths with:
g.get_all_simple_paths(source_vertex, target_vertex)
