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

SCM Repository

[smlnj] View of /sml/trunk/src/MLRISC/graphs/graph-topsort.sml
ViewVC logotype

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 246 - (download) (annotate)
Sat Apr 17 18:47:12 1999 UTC (20 years, 6 months ago) by monnier
File size: 596 byte(s)
This commit was generated by cvs2svn to compensate for changes in r245,
which included commits to RCS files with non-trunk default branches.
structure GraphTopsort : GRAPH_TOPOLOGICAL_SORT = 
struct

   structure G = Graph

   (*
    * Topological sort
    *)
   fun topsort (G.GRAPH G) roots = 
   let val visited = BitSet.create (#capacity G ())
       val succ    = #succ G
       fun dfs (n, list) =
          if BitSet.markAndTest(visited,n) then list
          else dfs'(n,succ n,list)
       and dfs'(x,[],list)    = x::list
         | dfs'(x,n::ns,list) = dfs'(x,ns,dfs(n,list))
       and dfs''([], list)    = list
         | dfs''(n::ns, list) = dfs''(ns,dfs(n,list))
   in
       dfs''(roots,[])
   end

end

(* 
 * $Log$
 *)

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