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

# SCM Repository

[smlnj] Diff of /sml/branches/SMLNJ/src/MLRISC/graphs/graph-scc.sml
 [smlnj] / sml / branches / SMLNJ / src / MLRISC / graphs / graph-scc.sml

# Diff of /sml/branches/SMLNJ/src/MLRISC/graphs/graph-scc.sml

revision 410, Fri Sep 3 00:25:03 1999 UTC revision 411, Fri Sep 3 00:25:03 1999 UTC
# Line 1  Line 1
1  (*  (*
2   *  Tarjan's algorithm   *  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   *)   *)
10
11  structure GraphSCC : GRAPH_STRONGLY_CONNECTED_COMPONENTS =  structure GraphSCC : GRAPH_STRONGLY_CONNECTED_COMPONENTS =
12  struct  struct
13
14     structure G = Graph     structure G = Graph
15     structure A = Array     structure A = Array
16
17     fun scc (G.GRAPH G) process S =     fun strong_components (G.GRAPH G) process S =
18     let val N = #capacity G ()     let val N = #capacity G ()
19         val onstack = BitSet.create N         val onstack = Word8Array.array(N,0w0)
20         val dfsnum = A.array(N,~1)         val dfsnum = A.array(N,~1)
21         fun dfs(v,num,stack,S) =         fun dfs(v,num,stack,S) =
22         let val dfsnum_v = num         let val dfsnum_v = num
# Line 20  Line 27
27                       let val (num,stack,dfsnum_w,low_w,S) = dfs(w,num,stack,S)                       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                       in  f(es,num,stack,Int.min(low_v,low_w),S) end
29                     else                     else
30                       if dfsnum_w < dfsnum_v andalso BitSet.contains(onstack,w)                       if dfsnum_w < dfsnum_v andalso
31                            Word8Array.sub(onstack,w) = 0w1
32                       then f(es,num,stack,Int.min(dfsnum_w,low_v),S)                       then f(es,num,stack,Int.min(dfsnum_w,low_v),S)
33                     else                     else
34                        f(es,num,stack,low_v,S)                        f(es,num,stack,low_v,S)
35                 end                 end
36             val _ = A.update(dfsnum,v,dfsnum_v)             val _ = A.update(dfsnum,v,dfsnum_v)
37             val _ = BitSet.set(onstack,v)             val _ = Word8Array.update(onstack,v,0w1)
38             val (num,stack,low_v,S) =             val (num,stack,low_v,S) =
39                    f(#out_edges G v,num+1,v::stack,dfsnum_v,S)                    f(#out_edges G v,num+1,v::stack,dfsnum_v,S)
40             fun pop([],SCC,S) = ([],S)             fun pop([],SCC,S) = ([],S)
41               | pop(x::stack,SCC,S) =               | pop(x::stack,SCC,S) =
42                   let val SCC = x::SCC                   let val SCC = x::SCC
43                       val _   = BitSet.reset(onstack,x)                       val _   = Word8Array.update(onstack,x,0w0)
44                   in  if x = v then (stack,process(SCC,S))                   in  if x = v then (stack,process(SCC,S))
45                       else pop(stack,SCC,S)                       else pop(stack,SCC,S)
46                   end                   end
# Line 51  Line 59
59
60  end  end
61
(*
* \$Log\$
*)

Legend:
 Removed from v.410 changed lines Added in v.411