20-CS-122-001 Computer Science II Spring 2012
Hints For Homework Assignment 3

Virtual functions, classes, inheritance, lists, queues, stacks, applications

Assembly Line Scheduling

Use recursion! Each SubassemblyType object (also known as a Node object in the hope of making things clearer for some) has a procedure topo which approximately does the following:
   enum State { START, ERROR, DONE };
   State state = START;
   Node **depends;                   // Pointers to dependent objects
   int ndepends;                     // Number of dependent objects
   void topo () {
      if (state == DONE) return;     // We are done already so we do nothing.
      if (state == ERROR) {          // If topo() is invoked when state == ERROR then
         cout << "\nCycle:\n";       // there is a cycle - so exit.
      state = ERROR;                 // Switch to the error state - if invoked at this
                                     // point, this node has not yet finished with its
                                     // dependencies so there must be a cycle.

      for (int i=0 ; i < ndepends ; i++) depends[i]->topo();

      cout << " " << ident;          // All dependencies have been printed, so
      state = DONE;                  // now it is this node's turn to be printed.
   }                                 // So print its ID and switch to state 
                                     // DONE (always returns immediately
                                     // after this).

A power point presentation showing how to build topo classes is found here