python - All possible paths from one node to another in a directed tree (igraph)

Question

I use python binding to igraph to represent a directed tree. I would like to find all possible paths from one node in that graph to another one. Unfortunately, I couldn't find a ready to use function in igraph that performs this task?

EDIT

The concerns on infinite number of paths

the graph I'm talking about is actually a directed acyclic graph (DAG) with a single root. It represents a unidirectional cascade of events that, on various levels of the cascade, can either split or join together. As I said, this is a unidirectional graph. It is also provided that the graph does not contain any cycles. Due to these two reasons, infinite list of paths, is impossible.

What am I trying to do?

My goal is to find all the possible paths that lead from the top of the graph (the root) to the given node.

Answer 1

You are looking for all paths between one node and another in a directed acyclic graph (DAG).

A tree is always a DAG, but a DAG isn't always a tree. The difference is that a tree's branches are not allowed to join, only divide, while a DAG's branches can flow together, so long as no cycles are introduced.

Your solution can be found as find_all_paths() in "Python Patterns - Implementing Graphs." This requires a little adaptation to use with igraph. I don't have igraph installed, but using mocks, this seems to work:

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)

It was unclear from the documentation whether the adjlist is a list of lists of vertex indices or a list of list of vertex objects themselves. I assumed that the lists contained indices to simplify using the adjlist. As a result, the returned paths are in terms of vertex indices. You will have to map these back to vertex objects if you need those instead, or adapt the code to append the vertex rather than its index.