2 /* --------------------------------------------------------------------------
3 * Strongly connected components algorithm for static.c.
5 * Hugs 98 is Copyright (c) Mark P Jones, Alastair Reid and the Yale
6 * Haskell Group 1994-99, and is distributed as Open Source software
7 * under the Artistic License; see the file "Artistic" that is included
8 * in the distribution for details.
12 * $Date: 1999/04/27 10:07:01 $
13 * ------------------------------------------------------------------------*/
17 #define visited(d) (isInt(DEPENDS(d))) /* binding already visited?*/
19 static Cell daSccs = NIL;
22 static Int local sccMin Args((Int,Int));
24 static Int local sccMin(x,y) /* calculate minimum of x,y */
25 Int x, y; { /* (unless y is zero) */
26 return (x<=y || y==0) ? x : y;
30 /* --------------------------------------------------------------------------
31 * A couple of parts of this program require an algorithm for sorting a list
32 * of values (with some added dependency information) into a list of strongly
33 * connected components in which each value appears before its dependents.
35 * The algorithm used here is based on those described in:
36 * 1) Robert Tarjan, Depth-first search and Linear Graph Algorithms,
37 * SIAM J COMPUT, vol 1, no 2, June 1972, pp.146-160.
38 * 2) Aho, Hopcroft and Ullman, Design and Analysis of Algorithms,
39 * Addison Wesley, 1972. pp.189-195.
40 * The version used here probably owes most to the latter presentation but
41 * has been modified to simplify the algorithm and improve the use of space.
43 * This would probably have been a good application for C++ templates ...
44 * ------------------------------------------------------------------------*/
46 static Int local LOWLINK Args((Cell)); /* local function */
47 static Int local LOWLINK(v) /* calculate `lowlink' of v */
50 Int dfn = daCount; /* depth first search no. of v */
51 List ws = DEPENDS(v); /* adjacency list for v */
53 SETDEPENDS(v,mkInt(daCount++)); /* push v onto stack */
56 while (nonNull(ws)) { /* scan adjacency list for v */
59 low = sccMin(low, (visited(w) ? intOf(DEPENDS(w)) : LOWLINK(w)));
62 if (low == dfn) { /* start a new scc? */
64 do { /* take elements from stack */
65 SETDEPENDS(top(),mkInt(0));
66 temp = cons(top(),temp);
68 daSccs = cons(temp,daSccs); /* make new strongly connected comp*/
75 static List local SCC(bs) /* sort list with added dependency */
76 List bs; { /* info into SCCs */
79 daSccs = NIL; /* clear current list of SCCs */
81 for (daCount=1; nonNull(bs); bs=tl(bs)) /* visit each binding */
86 return tmp; /* reverse to obtain correct order */
90 #ifdef SCC2 /* Two argument version */
91 static List local SCC2(bs,cs) /* sort lists with added dependency*/
92 List bs, cs; { /* info into SCCs */
95 daSccs = NIL; /* clear current list of SCCs */
97 for (daCount=1; nonNull(bs); bs=tl(bs)) /* visit each binding */
100 for (; nonNull(cs); cs=tl(cs))
101 if (!visited(hd(cs)))
105 return tmp; /* reverse to obtain correct order */
109 /*-------------------------------------------------------------------------*/