Graph Theory: Finding all possible paths of 'n' length (with some constraints)

Question

I was given a sample challenge question by one of my friends. I would like to hear some advice on how to best approach finding a solution.

The problem involves calculating all possible patterns of traversing a series of points on a grid-like scale. I will simply be given a number 'n' that represents how many times I must move, and I must determine the number of ways I can traverse the grid moving n times. The starting point can be any of the points so I must run my calculation on every starting point with my answer being the sum of the results of each starting point.

I am still a bit of a beginner is some regards to programming, and my best guess as to how to approach this problem is to use graph theory. I have started by creating a graph to represent the nodes as well as their neighbors. I am leaving this problem intentionally vague because I want to learn how to approach these kinds of problems rather than having some expert swoop in and simply solve the entire thing for me. Here is an example representation of my graph in Python 3 (a dictionary).

graph = {'a':['b','c']
         'b':['a','e','f']
         'c':['a','d']
         'd':['c']
         'e':['b','g'] and etc. 

My real graph is significantly bigger with each node typically having at least 3-4 neighbors. Let's pretend the 'n' given is 6, meaning I need to return all possible valid paths that involve moving 6 times. I am allowed to revisit nodes, so a valid path could simply be a-b-a-b-a-b. Another example of a 'valid' path is a-b-a-c-d-c or e-b-a-c-a-b since we can start from any starting point.

I am at a bit of a loss as to how to best approach this problem. Recursion has crossed my mind as a possible solution where I traverse all possible paths and increment a counter each time I hit the 'end' of a path. Another possible solution I have considered is at each node, calculate the possible moves and multiply it with a running tally. For example, starting at 'a', I have two moves. If I navigate to 'b', I have 3 moves. If I navigate to 'c', I have 2 moves. At this point, I have 1*3*2 moves. This could be a completely wrong approach...just an idea I had.

The actual problem is a lot more complex with constraints for certain nodes (how many times you can visit it, rules against visiting it if a certain sequence of nodes were hit prior, etc.) but I will omit the details for now. What I will say is that given these constraints, my algorithm must know what the previous pattern of visited nodes was. At the 5th move, for example, I must be able to refer to the previous 4 moves at any time.

I would love to hear advice on how you would best approach solving the 'simpler' problem I outlined above.

Answer 1

Check out Depth First Search (DFS). Just off the top of my head: Use recursive DFS, use a counter for saving each node found after making 'n' moves. You would need to build an undirected graph representation of the given data, so that you could run the DFS algorithm on the graph.

Answer 2

Here's the simplest answer for the case you gave. Once you have you graph in the form of a "transition map" (which can just be a dictionary, like you've shown), then the following code will work:

def myDFS(trans_dict,start,length,paths,path=[]): 
    path=path+[start] 
    if len(path)==length:
        paths.append(path) 
    else:
        for node in trans_dict[start]:
            myDFS(trans_dict,node,length,paths,path)

If you want the number of ways you can traverse the map with a path of a given length, then that would just be len(paths).

Example:

trans_dict = {0:[1,2],1:[2,3],2:[0,3],3:[3]}
paths = []
length = 3

for a in trans_dict:
    myDFS(trans_dict,a,length,paths)

print paths # [[0, 1, 2], [0, 1, 3], [0, 2, 0], [0, 2, 3], [1, 2, 0], [1, 2, 3], [1, 3, 3], [2, 0, 1], [2, 0, 2], [2, 3, 3], [3, 3, 3]]
print len(paths) # 11

Answer was inspired by this Q&A: trying to find all the path in a graph using DFS recursive in Python