Recursion into stack-form. Preserving a search pat

Question

---

A short form of question is: How do I convert a recursive search into a stack search? The trick is to be able to grab a branch that leads towards each of the recursion's endings.

This Article's suggestion won't work as the path to the ending cannot be traced. (Ultimately if we could save each step into array via the reference to trace later on)

I am using c#, and building a web of nodes.

---

Each node contains an information about its neighbors. Also, each node contains 2 arrays. The 1st one is referencing all the nodes to which this node can communicate. The 2nd array holds lists, each of which contains "a path", consisting of ordered node references.

If node A wishes to communicate to node B, he will look at the first array to see if B is even in his reach. If he finds it, he uses this index from a first array on a 2nd array to obtain "a path".

It's important for me to preserve this order.

As well as that, every node contains a list of direct neighbors (within a reach of 1).

Knowing its neighbors is actually the only thing each node knows before a Bake process occurs.

During the Bake, I recursively search through each neighbor of an inspected node, recording the "recursion branch" into a path-buffer list. As soon as there are no more neighbors, I copy this buffer "path-list" into the 2nd Array + copy this dead-end node into a next cell of the 1st Array. of corse 1st and 2nd array belong to the node which we started from.

I then remove 1 dead -end node from the path list's last cell, rollback to a previous node to inspect another neighbor and the process repeats.

The problem is - huge recursions cause a stack overflow if the web gets too big. I need to translate it into a stack form.

I've looked over articles, such as this one, but there is obviously no way of accumulating this "path list", since every neighbor of every node on the way is pushed into a stack, anticipating a further inspection in future. There is no clear "trace" of the path we took to get to this dead-end node.

Here is a simplified version of the code (2 classes)

class Node{

    List neighbours;
    List accessNodes;
    List allPaths;
}

class Baker{

  List bakerBufferPaths;
  List bakerBanned;


   foreach particular node in scene{
        clear accessNodes;
        clear allPaths;
        clear bakerBufferPaths;
        }

        MainNodeList1 = particular node's list1 by reference. //those 2 variables will always  refer to the base node for which the search happens. They will be unchanged on all the levels of recursion
        MainNodeList2 = particular node's list2 by reference.


    void  function LookFurther(Node node){
          Node current;
          current = node;


          bakerBufferList(add current);


          foreach (not banned neighbor in current){

               LookFurther(current);
          }//end of foreach neighbor of current

          MainNodeList 1 (add current);
          MainNodeList 2 (add bakerBufferList);

          bakerBanned(add current);

         bakerBufferList(remove last);
     } //end of look further function

} //end of baker class

What to do?

Thank you

Answer 1

OK, this was an interesting question, so here's some example C# code I wrote up.

private static void SearchConnections(Node root)
{
    var path = new Stack<Node>();
    var progress = new Stack<int>();

    path.Push(root);        // start with root
    progress.Push(0);       // start with root's first neighbour

    while (path.Any())
    {
        var topnode = path.Peek();

        // continue the search until we get to a leaf
        int neighbourIx = progress.Pop();
        if (neighbourIx < topnode.Neighbours.Count())
        {
            // next time we are at this node, take the next neighbour
            progress.Push(neighbourIx + 1); 
            // don't push cycles onto the stack!
            var nextNeighbour = topnode.Neighbours[neighbourIx];
            if (!path.Contains(nextNeighbour))
            {
                path.Push(nextNeighbour);
                // when we process the neighbour we just pushed,
                // start with its first neighbour
                progress.Push(0);
            }
        }
        else
        {
            // no more neighbours here - either a leaf, or we've searched all 
            // neighbours. this is the last time we'll see this node, so 
            // process it now. record the path to the top node unless 
            // topnode is root - no path to self!
            if (topnode != root)
            {
                var trace = path.Reverse().ToList();
                root.Reachable.Add(topnode);
                root.Paths.Add(trace);
            }

            // remove the topnode from the stack
            path.Pop();
        }
    }
}

Here's a fiddle that shows it working: http://dotnetfiddle.net/6ijNzb

I've used two stacks - one to keep track of the nodes in the path, and one to keep track of which neighbour we picked at each branch in the path.