Iterative Tree Traversal using a stack

Hi guys,

In my final thoughts on my scheduling algo, I have elected to imitate a recursive call with a stack. Thanks for the advice Codeplug. The pseudo code for my algo is as follows:

Code:

while(!empty())
    peek at top item; // This involves scheduling it, etc
    push() on next branches; // Put the next level of calls on stack
        continue if there were pushes done
    pop(); // Only do this if we didn't push anything on
        this mimics the return of the recursive function call
end while

All is well, except for one thing: After going down, then coming back up, I'll peek at the same node more than once. I somehow need to skip it, or pop it off the 2nd time I see it. Picture this tree for example:

Code:

            1
     /      |     \
    2      2      2
  / | \  / | \  / | \
  3 3 3  3 3 3  3 3 3

My goal is to travers the tree in normal order:
1 to 2 via left branch
2 to 3 via left branch
2 to 3 via middle branch
2 to 3 via right branch
1 to 2 via middle branch
2 to 3 via left branch
etc.....

Using my algorithm, I "visit" a node, and do the scheduling, etc, at the beginning of my while loop when I peek at the top. Later, I pop it off to simulate the recursive call. Thus, for example, when I've gone down the left third of the tree, my stack looks like this:

Code:

r m l r m l r m l
  1  |  2  |  3

Where r, m, l mean right, middle, left for the branches, and the numbers below are for what node we're talkinga about. After I've explored all three paths from 2 to 3, my stack will look like this:

Code:

r m l r m l
  1  |  2

This is where I run into a problem. Based on my algo, I will now peek at 2's left path, and push from there. Well, I already did that! How do I indicate that I need to pop that item, and insted travers 2's middle path?

My code is below, if it's any help. Kind of messy right now, with lots of global data (used to make my previous recursive solution faster) Any ideas??????

Thanks!

Code:

void solveIter ()
{
    stack<StackStructType> callStack;
    StackStructType current;

    current.job = 0;
    current.comp = '-';
    callStack.push(current);
    for (int i = Job::getMachPerJob() - 1; i >= 0 ; i--)
    {
        current.comp = jobs[current.job].getComp(i);   
        callStack.push(current);
    }
    while (!callStack.empty())
    {
        current = callStack.top();
        
        if (current.comp != '-' && !jobs[current.job].isScheduled())
        {
            numOfJobs++;
            if (numOfJobs > currentBest)
            {
                currentBest = numOfJobs;
                best = jobs;
            }
            computers[current.comp - 97].addJob(jobs[current.job].getEnd());
            jobs[current.job].setSchedule(current.comp);
        }
        if (current.job + 1 < jobSize)
        {
            current.job += 1;
            current.comp = '-';
            callStack.push(current);
            for (int i = Job::getMachPerJob() - 1; i >= 0; i--)
            {
                if (computers[jobs[current.job].getComp(i) - 97].isAvailable(jobs[current.job].getStart()))
                {
                    current.comp = jobs[current.job].getComp(i);   
                    callStack.push(current);
                }
            }
            continue;
        }
        current = callStack.top();
        callStack.pop();
        if (current.comp != '-')
        {
            numOfJobs--;
            computers[current.comp - 97].removeJob();
        }
    }
}

What about something like visited in the StackStructType?

gg

I had something like that, only I had it as a member of the corresponding job object. This was causing me some problems, in that I would start scheduling jobs that I just popped, so I need to re work that part, I guess. I will try it, as you suggest, and put it into the stackType type. Just so I'm on the same page, when I peek, I should set it to true...

Here is what I have now....

I still end up scheduling the same job over and over and getting in an infinite loop...

Any thoughts?

Code:

void solveIter()
{
    stack<StackStructType> callStack;
    StackStructType current;
    int previousJob;

    current.job = 0;
    current.comp = '-';
    current.visited = false;
    callStack.push(current);
    for (int i = Job::getMachPerJob() - 1; i >= 0 ; i--)
    {
        current.comp = jobs[current.job].getComp(i);   
        callStack.push(current);
    }
    while (!callStack.empty())
    {
        current = callStack.top();
        callStack.pop();
        
        if (!current.visited)
        {
            if (current.comp != '-')
            {
                numOfJobs++;
                
                if (numOfJobs > currentBest)
                {
                    currentBest = numOfJobs;
                    best = jobs;
                }
                computers[current.comp - 97].addJob(jobs[current.job].getEnd());
                jobs[current.job].setSchedule(current.comp);
                current.visited = true;
                callStack.push(current);
            }
            if (current.job + 1 < jobSize)
            {
                current.job += 1;
                current.comp = '-';
                callStack.push(current);
                
                for (int i = Job::getMachPerJob() - 1; i >= 0; i--)
                {
                    if (computers[jobs[current.job].getComp(i) - 97].isAvailable(jobs[current.job].getStart()))
                    {
                        current.comp = jobs[current.job].getComp(i);   
                        callStack.push(current);
                        
                    }
                }
                continue;
            }
        }
        current = callStack.top();
        callStack.pop();
        cout << "Returning from " << current.job << "," << current.comp << endl;
        if (current.comp != '-')
        {
            numOfJobs--;
            computers[current.comp - 97].removeJob();            
        }
    }
}

I'm gonna have to go back to the original recursive solution and think about coverting it - (I'm too lazy to digest the code you've already done )

gg

Ok, the original recursive algorithm (that works):

Code:

void solveRecurse(int currentJob)
{
1     char currentJobSched = jobs[currentJob].getSchedule();
2     int jobSize = jobs.size();
3     char getComp;
4 
5     if (currentJobSched != '-' && currentJob >= 0)
6     {
7         numOfJobs++;        
8         if (numOfJobs > currentBest)
9         {
10            currentBest = numOfJobs;
11            best = jobs;
12        }
13        computers[currentJobSched - 97].addJob(jobs[c4urrentJob].getEnd());        
14    }
15    if (currentJob + 1 < jobSize)
16    {
17        for (int i = 0; i < Job::getMachPerJob(); i++)
18        {            
19            getComp = jobs[currentJob + 1].getComp(i);
20            if (computers[getComp - 97].isAvailable(jobs[currentJob + 1].getStart()))
21            {
22                jobs[currentJob + 1].setSchedule(getComp);
23                solveRecurse(currentJob + 1);
24            }
25        }
26        jobs[currentJob + 1].setSchedule('-');
27        solveRecurse(currentJob + 1);
28    }    
29    if (currentJobSched != '-' && currentJob >= 0)
30    {
31        computers[currentJobSched - 97].removeJob();
32        numOfJobs--;
33    }    
}

And here is the speudo code for an iterative implementation of a tail-recursive algorithm:

Code:

//prime the pump
push initial locals

WHILE stack not empty
   //this is our "recursive" entry point, peek the TOS to get locals
   ...
   //to mimic a recursive call, push and continue
   ...
   //to mimic a "return", pop and continue
ENDWHILE

The problem is that the recursive algorithm is not tail recursive. Namely, both recursive calls on lines 23 and 27 both need to do additional work when the recursive calls return.
So my idea is to expand the functionality at the top of the WHILE to being not only the recursive entry point, but also the "do post recursive call work".

To accoplish this, each stack frame will also keep up with the following state information:
- in recursion site 1 call (line 23)
- in recursion site 2 call (line 27)
Then, to mimic a recusive call on lines 23 and 27 you will:

Code:

   set state in current frame (TOS), "in recursion site [1,2] call"
   push frame for new recursive call
   continue

The WHILE loop will then look something like:

Code:

WHILE stack not empty
   peek TOS to get current frame
   IF in recursion site 1 call
      do work that follows site 1 call
   ELSE IF in recursion site 2 call
      do work that follows site 2 call
   ELSE
      do work for a "fresh" call
   ENDIF
ENDWHILE

As is, this will have a LOT of redundant code since "work after site 1" includes "work after site 2", and the final ELSE contains all that work.........if there were ever a reason to use goto's THIS IS IT! Its a rare opportunity indeed, lets relish it
So we can keep the original form and just place some labels right after the "continue" that represents the recursive call mimic for lines 23 and 27. The WHILE loop then looks like:

Code:

WHILE stack not empty
   peek TOS to get current frame
   IF in recursion site 1 call
      goto post_site_1_call
   ELSE IF in recursion site 2 call
      goto post_site_2_call
   ENDIF

   do work for a "fresh" call
ENDWHILE

What do you think?

gg

Hmmm, I'm not following (this is all new to me)...

What do you mean "set state in current frame" ? Because, if you want to know from which recursive call it came from, that is easily determined: If it came from line 27, the comp member of the stack will contain a '-'. Otherwise, it will contain a letter.

Unfortunatly, I don't understand the benifit of knowing which recursive call it came from...or is that not our goal?

Well, my goal was to minimize complexity by "re-using" the recursive implementation that already works - instead of coming up with new logic for the core algorithm.

Yes, all we need to know is "from what call-site are we returning" or "is this a fresh call". If the TOS is "returning" from a recursive call site, then "goto" just past that call site - as if it actually "return"ed there.

gg