Recursive lambda expression to find the path(s) through a directed graph?

Question

I need to find a path or paths down a complicated graph structure. The graph is built using something similar to this:

class Node
{
    public string Value { get; set;}
    public List<Node> Nodes { get; set;}

    public Node()
    {
        Nodes = new List<Node>();
    }
}

What makes this complicated is that the nodes can reference back to an earlier node. For example,

A -> C -> E -> A

What I need to do is get a list of stacks which represent paths through the Nodes until I get to a Node with a specific value. Since its possible there can be some very large paths available we can have a maximum Nodes to try.

List<Stack<Node>> paths = FindPaths(string ValueToFind, int MaxNumberNodes);

Does anyone have a way to build this (or something similar)? I've done recursion in the past but I'm having a total brain fart thinking about this for some reason. My question specified a lambda expression but using a lambda is not necessarily required. I'd be grateful for any solution.

Side note: I lifted the class from aku's excellent answer for this recursion question. While his elegant solution shown below traverses the tree structure it doesn't seem to allow enough flexibility to do what I need (for example, dismiss paths that are circular and track paths that are successful).

Action<Node> traverse = null;
traverse = (n) => { Console.WriteLine(n.Value); n.Nodes.ForEach(traverse);};
traverse(root);  // where root is the tree structure

Edit:

Based on input from the comments and answers below I found an excellent solution over in CodeProject. It uses the A* path finding algorithm. Here is the link.

Answer 1

If you're issue is related to Pathfinding, you may want to google for "A star" or "A*". Its a common and efficient pathfinding algorithm. See this article for an example directly related to your problem.

You may also want to look at the Dijsktra Algorithm

Answer 2

I'm not sure whether your intended output is all paths to the goal, the best path to the goal (by some metric, e.g. path length), or just any path to the goal.

Assuming the latter, I'd start with the recursive strategy, including tracking of visited nodes as outlined by Brann, and make these changes:

1. Add parameters to represent the goal being sought, the collection of successful paths, and the current path from the start.

2. When entering a node that matches the goal, add the current path (plus the current node) to the list of successful paths.

3. Extend the current path with the current node to create the path passed on any recursive calls.

4. Invoke the initial ExploreGraph call with an empty path and an empty list of successful paths.

Upon completion, your algorithm will have traversed the entire graph, and distinct paths to the goal will have been captured.

That's just a quick sketch, but you should be able to flesh it out for your specific needs.

Answer 3

I don't know exactly what you want to achieve, but this circular reference problem is usually solved by tagging already visited nodes. Just use a Dictionnary to keep track of the nodes which have already been visited so that you don't loop.

Example :

  public void ExploreGraph(TreeNode tn, Dictionary<TreeNode, bool> visitednodes)
        {

            foreach (Treenode childnode in tn.Nodes)
            {
                if (!visitedNodes.ContainsKey(childnode))
                {
                    visitednodes.Add(childnode);
                    ExploreGraph(childnode, visitednodes);
                }
            }
        }