Learning Topological sort with Ocaml with Kahns Algorithmn

Your program must take in a list of tasks and either output an order in which to perform them or the single word cycle.

Your program will accept a number of lines of textual input (via standard input). There are no command-line arguments you must always read from standard input. Do not open a named file. Instead, always read from standard input.

That text input will contain a non-zero but even number of lines. Every two lines represent a pair of tasks. The first line gives the name of a task, the second line gives the name of a task that it depends on. This text input is also called the task list.

The task list will contain only standard ASCII characters (no UTF/8 Unicode or special accents). The goal is to test programming and program language concepts, not your internationalization abilities.

Each task name starts at the beginning of the line and extends all the way up to (but not including) the end of that line. So the newline or carriage return characters or are not part of the task name. Each task name is at most 60 characters long. (This limit is to make the C implementation easier; if you can support longer strings natively, feel free to do so.)

Example task list:

learn C

read the C tutorial

do PA1

learn C

The interpretation is that in order to learn C one must first read the C tutorial and that in order to do PA1 one must first learn C. Desired output for this example:

read the C tutorial

learn C

do PA1

If the task list containts a cycle of any size, your program should output exactly and only the word cycle. Example cyclic input:

get a job

have experience

have experience

work on a job

work on a job

get a job

Even if the task list contains a few non-cyclic parts, any single cycle forces you to output only the word cycle.

There is no fixed limit on the number of lines in the task list (although it is not zero and it is even).

Two tasks with the same name are really just the same task. Use standard string equality.

Duplicated pairs of tasks are not allowed. For example:

learn C

read the C tutorial

do PA1

learn C

learn C

read the C tutorial

... that task list is not valid input because the pair learn C/read the C tutorial appears twice. Program behavior if the task list contains a duplicate pair is undefined. You will not be tested on it.

Your program may not perform any other file I/O, such as creating a temporary file to keep track of some intermediate sorting results. You do not need to create any such temporary files to solve this problem.

Choosing Among Unconstrained Tasks

If there are multiple outstanding unconstrained tasks, your program should output them in ascending ASCII alphabetical order. That is, if you ever have two or more tasks, each of which has no remaining dependencies, output the one that comes first ASCII-alphabetically. (This constraint makes your program deterministic; for any given input there is only one correct output.) Example:

learn C

understand C pointers

learn C

read the C tutorial

do PA1

learn C

Because r comes before u, your output should be:

read the C tutorial

understand C pointers

learn C

do PA1

The proper ordering for this set of tasks is A B D E C. Note that B comes before D and E, even though B depends on A. This is because, once A is finished, B is free to go and it comes first alphabetically. You may want to consider this requirement when you pick your sorting algorithm. Given this requirement the answer A D E B C is incorrect and will receive no credit.

Commentary

This problem is just topological sort not-so-cleverly disguised.

Building and maintaining explicit graph structure is probably overkill.

Since you do not know the number of tasks in advance you will need some sort of dynamic memory allocation. You must solve this by coding in Ocaml