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