DOC HOME SITE MAP MAN PAGES GNU INFO SEARCH PRINT BOOK
 
Associative Arrays in C++ - Map(3C++)

The Problem

Our input file consists of words separated by white space (spaces, tabs, newlines). Each word is considered to represent some abstract object; the words are taken in pairs to assert that the first object of each pair is ``less than'' the second. If both words in the pair are the same, that pair just says that the particular word exists without saying anything about its ordering. The problem is to find a single linear ordering that satisfies all the given constraints. This may be impossible because of a loop in the ordering. In that case, the program should say so.

For example, the following input represents some constraints on clothing:

   pants           belt
   left_sock       left_shoe
   right_sock      right_shoe
   shirt           shirt
   pants           left_shoe
   pants           right_shoe

Here, we say that one article of clothing is ``less than'' another if it must be put on before the other. Thus each sock must be put on before the corresponding shoe, it is difficult to put on pants over shoes, one must put one's pants on before one's belt, and there is a shirt in there somewhere.

One ordering that satisfies all these constraints is:

   left_sock
   pants
   right_sock
   shirt
   belt
   left_shoe
   right_shoe

There are others, of course.

Topological sorting is often used to put modules into an appropriate order for load module archives in the UNIX® system; there is therefore a topological sort utility program called tsort available as a standard for comparison.


Next topic: Implementation
Previous topic: Another Example: Topological Sorting

© 2004 The SCO Group, Inc. All rights reserved.
UnixWare 7 Release 7.1.4 - 27 April 2004