2 /* --------------------------------------------------------------------------
3 * Strongly connected components algorithm for static.c.
5 * The Hugs 98 system is Copyright (c) Mark P Jones, Alastair Reid, the
6 * Yale Haskell Group, and the Oregon Graduate Institute of Science and
7 * Technology, 1994-1999, All rights reserved. It is distributed as
8 * free software under the license in the file "License", which is
9 * included in the distribution.
13 * $Date: 2000/03/22 18:14:23 $
14 * ------------------------------------------------------------------------*/
18 #define visited(d) (isInt(DEPENDS(d))) /* binding already visited?*/
20 static Cell daSccs = NIL;
23 static Int local sccMin ( Int x, Int y) /* calculate minimum of x,y */
24 { /* (unless y is zero) */
25 return (x<=y || y==0) ? x : y;
29 /* --------------------------------------------------------------------------
30 * A couple of parts of this program require an algorithm for sorting a list
31 * of values (with some added dependency information) into a list of strongly
32 * connected components in which each value appears before its dependents.
34 * The algorithm used here is based on those described in:
35 * 1) Robert Tarjan, Depth-first search and Linear Graph Algorithms,
36 * SIAM J COMPUT, vol 1, no 2, June 1972, pp.146-160.
37 * 2) Aho, Hopcroft and Ullman, Design and Analysis of Algorithms,
38 * Addison Wesley, 1972. pp.189-195.
39 * The version used here probably owes most to the latter presentation but
40 * has been modified to simplify the algorithm and improve the use of space.
42 * This would probably have been a good application for C++ templates ...
43 * ------------------------------------------------------------------------*/
45 static Int local LOWLINK( Cell v ) /* calculate `lowlink' of v */
48 Int dfn = daCount; /* depth first search no. of v */
49 List ws = DEPENDS(v); /* adjacency list for v */
51 SETDEPENDS(v,mkInt(daCount++)); /* push v onto stack */
54 while (nonNull(ws)) { /* scan adjacency list for v */
57 low = sccMin(low, (visited(w) ? intOf(DEPENDS(w)) : LOWLINK(w)));
60 if (low == dfn) { /* start a new scc? */
62 do { /* take elements from stack */
63 SETDEPENDS(top(),mkInt(0));
64 temp = cons(top(),temp);
66 daSccs = cons(temp,daSccs); /* make new strongly connected comp*/
73 static List local SCC ( List bs ) /* sort list with added dependency */
74 { /* info into SCCs */
77 daSccs = NIL; /* clear current list of SCCs */
79 for (daCount=1; nonNull(bs); bs=tl(bs)) /* visit each binding */
84 return tmp; /* reverse to obtain correct order */
88 #ifdef SCC2 /* Two argument version */
89 static List local SCC2 ( List bs,
90 List cs ) /* sort lists with added dependency*/
91 { /* info into SCCs */
94 daSccs = NIL; /* clear current list of SCCs */
96 for (daCount=1; nonNull(bs); bs=tl(bs)) /* visit each binding */
99 for (; nonNull(cs); cs=tl(cs))
100 if (!visited(hd(cs)))
104 return tmp; /* reverse to obtain correct order */
108 /*-------------------------------------------------------------------------*/