(*
 * relax.sml - An algorithm for relaxing edges
 *   Ronald Garcia
 *   $Id: relax.sml,v 1.2 2003/05/02 20:03:41 jewillco Exp $
 *)

(* Copyright 2003, Trustees of Indiana University
 * Please see the license in the file ../LICENSE
 *)

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

(* 
Dijkstra is implemented in terms of BFS.  A special BFSVisitor is built 
to handle the necessary calls for Dijkstra.  A priority_queue that uses a
property map for its priorities is passed to BFS as its Buffer. *)


(* Relax - An algorithm used to implement Dijkstra *)
signature RelaxPSig =
sig
    structure Graph : EdgeGraphSig
    structure WMap : ReadablePropertyMapSig
    structure DMap : ReadWritePropertyMapSig
    structure PMap : ReadWritePropertyMapSig
    structure Cmp : StrictWeakOrderingSig
    structure Cmb : BinaryFunctionSig

    sharing type DMap.key_t =
                 PMap.key_t =
                 PMap.value_t =
                 Graph.vertex_t

    sharing type WMap.key_t = Graph.edge_t

    sharing type Cmp.arg_t =
                 Cmb.first_t =
                 Cmb.result_t =
                 DMap.value_t

    sharing type WMap.value_t = Cmb.second_t

end

functor MakeRelax(Params : RelaxPSig):
sig
    type edge_t
    val go : Params.DMap.data_t -> Params.WMap.data_t -> Params.PMap.data_t ->
             Params.Cmp.data_t -> Params.Cmb.data_t -> Params.Graph.graph_t ->
             edge_t -> bool
end
 =
struct
  structure DMap = Params.DMap
  structure Cmp = Params.Cmp
  structure Cmb = Params.Cmb
  structure Graph = Params.Graph
  structure WMap = Params.WMap
  structure PMap = Params.PMap

  type edge_t = Params.Graph.edge_t

  fun go dmap wmap pmap cmp cmb g e =
      let
          val u = Graph.source g e 
          val v = Graph.target g e 
      in
          let
              val du = DMap.get dmap u
              val dv = DMap.get dmap v
              val wuv = WMap.get wmap e
          in
              if Cmp.go cmp (Cmb.go cmb du wuv) dv then
                  (DMap.put dmap v (Cmb.go cmb du wuv);
                   PMap.put pmap v u; true)
              else
                  false
          end
      end
end