home *** CD-ROM | disk | FTP | other *** search
/ Media Share 9 / MEDIASHARE_09.ISO / progmisc / ad12.zip / TOPOSORT.AD < prev   
Text File  |  1990-03-02  |  1KB  |  47 lines
  1.  ┌ * Algorithm for topological sort
  2.  │ 
  3.  │ * Input:  a set of ordered pairs that respresents a partial order.
  4.  │ 
  5.  │ * Output: a total order in which which the partial order is embedded.
  6.  │ 
  7.  │ * Data structures
  8.  │ *     Assume a dictionary of items to be sorted.
  9.  │ *     Must be able to store with each item the number of its
  10.  │ *       predecessors and a pointer to a linked list of its
  11.  │ *       successors in the partial order.
  12.  │ 
  13.  │ * Based on algorithm given in Data Structures and C Programs,
  14.  │ * C.J. Van Wyk
  15.  │ 
  16.  │ ┌ * Initialize data structures
  17.  │ │ 
  18.  │ │ ╔ For Each ordered pair (a, b) in the input
  19.  │ │ ║ Add 1 to b's count of predecessors
  20.  │ │ ║ Add b to a's list of successors
  21.  │ │ ╚ End For
  22.  │ │ 
  23.  │ │ Enqueue each item that has no predecessors
  24.  │ └  
  25.  │ 
  26.  │ ┌ * Construct topological order
  27.  │ │ 
  28.  │ │ ╔ While the queue is not empty
  29.  │ │ ║ 
  30.  │ │ ║ ╔ For Each successor of the item at the head of the queue
  31.  │ │ ║ ║ 
  32.  │ │ ║ ║ Subtract 1 from its predecessor count
  33.  │ │ ║ ║ 
  34.  │ │ ║ ║ ╒ If its predecessor count is zero
  35.  │ │ ║ ║ │ Enqueue it
  36.  │ │ ║ ║ └ End If
  37.  │ │ ║ ║ 
  38.  │ │ ║ ╚ End For
  39.  │ │ ║ 
  40.  │ │ ║ Dequeue and output the item at the head of the queue
  41.  │ │ ║ 
  42.  │ │ ╚ End While
  43.  │ │ 
  44.  │ └  
  45.  │ 
  46.  └ 
  47.