Senior: Topological Sort Section A

Problem: Large projects require the co-ordination of many tasks so that they are completed at the right time. Different tasks require other tasks to be completed before they can start (e.g., in building a house, it is usually necessary that the basement be dug before the first floor is built). Your challenge is to create a program that will print out the order that tasks should be completed. For your trivia knowledge, the computation you are performing is called a "Topological Sort", a term that comes from mathematical graph theory.

Note that it is possible to enter a sequence of tasks in which some cannot be prioritised. Your program should print a message when it is impossible to sort the tasks.

Input: The program must repeatedly accept the name of a task and then the name of the task it depends on (see sample). Task names are single words that are not more than 10 letters long. When the word "Done" is read, the information is finished and the program should compute the order. There will be a maximum of fifteen entries before the "Done" command is issued. Note that the same task could depend on more than one other tasks (see sample).

Output: The program must print the order of the tasks to be complete. Tasks should be done as soon as possible. Also, ignore the possibility of some tasks taking longer or shorter to complete than other tasks. It may be possible to do a task at the same time as other tasks are being done if they don’t depend on each other (e.g., in building a house, the plumber can put in the sink at the same time as the doors are being put in by other workers). Print one "level" of tasks per line. Each level contains tasks that must be done after tasks in the previous levels (see samples).

Samples:

Enter task name: Walls

‘Walls’ depends on: Basement

Enter task name: Electric

‘Electric’ depends on: Walls

Enter task name: Plumbing

‘Plumbing’ depends on: Walls

Enter task name: FuseBox

‘FuseBox’ depends on: Electric

Enter task name: Fridge

‘Fridge’ depends on: Plumbing

Enter task name: Fridge

‘Fridge’ depends on: FuseBox

Enter task name: Done

The tasks to be done in order:

Level 1: Basement

Level 2: Walls

Level 3: Electric Plumbing

Level 4: FuseBox

Level 5: Fridge

Again? (Y/n) Y

Enter task name: Walls

‘Walls’ depends on: Basement

Enter task name: Electric

‘Electric’ depends on: Walls

Enter task name: Plumbing

‘Plumbing’ depends on: Walls

Enter task name: FuseBox

‘FuseBox’ depends on: Electric

Enter task name: Walls

‘Walls’ depends on: FuseBox

Enter task name: Fridge

‘Fridge’ depends on: FuseBox

Enter task name: Done

The tasks cannot be prioritised.

Again? (Y/n) N

 

If you can’t tell why this is impossible, try it by hand.

 

 


Last Modified:- 1999, May 16, 06:24 PM by M. Smith