module Minsep

: sig

Minimal separators of a graph

Based on the article: Generating all the minimal separators of a graph. by A. Berry, J.-P. Bordat and O.Cogis http://www.isima.fr/berry/generating.html

A set S of vertices is a minimal separator if it exists 2 distinct connected components C and D in G \ S such that each vertex of S has a successor in C and D.

module type G = sig

Minimal signature for computing the minimal separators

type t

module V : Sig.COMPARABLE

val succ : t -> V.t -> V.t list

val iter_succ : (V.t -> unit) -> t -> V.t -> unit

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

val iter_vertex : (V.t -> unit) -> t -> unit

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

end

module type MINSEP = sig

module G : G

Implementation of a graph

module Vertex_Set : Set.S with type elt = G.V.t

Implementation of a set of vertex

module VSetset : Set.S with type elt = Vertex_Set.t

Implementation of a set of Vertex_Set

val allminsep : G.t -> Vertex_Set.t list

allminsep g computes the list of all minimal separators of g.

val list_of_allminsep : G.t -> G.V.t list list

Less efficient that allminsep

val set_of_allminsep : G.t -> VSetset.t

Less efficient that allminsep

end

module P : functor (G : sig

include G

val remove_vertex : t -> V.t -> t

end

) -> MINSEP with module G = G

Implementation for a persistent graph

module I : functor (G : sig

include G

module Mark : Sig.MARK with type graph = t and type vertex = V.t

end

) -> MINSEP with module G = G

Implementation for an imperative graph. Less efficient that the implementation for a persistent graph

end