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.
Original graph vertex
Set of original vertices
Clique tree vertex type
Trace of the algorithm as a list of markers Clique vertices
Vertices in the clique tree edge
(intersection of the two clique extremities).
The clique tree graph type
mcs_clique g return an perfect elimination order of g
(if it is chordal), the clique tree of g and its root.
is_chordal g uses the clique tree construction to test if a graph is
chordal or not.
maxwidth g tri tree returns the maxwidth characteristic of the
triangulation tri of graph g given the clique tree tree of tri.
maxwidth g tri tree