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

View of /sml/trunk/src/MLRISC/graphs/kruskal.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: 768 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 Kruskal : MIN_COST_SPANNING_TREE =
struct
   structure P = NodePartition
   structure Q = PriorityQueue
   structure G = Graph

   exception Unconnected

   fun spanning_tree { weight, < } (G as G.GRAPH G') add_edge u =
   let fun less (e1,e2) = weight e1 < weight e2
       val Q            = Q.create less 
       val _            = #forall_edges G' (Q.insert Q) 
       val P            = P.node_partition G
       fun make_tree(1,u) = u
         | make_tree(M,u) =
            let val e as (i,j,_) = Q.deleteMin Q
            in  if P.union' P (i,j) then make_tree(M-1,add_edge(e,u))
                else make_tree(M,u)
            end
   in  
       make_tree(#order G' (),u)
   end handle Q.EmptyPriorityQueue => raise Unconnected
end

(*
 * $Log$
 *)

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