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/trunk/src/MLRISC/graphs/graph-topsort.sml
 [smlnj] / sml / trunk / src / MLRISC / graphs / graph-topsort.sml

Diff of /sml/trunk/src/MLRISC/graphs/graph-topsort.sml

revision 245, Sat Apr 17 18:47:12 1999 UTC revision 411, Fri Sep 3 00:25:03 1999 UTC
# Line 1  Line 1
1    (*
2     * This module computes a topological sort of a graph
3     *
4     * -- Allen
5     *)
6
7  structure GraphTopsort : GRAPH_TOPOLOGICAL_SORT =  structure GraphTopsort : GRAPH_TOPOLOGICAL_SORT =
8  struct  struct
9
# Line 7  Line 13
13      * Topological sort      * Topological sort
14      *)      *)
15     fun topsort (G.GRAPH G) roots =     fun topsort (G.GRAPH G) roots =
16     let val visited = BitSet.create (#capacity G ())     let val visited = Word8Array.array(#capacity G (),0w0)
17         val succ    = #succ G         val succ    = #succ G
18         fun dfs (n, list) =         fun dfs (n, list) =
19            if BitSet.markAndTest(visited,n) then list            if Word8Array.sub(visited,n) <> 0w0 then list
20            else dfs'(n,succ n,list)            else (Word8Array.update(visited,n,0w1); dfs'(n,succ n,list))
21         and dfs'(x,[],list)    = x::list         and dfs'(x,[],list)    = x::list
22           | dfs'(x,n::ns,list) = dfs'(x,ns,dfs(n,list))           | dfs'(x,n::ns,list) = dfs'(x,ns,dfs(n,list))
23         and dfs''([], list)    = list         and dfs''([], list)    = list
# Line 22  Line 28
28
29  end  end
30
(*
* \$Log\$
*)

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

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