1

I have a directed network as follows.

enter image description here

Now, I would like to get all the possible 4 length and 5 length paths of this graph (where both the starting and ending paths are B)

Examples of 4 length paths are;

  • B--C--B--A--B
  • B--A--B--B--B
  • B--A--B--C--B

Examples of 5 length paths are;

  • B--C--B--A--B--B
  • B--A--B--B--C--B

I tried to use Breadth First Search (BFS) to solve this. It seems like most of the code of BFS algorithm does not satisfies my requirements. That is;

  • They do not consider variable length paths
  • Their starting and end node is not same as mine (They are different)

My current code is as follows:

graph = {'A': ['B'],
         'B': ['A','C', 'B'],
         'C': ['B']}

# visits all the nodes of a graph (connected component) using BFS
def bfs_connected_component(graph, start):
   # keep track of all visited nodes
   explored = []
   # keep track of nodes to be checked
   queue = [start]

   # keep looping until there are nodes still to be checked
   while queue:
       # pop shallowest node (first node) from queue
       node = queue.pop(0)
       if node not in explored:
           # add node to list of checked nodes
           explored.append(node)
           neighbours = graph[node]

           # add neighbours of node to queue
           for neighbour in neighbours:
               queue.append(neighbour)
   return explored

bfs_connected_component(graph,'A')

I would like to know if there are any python libraries I can use for this or is there is a way to modify BFS to accomplish this problem.

I am happy to provide more examples if needed :)

J Cena
  • 963
  • 2
  • 11
  • 25

1 Answers1

2

When searching for all combinatorial results, I found that recursive generators in python provide more compact and understandable code compared to other approaches (such as recursive functions, or stack-based equivalents).

Here we are looking for all paths from node to goal of fixed length. The list path is used as an accumulator, which, at the base case, becomes a prefix of the 1-path passing thru node.

def all_paths(graph, node, goal, length, path=[]):
    if length == 0 and node == goal:
        yield path + [node]
    elif length > 0:
        for n in graph[node]:
            yield from all_paths(graph, n, goal, length - 1, path + [node])

Paths of length 4:

>>> print(*all_paths(graph, 'B', 'B', 4), sep='\n')
['B', 'A', 'B', 'A', 'B']
['B', 'A', 'B', 'C', 'B']
['B', 'A', 'B', 'B', 'B']
['B', 'C', 'B', 'A', 'B']
['B', 'C', 'B', 'C', 'B']
['B', 'C', 'B', 'B', 'B']
['B', 'B', 'A', 'B', 'B']
['B', 'B', 'C', 'B', 'B']
['B', 'B', 'B', 'A', 'B']
['B', 'B', 'B', 'C', 'B']
['B', 'B', 'B', 'B', 'B']

Paths of length 5:

>>> print(*all_paths(graph, 'B', 'B', 5), sep='\n')
['B', 'A', 'B', 'A', 'B', 'B']
['B', 'A', 'B', 'C', 'B', 'B']
['B', 'A', 'B', 'B', 'A', 'B']
['B', 'A', 'B', 'B', 'C', 'B']
['B', 'A', 'B', 'B', 'B', 'B']
['B', 'C', 'B', 'A', 'B', 'B']
['B', 'C', 'B', 'C', 'B', 'B']
['B', 'C', 'B', 'B', 'A', 'B']
['B', 'C', 'B', 'B', 'C', 'B']
['B', 'C', 'B', 'B', 'B', 'B']
['B', 'B', 'A', 'B', 'A', 'B']
['B', 'B', 'A', 'B', 'C', 'B']
['B', 'B', 'A', 'B', 'B', 'B']
['B', 'B', 'C', 'B', 'A', 'B']
['B', 'B', 'C', 'B', 'C', 'B']
['B', 'B', 'C', 'B', 'B', 'B']
['B', 'B', 'B', 'A', 'B', 'B']
['B', 'B', 'B', 'C', 'B', 'B']
['B', 'B', 'B', 'B', 'A', 'B']
['B', 'B', 'B', 'B', 'C', 'B']
['B', 'B', 'B', 'B', 'B', 'B']
fferri
  • 18,285
  • 5
  • 46
  • 95
  • Thanks a lot for the great answer. very helpful :) – J Cena Apr 25 '18 at 09:03
  • If I need to change my starting and end node as A, I hope the only changes I need to do are 1) the `node` and `goal` parameters when calling the function as A, A and; 2) the if condition as `if length == 0 and node == 'A':` – J Cena Apr 25 '18 at 09:32
  • 1
    I had a small error in the first line, which should read as `if length == 0 and node == goal:`, so you need to change only the arguments passed to the function. – fferri Apr 25 '18 at 10:01
  • Thanks a lot once again :) – J Cena Apr 25 '18 at 10:18