Module Graph.Flow

Algorithms on flows

The following flow algorithms only apply to networks, that are directed graphs together with a source (a 0 in-degree vertex) and a terminal (a 0 out-degree vertex).

Maximum flow algorithms

module type FLOW = sig ... end

Signature for edges' flow.

Goldberg-Tarjan maximal flow algorithm

module type G_GOLDBERG_TARJAN = sig ... end

Minimal graph signature for Goldberg-Tarjan. Sub-signature of Sig.G.

module Goldberg_Tarjan (G : G_GOLDBERG_TARJAN) (F : FLOW with type label = G.E.label) : sig ... end

Ford-Fulkerson maximal flow algorithm

module type G_FORD_FULKERSON = sig ... end

Minimal digraph signature for Ford-Fulkerson. Sub-signature of Sig.G.

module type FLOWMIN = sig ... end
module Ford_Fulkerson (G : G_FORD_FULKERSON) (F : FLOWMIN with type label = G.E.label) : sig ... end