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 1260 - (download) (annotate)
Mon Jul 15 17:27:34 2002 UTC (18 years, 6 months ago) by george
File size: 911 byte(s)
bug fix from Allen
 * This module implements Kruskal's algorithm for minimal cost
 * spanning tree.
 * -- Allen

structure Kruskal : MIN_COST_SPANNING_TREE =
   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.== P (i,j) then 
                   (P.union' P (i,j); make_tree(M-1,add_edge(e,u)))
       make_tree(#order G' (),u)
   end handle Q.EmptyPriorityQueue => raise Unconnected

ViewVC Help
Powered by ViewVC 1.0.0