Assignment 1
CS 152                    (100 points)          due September 24, 1997



    The topological sort problem takes a set of tasks, and a
prerequisite relation defined on those tasks, and returns a sequence
containing all the tasks with the property that each task appears
only after all of its prerequisites (if such a sequence exists).
Examples are given on pp. 278-282 of the text, where the set of
prerequisites is represented by a directed graph.

    For this assignment, the relation is specified by giving a list
of its pairs, while the set of tasks is defined implicitly as those
elements appearing in any member of the prerequisite relation.  You
may assume that each task is represented by a task name, taking the
form of a character string with no internal spaces.  For output, you
need only print the names of those tasks that may be completed (in
their appropriate output order); you needn't return an explicit
structure.  Output may be sent either to the screen (standard output)
or to a file.

    The topological sort algorithm first traverses the prerequisite
relation to determine for each task (1) the number of prerequisites
it has, and (2) the list of tasks for which it is a prerequisite.  It
then repeatedly looks for a task with no unmet prerequisites, adds it
to the output list, and decrements the number of unmet prerequisites
for each task for which it is a prerequisite.  It can be shown that
an instance of the topological sort problem has a solution iff the
algorithm can always find a task with no unmet prerequisites (before
each task has been output) iff there is no directed cycle in the
directed graph representing the prerequisite relation.

    For Assignment 1, you are to write a program in C to implement and
test the topological sort algorithm.  Do not use C++ constructions in
this program.  Your tests should include at least
the 7 data files I have publicized (those with extensions .DAT), as
well as a nonexistent file.  You should be able to detect and respond
with an appropriate error message to at least the following types of
errors:

    1)  nonexistent files
    2)  ill-formed input files due to an odd number of tasks
    3)  cycles of prerequisites

In the 3rd case you should print out those tasks (in the appropriate
order) that can be accomplished.  In the other cases you needn't
attempt to apply the topological sort algorithm.