Check if exists any path, in DI-Graph

Question

If i have a Di-Graph, how to check if all pairs (a,b) of nodes create a path?

Example:

Input:

v1 v2
v5 v6
v2 v3
v3 v4
v4 v5
v0 v1

And i need check if exist atleast one path through this graph, without visiting each node more then once.

I have already tried backtracking, but for biggest input it will took hours...

Specific example:

On input i have edges:

{m,a}, {a,c}, {a,m} 

and i have to check, if there is a path, in this case it will return True, because exist

{a,m} -> {m, a} -> {a,c}

Answer 1

A relatively naive, quadratic algorithm

Pop a path from your list of path. Pop another path in the list to concatenate it with. Push the concatenated path back into the list. If at any time we cannot find another path to concatenate it with, it means the answer is no, all pairs of nodes do not combine into a single path, so we return None.

def combine_into_one_path(list_of_paths):
  path = list_of_paths.pop()
  while list_of_paths:
    path2 = pop_adjacent_path(list_of_paths, path[0], path[-1])
    if path2 is None:
      return None
    elif path[-1] == path2[0]:
      path = path[:-1] + path2
    elif path2[-1] == path[0]:
      path = path2[:-1] + path
    else:
      assert(False)
  return path

def pop_adjacent_path(list_of_paths, a, b):
  for i,p in enumerate(list_of_paths):
    if p[0] in (a, b) or p[-1] in (a,b):
      return list_of_paths.pop(i)
  return None

print(combine_into_one_path([[1, 2], [5, 6], [2, 3], [3, 4], [4, 5], [0, 1]]))
# [0, 1, 2, 3, 4, 5, 6]

print(combine_into_one_path([[1, 2], [5, 6], [2, 3], [3, 7], [4, 5], [0, 1]]))
# None

This algorithm is quadratic in the number of paths because the while-loop in combine_into_one_path has one iteration per path in the list, and function pop_adjacent_path iterates through the list as well.

Note that this code doesn't check that nodes are unique; for instance, [v1, v2, v3, v2, v4, v1, v5] would be considered a valid path. You could add a check just before the final return in combine_into_one_path to make sure every element in the path is unique.

Making it linear

What slow the algorithm down is having to iterate through the whole list to find a pair of nodes to combine our current path with. One way to avoid that would be to store the pairs in a dictionary, so we can answer the questions "does a pair end with a?" and "does a pair start with b?" in constant time.

def combine_into_one_path(list_of_paths):
  path = list_of_paths.pop()
  forwards = {p[0]:p for p in list_of_paths}
  backwards = {p[-1]:p for p in list_of_paths}
  while forwards:
    if path[-1] in forwards:
      p2 = forwards[path[-1]]
      del forwards[path[-1]]
      del backwards[p2[-1]]
      path = path[:-1] + p2
    elif path[0] in backwards:
      p2 = backwards[path[0]]
      del backwards[path[0]]
      del forwards[p2[0]]
      path = p2[:-1] + path
    else:
      return None
    print('\npath     =', path)
    print('forwards =', forwards)
    print('backwards=', backwards)
  return path

print(combine_into_one_path(['manta', 'alcats', 'random']))
# randomantalcats

This is almost the same algorithm, but we replaced function pop_adjacent_path with a dictionary check, which is constant time instead of linear.

Just to understand how the algorithm works:

list_of_paths = [[1, 2], [5, 6], [3, 4], [4, 5], [0, 1], [2, 3]]

path     = [2, 3]
forwards = {1: [1, 2], 5: [5, 6], 3: [3, 4], 4: [4, 5], 0: [0, 1]}
backwards= {2: [1, 2], 6: [5, 6], 4: [3, 4], 5: [4, 5], 1: [0, 1]}

path     = [2, 3, 4]
forwards = {1: [1, 2], 5: [5, 6], 4: [4, 5], 0: [0, 1]}
backwards= {2: [1, 2], 6: [5, 6], 5: [4, 5], 1: [0, 1]}

path     = [2, 3, 4, 5]
forwards = {1: [1, 2], 5: [5, 6], 0: [0, 1]}
backwards= {2: [1, 2], 6: [5, 6], 1: [0, 1]}

path     = [2, 3, 4, 5, 6]
forwards = {1: [1, 2], 0: [0, 1]}
backwards= {2: [1, 2], 1: [0, 1]}

path     = [1, 2, 3, 4, 5, 6]
forwards = {0: [0, 1]}
backwards= {1: [0, 1]}

path     = [0, 1, 2, 3, 4, 5, 6]
forwards = {}
backwards= {}