module Cliquetree

: sig

Construction of the clique tree of a graph and recognition of chordal graphs.

Based on the article: Chordal graphs and their clique graph by P. Galinier, M. Habib and C. Paul.

Author Matthieu Sozeau

module CliqueTree : functor (G : Sig.G) -> sig

module CliqueV : sig

Original graph vertex

type t

val compare : t -> t -> int

val hash : t -> int

val equal : t -> t -> bool

val label : t -> t

val create : G.V.t -> t

val vertex : t -> G.V.t

end

module CVS : Set.S with type elt = CliqueV.t

Set of original vertices

module CliqueTreeV : sig

Clique tree vertex type

type data = CliqueV.t list * CVS.t

Trace of the algorithm as a list of markers Clique vertices

type label

type t

val compare : t -> t -> int

val hash : t -> int

val equal : t -> t -> bool

val create : data -> label -> t

val label : t -> label

val data : t -> data

end

module CliqueTreeE : sig

type t = int * CVS.t

val compare : t -> t -> int

val default : t

val create : int -> CVS.t -> t

val vertices : t -> CVS.t

Vertices in the clique tree edge (intersection of the two clique extremities).

end

module CliqueTree : Sig.G with type V.t = CliqueTreeV.t and type E.label = CliqueTreeE.t

The clique tree graph type

val mcs_clique : G.t -> G.V.t list * CliqueTree.t * CliqueTree.V.t

mcs_clique g return an perfect elimination order of g (if it is chordal), the clique tree of g and its root.

val is_chordal : G.t -> bool

is_chordal g uses the clique tree construction to test if a graph is chordal or not.

val maxwidth : G.t -> G.t -> CliqueTree.t -> int

maxwidth g tri tree returns the maxwidth characteristic of the triangulation tri of graph g given the clique tree tree of tri.

end