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

by

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.

More Related Contents:

  1. how to check Recursively if i can create a sum from a list of numbers? [closed]
  2. How do i implement these algorithms below
  3. Permutations between two lists of unequal length
  4. How to efficiently compare two unordered lists (not sets) in Python?
  5. About Python’s built in sort() method
  6. Approximating data with a multi segment cubic bezier curve and a distance as well as a curvature contraint
  7. Efficient way to apply multiple filters to pandas DataFrame or Series
  8. Rolling or sliding window iterator?
  9. What is the best way to get all the divisors of a number?
  10. How to efficiently compare two unordered lists (not sets)?
  11. Efficient calculation of Fibonacci series
  12. Python – Is a dictionary slow to find frequency of each character?
  13. How to implement a binary tree?
  14. In Python, what is the fastest algorithm for removing duplicates from a list so that all elements are unique *while preserving order*? [duplicate]
  15. Best way to determine if a sequence is in another sequence?
  16. Mapping a range of values to another
  17. How to test if one string is a subsequence of another? [duplicate]
  18. Find elements of array one nearest to elements of array two
  19. Complexity of list.index(x) in Python
  20. Why does Python’s itertools.permutations contain duplicates? (When the original list has duplicates)
  21. Python: find closest string (from a list) to another string
  22. Split a list of numbers into n chunks such that the chunks have (close to) equal sums and keep the original order
  23. In Python, how do you find the index of the first value greater than a threshold in a sorted list?
  24. Python: Choose random line from file, then delete that line
  25. String similarity metrics in Python [duplicate]
  26. What is the time complexity of heapq.nlargest?
  27. creating a spiral array in python?
  28. Understanding change-making algorithm
  29. Path between two nodes
  30. Apache Airflow scheduler does not trigger DAG at schedule time

Leave a Comment