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
ViewVC logotype

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

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

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

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