/usr/lib/ocaml/ocamlgraph/cliquetree.mli is in libocamlgraph-ocaml-dev 1.8.6-1build5.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 | (**************************************************************************)
(* *)
(* Ocamlgraph: a generic graph library for OCaml *)
(* Copyright (C) 2004-2010 *)
(* Sylvain Conchon, Jean-Christophe Filliatre and Julien Signoles *)
(* *)
(* This software is free software; you can redistribute it and/or *)
(* modify it under the terms of the GNU Library General Public *)
(* License version 2.1, with the special exception on linking *)
(* described in file LICENSE. *)
(* *)
(* This software is distributed in the hope that it will be useful, *)
(* but WITHOUT ANY WARRANTY; without even the implied warranty of *)
(* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. *)
(* *)
(**************************************************************************)
(** 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(G : Sig.G) : sig
(** Original graph vertex *)
module CliqueV :
sig
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
(** Set of original vertices *)
module CVS : Set.S with type elt = CliqueV.t
(** Clique tree vertex type *)
module CliqueTreeV : sig
(** Trace of the algorithm as a list of markers Clique vertices *)
type data = CliqueV.t list * CVS.t
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
(** Vertices in the clique tree edge
(intersection of the two clique extremities). *)
val vertices : t -> CVS.t
end
(** The clique tree graph type *)
module CliqueTree : Sig.G with type V.t = CliqueTreeV.t
and type E.label = CliqueTreeE.t
(** [mcs_clique g] return an perfect elimination order of [g]
(if it is chordal), the clique tree of [g] and its root. *)
val mcs_clique : G.t -> G.V.t list * CliqueTree.t * CliqueTree.V.t
(** [is_chordal g] uses the clique tree construction to test if a graph is
chordal or not. *)
val is_chordal : G.t -> bool
(** [maxwidth g tri tree] returns the maxwidth characteristic of the
triangulation [tri] of graph [g] given the clique tree [tree] of [tri]. *)
val maxwidth : G.t -> G.t -> CliqueTree.t -> int
end
|