module Kruskal

: sig

Kruskal's minimum-spanning-tree algorithm.

module type G = sig

Minimal graph signature for Kruskal. Sub-signature of Sig.G.

type t

module V : Sig.COMPARABLE

module E : sig

type t

type label

val label : t -> label

val dst : t -> V.t

val src : t -> V.t

end

val fold_vertex : (V.t -> 'a -> 'a) -> t -> 'a -> 'a

val iter_edges_e : (E.t -> unit) -> t -> unit

end

module Make : functor (G : G) -> functor (W : Sig.ORDERED_TYPE with type t = G.E.label) -> sig

Functor providing an implementation of Kruskal's minimum-spanning-tree algorithm. Parameter W ensures that label on edges are comparable.

val spanningtree : G.t -> G.E.t list

end

Generic version where union-find implementation is provided

module type UNIONFIND = sig

Signature of union-find.

type elt

type t

val init : elt list -> t

val find : elt -> t -> elt

val union : elt -> elt -> t -> unit

end

module Generic : functor (G : G) -> functor (W : Sig.ORDERED_TYPE with type t = G.E.label) -> functor (UF : UNIONFIND with type elt = G.V.t) -> sig

Functor providing an implementation of Kruskal's minimum-spanning-tree algorithm using a user-defined union-find algorithm. Parameter W ensures that label on edges are comparable.

val spanningtree : G.t -> G.E.t list

end