Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Annotation of /sml/trunk/src/MLRISC/graphs/graph-scc.sml
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/graphs/graph-scc.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 412 - (view) (download)

1 : monnier 245 (*
2 : monnier 411 * Tarjan's algorithm
3 :     *
4 :     * This module computes strongly connected components (SCC) of
5 :     * a graph. Each SCC is represented as a list of nodes. All nodes
6 :     * are folded together with a user supplied function.
7 :     *
8 :     * -- Allen
9 : monnier 245 *)
10 : monnier 411
11 : monnier 245 structure GraphSCC : GRAPH_STRONGLY_CONNECTED_COMPONENTS =
12 :     struct
13 :    
14 :     structure G = Graph
15 :     structure A = Array
16 :    
17 : monnier 411 fun strong_components (G.GRAPH G) process S =
18 : monnier 245 let val N = #capacity G ()
19 : monnier 411 val onstack = Word8Array.array(N,0w0)
20 : monnier 245 val dfsnum = A.array(N,~1)
21 :     fun dfs(v,num,stack,S) =
22 :     let val dfsnum_v = num
23 :     fun f([],num,stack,low_v,S) = (num,stack,low_v,S)
24 :     | f((_,w,_)::es,num,stack,low_v,S) =
25 :     let val dfsnum_w = A.sub(dfsnum,w)
26 :     in if dfsnum_w = ~1 then
27 :     let val (num,stack,dfsnum_w,low_w,S) = dfs(w,num,stack,S)
28 :     in f(es,num,stack,Int.min(low_v,low_w),S) end
29 :     else
30 : monnier 411 if dfsnum_w < dfsnum_v andalso
31 :     Word8Array.sub(onstack,w) = 0w1
32 : monnier 245 then f(es,num,stack,Int.min(dfsnum_w,low_v),S)
33 :     else
34 :     f(es,num,stack,low_v,S)
35 :     end
36 :     val _ = A.update(dfsnum,v,dfsnum_v)
37 : monnier 411 val _ = Word8Array.update(onstack,v,0w1)
38 : monnier 245 val (num,stack,low_v,S) =
39 :     f(#out_edges G v,num+1,v::stack,dfsnum_v,S)
40 :     fun pop([],SCC,S) = ([],S)
41 :     | pop(x::stack,SCC,S) =
42 :     let val SCC = x::SCC
43 : monnier 411 val _ = Word8Array.update(onstack,x,0w0)
44 : monnier 245 in if x = v then (stack,process(SCC,S))
45 :     else pop(stack,SCC,S)
46 :     end
47 :     val (stack,S) = if low_v = dfsnum_v then pop(stack,[],S)
48 :     else (stack,S)
49 :     in (num,stack,dfsnum_v,low_v,S)
50 :     end
51 :     fun dfsAll([],S) = S
52 :     | dfsAll((n,_)::nodes,S) =
53 :     if A.sub(dfsnum,n) = ~1 then
54 :     let val (_,_,_,_,S) = dfs(n,0,[],S)
55 :     in dfsAll(nodes,S) end
56 :     else dfsAll(nodes,S)
57 :     in dfsAll(#nodes G (),S)
58 :     end
59 :    
60 :     end
61 :    

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0