module Mcs_m

: sig

Maximal Cardinality Search (MCS-M) algorithm

Based on the article: Maximal Cardinality Search for Computing Minimal Triangulations of Graphs. by A. Berry, Jean R. S. Blair, Pinar Heggernes & Barry W. Peyton.

Author Matthieu Sozeau

Author Pierre-Loic Garoche

module MaximalCardinalitySearch : sig

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

type edgelist = (G.V.t * G.V.t) list

val mcsm : G.t -> (int * G.V.t) list * edgelist

mcsm g returns a tuple (o, e) where o is a perfect elimination order of g' where g' is the triangulation e applied to g.

val triangulate : G.t -> G.t

triangulate g computes a triangulation of g using the MCS-M algorithm

end

module I : functor (Gr : Sig.I) -> sig

type edgelist = (Gr.V.t * Gr.V.t) list

val mcsm : Gr.t -> (int * Gr.V.t) list * edgelist

mcsm g return a tuple (o, e) where o is a perfect elimination order of g' where g' is the triangulation e applied to g.

val triangulate : Gr.t -> unit

triangulate g triangulates g using the MCS-M algorithm

end