home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / modula2 / library / modula1 / topsort.mod < prev    next >
Text File  |  1987-06-11  |  2KB  |  93 lines
  1. (* Read a sequence of relations defining a directed, finite
  2.    graph.  Then establish whether or not a partial ordering
  3.    is defined.  If so, print the element in a sequence showing
  4.    the partial ordering. (Topological sorting)  *)
  5.  
  6. MODULE topsort;
  7.  
  8. FROM InOut   IMPORT WriteLn, WriteCard, ReadCard, WriteString;
  9. FROM Storage IMPORT ALLOCATE;
  10.  
  11. TYPE lref = POINTER TO leader;
  12.  
  13.      tref = POINTER TO trailer;
  14.      
  15.      leader = RECORD
  16.                 key: CARDINAL;
  17.                 count: CARDINAL;
  18.                 trail: tref;
  19.                 next: lref;
  20.               END;
  21.      
  22.      trailer = RECORD
  23.                  id: lref;
  24.                  next: tref
  25.                END;
  26.  
  27. VAR head,tail,p,q: lref;
  28.     t: tref;
  29.     z,x,y: CARDINAL;
  30.  
  31. PROCEDURE l(w: CARDINAL): lref;
  32.   (* reference fo leader with key w *)
  33. VAR h: lref;
  34.  
  35. BEGIN
  36.   h := head;
  37.   tail^.key := w;     (* sentinel *)
  38.   WHILE h^.key # w DO h := h^.next END;
  39.   IF h = tail THEN    (* no element with key w in the list *)
  40.     NEW(tail); INC(z);
  41.     h^.count := 0;
  42.     h^.trail := NIL;
  43.     h^.next := tail
  44.   END;
  45.   RETURN h
  46. END l;
  47.  
  48. BEGIN  (* initialize list of leaders with a dummy *)
  49.   NEW(head); z := 0;
  50.   tail := head;
  51.   LOOP            (* input phase *)
  52.     ReadCard(x);
  53.     IF x = 0 THEN EXIT END;
  54.     ReadCard(y); WriteCard(x,6);
  55.     WriteCard(y,6); WriteLn;
  56.     p := l(x); q := l(y);
  57.     NEW(t); t^.id := q;
  58.     t^.next := p^.trail;
  59.     p^.trail := t;
  60.     INC(q^.count)
  61.   END;
  62.   
  63. (* search for leaders with count = 0 *)
  64.   p := head;
  65.   head := NIL;
  66.   WHILE p # tail DO
  67.     q := p; p := p^.next;
  68.     IF q^.count = 0 THEN
  69.       q^.next := head;
  70.       head := q
  71.     END
  72.   END;
  73.   
  74. (* output phase *)
  75.   q := head;
  76.   WHILE q # NIL DO
  77.     WriteCard(q^.key,6); WriteLn;
  78.     DEC(z);
  79.     t := q^.trail;
  80.     q := q^.next;
  81.     WHILE t # NIL DO
  82.       p := t^.id;
  83.       DEC(p^.count);
  84.       IF p^.count = 0 THEN   (* insert p^ in q-list *)
  85.         p^.next := q;
  86.         q := p
  87.       END;
  88.       t := t^.next
  89.     END
  90.   END;
  91.   IF z # 0 THEN WriteString(' This set is not partially ordered. ') END;
  92. END topsort.
  93.