Directed cyclic graph traversal to find a path of certain length

Question

I have a directed graph that looks sort of like this. All edges are unidirectional, cycles exist, and some nodes have no children.

I want a traversal algorithm where the goal is to find a path of length n nodes anywhere in the graph. The algorithm should do the following:

• Starting node is randomly chosen, it traverses its children, and visited nodes is kept somewhere to return a path at the end
• Same nodes can be visited again
• If it reaches a node with no children, it traverses the most recent node with unexplored children. If all possible paths from the starting node are traversed, try starting from other nodes. (I think this method ensures all possible paths are explored)
• Traversal stops when number of nodes visited reaches n and path is returned
• If no path of length n is found, it returns "No valid path"

I'm not sure if an algorithm for this already exists. Most search algorithms seem to deal with finding shortest path, MSTs, and can't visit same nodes. Pathfinding algorithms like A* and Dijkstra's seem overcomplicated for my needs. I might need a modified version of one of these, but not sure exactly which one to use.

Answer 1

It sounds like you just want a simple recursive algorithm. Here's some basic pseudocode.

find_path(node, n):   
   if n == 1:
       yield [node]
       return
   for each child of node n:
       for each path in find_path(child, n - 1):
           yield [node] + path