module Contraction

: sig

Edge contraction for directed, edge-labeled graphs

module type G = sig

Minimal graph signature for edge contraction algorithm

type t

module V : Sig.COMPARABLE

type vertex = V.t

module E : Sig.EDGE with type vertex = vertex

type edge = E.t

val empty : t

val add_edge_e : t -> edge -> t

val fold_edges_e : (edge -> 'a -> 'a) -> t -> 'a -> 'a

val fold_vertex : (vertex -> 'a -> 'a) -> t -> 'a -> 'a

end

module Make : functor (G : G) -> sig

val contract : (G.E.t -> bool) -> G.t -> G.t

contract p g will perform edge contraction on the graph g. The edges for which the property p holds/is true will get contracted: The resulting graph will not have these edges; the start- and end-node of these edges will get united.

end