Up

moduleCliquetree

: 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.

#
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
end