(*
 * prim.sml - Prim's minimum spanning tree algorithm
 *  Ronald Garcia
 *  $Id: prim.sml,v 1.3 2003/08/08 22:15:34 garcia Exp $
 *)

use "dijkstra.sml";


use "concepts.sml";
use "graph.sml";
use "property_map.sml";
use "color_map.sml";

signature PrimPSig =
sig
 structure VertexListGraph : VertexListGraphSig
 structure IncidenceGraph : IncidenceGraphSig
 structure PredecessorMap : ReadWritePropertyMapSig
 structure DistanceMap : ReadWritePropertyMapSig
 structure WeightMap : ReadablePropertyMapSig
 structure VertexIndexMap : ReadablePropertyMapSig where type value_t = int
 structure Compare : StrictWeakOrderingSig

 sharing VertexListGraph = IncidenceGraph
 sharing type IncidenceGraph.edge_t = WeightMap.key_t
 sharing type WeightMap.value_t =
              Compare.arg_t =
              DistanceMap.value_t

 sharing type VertexListGraph.vertex_t =
              PredecessorMap.key_t =
              PredecessorMap.value_t =
              DistanceMap.key_t =
              VertexIndexMap.key_t
end

functor MakePrim (Params : PrimPSig) :
sig
    structure VLGraphT : VertexListGraphSig
    structure VIMapT : ReadablePropertyMapSig where type value_t = int
    structure PMapT : ReadWritePropertyMapSig
    structure DMapT : ReadWritePropertyMapSig
    structure WMapT : ReadablePropertyMapSig
    structure CmpT : StrictWeakOrderingSig

    val prim_minimum_spanning_tree :
        VLGraphT.graph_t -> VLGraphT.vertex_t -> PMapT.data_t ->
        DMapT.data_t -> WMapT.data_t -> VIMapT.data_t ->
        CmpT.data_t -> DMapT.value_t -> DMapT.value_t -> unit

end
=
struct
    structure VLGraphT = Params.VertexListGraph
    structure IGraphT = Params.IncidenceGraph
    structure PMapT = Params.PredecessorMap
    structure DMapT = Params.DistanceMap
    structure WMapT = Params.WeightMap
    structure VIMapT = Params.VertexIndexMap
    structure CmpT = Params.Compare

    structure ProjectSnd =
    struct
      type data_t = unit
      type result_t = DMapT.value_t
      type first_t = result_t
      type second_t = WMapT.value_t

      fun create () = ()
      fun go () first second = second
    end

    structure DSP = 
    MakeDijkstra(struct 
                    structure VertexListGraph = VLGraphT
                    structure IncidenceGraph = IGraphT
                    structure PredecessorMap = PMapT
                    structure DistanceMap = DMapT
                    structure WeightMap = WMapT
                    structure VertexIndexMap = VIMapT
                    structure Compare = CmpT
                    structure Combine = ProjectSnd
                    end);


    fun prim_minimum_spanning_tree
    graph vertex pmap dmap wmap imap cmp inf zero =
        DSP.dijkstra_shortest_paths
            graph vertex pmap dmap wmap imap cmp (ProjectSnd.create())
            inf zero
end