## warshall.a68

```
1  CO
2
3  @section Synopsis
4
5  Warshall's algorithm for transitive closures.
6
7  This code demonstrates a68g's small refinement preprocessor.
8  At the University of Nijmegen a preprocessor much like this one was used
9  as a front-end to FLACC in freshman programming courses in the 1980's.
10
11  See:
12
13    C.H.A. Koster, H. Meijer.
14    Systematisch programmeren in Algol 68, Deel I en II.
15    Kluwer, Deventer [1978, 1981].
16
17  CO
18
19  # Suppose a compiler finds four procedures that call each other
20    according below matrix.
21    Entry calls[j, k] means procedure 'j' calls 'k' directly.
22  #
23
24  INT n = 4;
25
26  MODE RELATION = [n, n] BOOL;
27
28  RELATION calls = ((FALSE, TRUE, FALSE, FALSE),
29                    (FALSE, FALSE, TRUE, FALSE),
30                    (FALSE, FALSE, FALSE, TRUE),
31                    (FALSE, FALSE, FALSE, FALSE)
32                   );
33
34  # Warshall's algorithm computes the transitive closure.
35    Entry warshall[j, k] means that 'j' calls 'k', either
36    directly or indirectly.
37  #
38
39  PROC warshall = (RELATION direct) RELATION:
40       (transitive closure);
41
42  print relations.
43
44  # The refinements follow below #
45
46     transitive closure:
47        RELATION indirect := direct;
48        construct indirect;
49        indirect.
50
51        construct indirect:
52           FOR m TO n
53           DO FOR s TO n
54              DO FOR t TO n
55                 DO indirect[s, t] := indirect[s, t] OR (indirect[s, m] AND indirect[m, t])
56                 OD
57              OD
58           OD.
59
60     print relations:
61        printf (\$"direct:"l\$);
62        printf ((\$n(n)(g)l\$, calls));
63        printf (\$"indirect:"l\$);
64        printf ((\$n(n)(g)l\$, warshall (calls))).

```

 © 2002-2024 J.M. van der Veer (jmvdveer@xs4all.nl)