Python igraph: get all possible paths in a directed graph

Question

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.

Answer 1

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.

Answer 2

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