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-topsort.sml
ViewVC logotype

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 651 - (view) (download)

1 : monnier 411 (*
2 :     * This module computes a topological sort of a graph
3 :     *
4 :     * -- Allen
5 :     *)
6 :    
7 : monnier 245 structure GraphTopsort : GRAPH_TOPOLOGICAL_SORT =
8 :     struct
9 :    
10 :     structure G = Graph
11 :    
12 :     (*
13 :     * Topological sort
14 :     *)
15 :     fun topsort (G.GRAPH G) roots =
16 : monnier 411 let val visited = Word8Array.array(#capacity G (),0w0)
17 : monnier 245 val succ = #succ G
18 :     fun dfs (n, list) =
19 : monnier 411 if Word8Array.sub(visited,n) <> 0w0 then list
20 :     else (Word8Array.update(visited,n,0w1); dfs'(n,succ n,list))
21 : monnier 245 and dfs'(x,[],list) = x::list
22 :     | dfs'(x,n::ns,list) = dfs'(x,ns,dfs(n,list))
23 :     and dfs''([], list) = list
24 :     | dfs''(n::ns, list) = dfs''(ns,dfs(n,list))
25 :     in
26 :     dfs''(roots,[])
27 :     end
28 :    
29 :     end
30 :    

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