|
1.1.1
by Sylvain Le Gall
Import upstream version 0.90 |
1 |
(* $Id: md.mli,v 1.2 2004/06/28 13:48:25 signoles Exp $ *)
|
2 |
||
3 |
(** Minimum Degree algorithm
|
|
4 |
|
|
5 |
Based on the article:
|
|
6 |
The Minimum Degree Heuristic and the Minimal Triangulation Process
|
|
7 |
by A. Berry, Pinar Heggernes & Geneviève Simonet.
|
|
8 |
|
|
9 |
@author Matthieu Sozeau
|
|
10 |
@author Pierre-Loic Garoche *)
|
|
11 |
||
12 |
module P(G : Sig.P) : sig |
|
13 |
||
14 |
type edgeset = (G.V.t * G.V.t) list |
|
15 |
||
16 |
val md : G.t -> G.t * edgeset * G.V.t list |
|
17 |
(** [md g] return a tuple [(g', e, o)] where [g'] is
|
|
18 |
a triangulated graph, [e] is the triangulation of [g] and
|
|
19 |
[o] is a perfect elimination order of [g'] *)
|
|
20 |
||
21 |
val triangulate : G.t -> G.t |
|
22 |
(** [triangulate g] return the graph [g'] produced by applying
|
|
23 |
miminum degree to [g]. *)
|
|
24 |
||
25 |
end
|
|
26 |
||
27 |
module I(G : Sig.I) : sig |
|
28 |
||
29 |
type edgeset = (G.V.t * G.V.t) list |
|
30 |
||
31 |
val md : G.t -> G.t * edgeset * G.V.t list |
|
32 |
(** [md g] return a tuple [(g', e, o)] where [g'] is
|
|
33 |
a triangulated graph, [e] is the triangulation of [g] and
|
|
34 |
[o] is a perfect elimination order of [g'] *)
|
|
35 |
||
36 |
val triangulate : G.t -> G.t |
|
37 |
(** [triangulate g] return the graph [g'] produced by applying
|
|
38 |
miminum degree to [g]. *)
|
|
39 |
||
40 |
end
|