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

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

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

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