1 /* -*- mode: hugs-c; -*- */
2 /* --------------------------------------------------------------------------
3 * Strongly connected components algorithm for static.c.
5 * Copyright (c) The University of Nottingham and Yale University, 1994-1997.
6 * All rights reserved. See NOTICE for details and conditions of use etc...
7 * Hugs version 1.4, December 1997
11 * $Date: 1998/12/02 13:22:34 $
12 * ------------------------------------------------------------------------*/
16 #define visited(d) (isInt(DEPENDS(d))) /* binding already visited ? */
18 static Cell daSccs = NIL;
21 static Int local sccMin Args((Int,Int));
23 static Int local sccMin(x,y) /* calculate minimum of x,y (unless */
24 Int x,y; { /* 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 Args((Cell)); /* local function */
46 static Int local LOWLINK(v) /* calculate `lowlink' of v */
49 Int dfn = daCount; /* depth first search no. of v */
50 List ws = DEPENDS(v); /* adjacency list for v */
52 SETDEPENDS(v,mkInt(daCount++)); /* push v onto stack */
55 while (nonNull(ws)) { /* scan adjacency list for v */
58 low = sccMin(low, (visited(w) ? intOf(DEPENDS(w)) : LOWLINK(w)));
61 if (low == dfn) { /* start a new scc? */
63 do { /* take elements from stack */
64 SETDEPENDS(top(),mkInt(0));
65 temp = cons(top(),temp);
67 daSccs = cons(temp,daSccs); /* make new strongly connected comp*/
74 static List local SCC(bs) /* sort list with added dependency */
75 List bs; { /* info into SCCs */
77 daSccs = NIL; /* clear current list of SCCs */
79 for (daCount=1; nonNull(bs); bs=tl(bs)) /* visit each binding */
83 return rev(daSccs); /* reverse to obtain correct order */
87 #ifdef SCC2 /* Two argument version */
88 static List local SCC2(bs,cs) /* sort lists with added dependency*/
89 List bs, cs; { /* info into SCCs */
91 daSccs = NIL; /* clear current list of SCCs */
93 for (daCount=1; nonNull(bs); bs=tl(bs)) /* visit each binding */
96 for (; nonNull(cs); cs=tl(cs))
100 return rev(daSccs); /* reverse to obtain correct order */
104 /*-------------------------------------------------------------------------*/