sig
module type FLOW =
sig
type t
type label
val max_capacity : Flow.FLOW.label -> Flow.FLOW.t
val min_capacity : Flow.FLOW.label -> Flow.FLOW.t
val flow : Flow.FLOW.label -> Flow.FLOW.t
val add : Flow.FLOW.t -> Flow.FLOW.t -> Flow.FLOW.t
val sub : Flow.FLOW.t -> Flow.FLOW.t -> Flow.FLOW.t
val zero : Flow.FLOW.t
val compare : Flow.FLOW.t -> Flow.FLOW.t -> int
end
module type G_GOLDBERG =
sig
type t
module V : Sig.COMPARABLE
module E :
sig
type t
val compare : t -> t -> int
type vertex = V.t
val src : t -> vertex
val dst : t -> vertex
type label
val create : vertex -> label -> vertex -> t
val label : t -> label
end
val nb_vertex : Flow.G_GOLDBERG.t -> int
val iter_vertex : (V.t -> unit) -> Flow.G_GOLDBERG.t -> unit
val iter_edges_e :
(Flow.G_GOLDBERG.E.t -> unit) -> Flow.G_GOLDBERG.t -> unit
val fold_succ_e :
(Flow.G_GOLDBERG.E.t -> 'a -> 'a) ->
Flow.G_GOLDBERG.t -> V.t -> 'a -> 'a
val fold_pred_e :
(Flow.G_GOLDBERG.E.t -> 'a -> 'a) ->
Flow.G_GOLDBERG.t -> V.t -> 'a -> 'a
end
module Goldberg :
functor (G : G_GOLDBERG) ->
functor
(F : sig
type t
type label = G.E.label
val max_capacity : label -> t
val min_capacity : label -> t
val flow : label -> t
val add : t -> t -> t
val sub : t -> t -> t
val zero : t
val compare : t -> t -> int
end) ->
sig val maxflow : G.t -> G.V.t -> G.V.t -> (G.E.t -> F.t) * F.t end
module type G_FORD_FULKERSON =
sig
type t
module V : Sig.HASHABLE
module E :
sig
type t
type label
val src : Flow.G_FORD_FULKERSON.E.t -> V.t
val dst : Flow.G_FORD_FULKERSON.E.t -> V.t
val label :
Flow.G_FORD_FULKERSON.E.t -> Flow.G_FORD_FULKERSON.E.label
end
val iter_succ_e :
(Flow.G_FORD_FULKERSON.E.t -> unit) ->
Flow.G_FORD_FULKERSON.t -> V.t -> unit
val iter_pred_e :
(Flow.G_FORD_FULKERSON.E.t -> unit) ->
Flow.G_FORD_FULKERSON.t -> V.t -> unit
end
module Ford_Fulkerson :
functor (G : G_FORD_FULKERSON) ->
functor
(F : sig
type t
type label = G.E.label
val max_capacity : label -> t
val min_capacity : label -> t
val flow : label -> t
val add : t -> t -> t
val sub : t -> t -> t
val zero : t
val compare : t -> t -> int
end) ->
sig val maxflow : G.t -> G.V.t -> G.V.t -> (G.E.t -> F.t) * F.t end
end