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

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

Assembly Line Scheduling

Due: April 26, 2012 (submit instructions: here)


Rationale:

This homework exercises your ability to use classes and think recursively. A reasonable solution is ridiculously short and yet the problem is one of the most important we will encounter in Computer Science.

Background:

A factory which produces complex machinery on a single assembly line may need to take some care in planning which subassemblies or components are completed at what point on the line. For, if a component type is scheduled for completion after it is supposed to be installed then a problem will certainly exist. The problem is compounded by the fact that duplicates of the same component type may be used many times in assembling other components which themselves may be used many times and so on.

We wish to find an order of assembly of components on a single production line so that no component requires a subassembly that has not been built earlier in the line. We again turn to graphs to help devise a solution. Use a vertex (a circle on a piece of paper) to represent a component type. If one component type, call it A, requires another, say B, then draw a line between the two circles representing type A and B with an arrowhead pointing in the direction of the B vertex. The arrow tells us that we cannot build A components before we build B components. In other words, we say A is dependent on B. For example, in the following picture

no component can be built before E or D components are, A components must wait until D and G components are completed, and so on. If the component assemblies are scheduled in the following order (left first)

 E, G, H, B, F, D, A, C, I, J 
then all the components can be assembled successfully. By the way, a graph with arrows as above is referred to as a partial ordering of elements (in this case component types A through J) and an ordering such as the one above, where all dependencies are satisfied, is called a topological sort of the elements of the partial order (in this case, of components A through J). If the graph were such that for some vertex you could visit one or more other vertices by moving in the direction of the arrows, and then return to the vertex at which you started, then the graph is not a partial ordering and a topological sort is impossible.

Purpose:

Use classes in a meaningful way, to represent objects. Use notions of recursion to simplify the search for the next object to be output: each object will have a function that invokes a function of the same name associated with each of its "neighbors" (as determined by the arrows leaving it) and the purpose of the function will be to insure all dependent objects are output before the current object is output. Read input data from a file; make multiple passes through the data file to avoid using constants to establish memory for data structures.

Homework Problem:

Write a program to determine a topological sort of the elements of a given partial ordering. This problem and an outline of the code you can write are as follows:

Topological Sort Problem:

Given a collection of n items and dependency lists for each item, determine whether the dependencies support a topological sort. If not, report this fact. Otherwise, find a topological sort of the vertices with respect to the given dependency lists. A topological sort of the items is a permutation of the items with the property that every item in the permutation is to the right of all items in its dependency list.

Example:

Given above.

Method:

input: A graph of vertices and lines with arrowheads in one direction
output: "Impossible" or a topological sort of the vertices

    0. Create objects for each vertex
    1. Set the state of each object to START
    2. Install all the dependency lists for all vertices from file
    3. For all vertices v execute topo(v) given below
       (imagine there is one copy of that code for each vertex)

topo:
input: A vertex v - invoked as topo(v)

    1. Check whether v is in the DONE state
    2. If so, return
    3. Check whether v is in the ERROR state
    4. If so, print "Impossible" and exit
    5. Change v's state to ERROR
    6. For all the vertices w in the dependency list of v do the following:
    6a.   Invoke topo(w)
    7. Change v's state to DONE
    8. Print "v"
    9. Return

This Power Point Presentation illustrates the action of the above method. In particular, 1) a vertex in the START state is colored blue, a vertex in the ERROR state is colored brown and a vertex in the DONE state is colored yellow; 2) a black line with arrow from one vertex (call it v) to another vertex (call it w) means, in the context of the above method, execute line 6a; 3) if a line is colored magenta, then that execution is in progress; 4) if a line is colored green then that execution is completed.

Analysis:

  1. The meaning of topo(v) is: output all objects v depends on then output v.

  2. Method topo(v) is designed so that v is output at most one time, regardless of how many times topo(v) is invoked: the only time v can be output is if the state of v is START when topo(v) is first invoked and the state of v is changed to ERROR immediately after this invocation, never to be set to START again.

  3. From 1. and 2. above, the For statement of Line 3. in the first of the two procedures above is enough to print a topological sort.

  4. All objects v depends on are output on Lines 6. and 6a. of topo(v) by the description of point 1. above. Then v is output. This happens once due to the state variable. Hence point 1. is justisfied inductively.


Requirements:

  1. Functional requirements:
    1. The program shall read a text file and display the results to the console.
    2. The input file shall be identified on the command line (that is, use int main(int argc, char **argv)).
    3. The input file shall contain printable ascii characters only plus newline characters for terminating a line.
    4. Enumerate all components and subassemblies (called objects below) from 0 to n-1 (assuming there are n such objects given). The 0th line shall name all the components and subassemblies to be represented by vertices. All names are to be separated by blanks. The line shall end with a '-' character after a blank. The first name corresponds to object 0, the second to object 1 and so on.
    5. Each additional line of the input file shall contain a sequence of positive integers, separated by blanks, with a blank-separated terminating character of '-'. The ith line (after the 0th) is the dependency list for the i-1st object.
    6. See topo.0.dat for an example input file.
    7. The output will consist of the names of all objects in topological order. See topo.result.0 for the output corresponding to the above problem.

  2. Performance requirements:
    1. Time: Less than 0.1 seconds to read a 1000 object file such as topo.1000.dat on a hard drive of 20 MB/s throughput. Less than 0.1 seconds to topologically sort 1000 input objects on a 1 GHz or faster i386 or compatible architecture.
    2. Space: Less than 3MB of RAM for 1000 objects.

  3. Implementation requirements:
    1. Use a class to organize all object information and methods as follows:
         class SubassemblyType {
            int state;                    // state for execution control
            char *ident;                  // String identifying this object
            SubassemblyType **depends;    // Array of pointers to dependent objects
            int ndepends;                 // Number of dependent objects
      
         public:
            SubassemblyType (char *);     // Constructor: sets ident, state
            void setdeps (SubassemblyType **, int);  // sets dependency list, ndepends
      
            // Topologically sort from this object.  This is accomplished by
            // topologically sorting the dependent objects first then outputting
            // the identity of this object.  The variable "state" is used to
            // prevent the sort from occurring more than once and to detect
            // cycles, if they should exist.
            void topo ();
         };
      
    2. Create an array components of type SubassemblyType* to hold all objects read from the input file (to be clear, the array is declared as follows: SubassemblyType **components;). Use "new" to allocate space after a pass through the first line to determine the number of objects.
    3. Space for the depends array of each object should be allocated using "new" after scanning the file line corresponding to that object to determine the number of dependencies for that object.
    4. Read and process file data so as to avoid "hard wiring" data structure size boundaries into the code. For example, do not use something like this:
         ...
         const int MAX_DEPENDS = 100;
         ...
         depends = new SubassemblyType*[MAX_DEPENDS];
      
      to make space for a dependency list. Instead use something like this:
         ...
         fstream fin;
         fin.open(argv[1],ios::in);
         ...
         for (int i=0 ; i < nobjects ; i++) setDependencies(fin, i, components);
      
      and setDependencies invokes components[i]->setdeps(...). This may require multiple reads of lines.

In Case Of Trouble:

If the problem is understanding classes, see the lecture notes. If the problem is inputting, then embed the dependencies in the text of the code and do not worry about the input process right now. Otherwise, identify the problem to the grader or myself.