Thread: Iterative Tree Traversal using a stack

  1. #1
    Registered User
    Join Date
    Apr 2002
    Posts
    80

    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();
            }
        }
    }
    Last edited by BigDaddyDrew; 03-09-2003 at 07:12 PM.

  2. #2
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,981
    What about something like visited in the StackStructType?

    gg

  3. #3
    Registered User
    Join Date
    Apr 2002
    Posts
    80
    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...
    Last edited by BigDaddyDrew; 03-10-2003 at 09:46 AM.

  4. #4
    Registered User
    Join Date
    Apr 2002
    Posts
    80
    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();            
            }
        }
    }

  5. #5
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,981
    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

  6. #6
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,981
    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

  7. #7
    Registered User
    Join Date
    Apr 2002
    Posts
    80
    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?

  8. #8
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,981
    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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 05:59 PM
  2. stack and pointer problem
    By ramaadhitia in forum C Programming
    Replies: 2
    Last Post: 09-11-2006, 11:41 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM