/usr/lib/ocaml/ocamlgraph/imperative.mli is in libocamlgraph-ocaml-dev 1.8.6-1+b2.
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 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 | (**************************************************************************)
(* *)
(* 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. *)
(* *)
(**************************************************************************)
(** Imperative Graph Implementations. *)
open Sig
(** Signature of imperative graphs. *)
module type S = sig
(** <b>Edges may be labeled or not</b>:
- Unlabeled: there is no label on edges
- Labeled: you have to provide a label implementation as a functor
parameter.
<b>Vertices may be concrete or abstract</b>:
- Concrete: type of vertex labels and type of vertices are identified.
- Abstract: type of vertices is abstract (in particular it is not equal
to type of vertex labels
<b>How to choose between concrete and abstract vertices for my graph
implementation</b>?
Usually, if you fall into one of the following cases, use abstract
vertices:
- you cannot provide efficient comparison/hash functions for vertices; or
- you wish to get two different vertices with the same label.
In other cases, it is certainly easier to use concrete vertices. *)
(** Imperative Unlabeled Graphs. *)
module Concrete (V: COMPARABLE) :
Sig.I with type V.t = V.t and type V.label = V.t and type E.t = V.t * V.t
and type E.label = unit
(** Abstract Imperative Unlabeled Graphs. *)
module Abstract(V: ANY_TYPE) :
Sig.IM with type V.label = V.t and type E.label = unit
(** Imperative Labeled Graphs. *)
module ConcreteLabeled (V: COMPARABLE)(E: ORDERED_TYPE_DFT) :
Sig.I with type V.t = V.t and type V.label = V.t
and type E.t = V.t * E.t * V.t and type E.label = E.t
(** Abstract Imperative Labeled Graphs. *)
module AbstractLabeled (V: ANY_TYPE)(E: ORDERED_TYPE_DFT) :
Sig.IM with type V.label = V.t and type E.label = E.t
end
(** Imperative Directed Graphs. *)
module Digraph : sig
include S
(** {2 Bidirectional graphs}
Bidirectional graphs use more memory space (at worse the double) that
standard concrete directional graphs. But accessing predecessors is in
O(1) amortized instead of O(max(|V|,|E|)) and removing a vertex is in
O(D*ln(D)) instead of O(|V|*ln(D)). D is the maximal degree of the
graph. *)
(** Imperative Unlabeled, bidirectional graph. *)
module ConcreteBidirectional (V: COMPARABLE) :
Sig.I with type V.t = V.t and type V.label = V.t and type E.t = V.t * V.t
and type E.label = unit
(** Imperative Labeled and bidirectional graph. *)
module ConcreteBidirectionalLabeled(V:COMPARABLE)(E:ORDERED_TYPE_DFT) :
Sig.I with type V.t = V.t and type V.label = V.t
and type E.t = V.t * E.t * V.t and type E.label = E.t
end
(** Imperative Undirected Graphs. *)
module Graph : S
(** Imperative graphs implemented as adjacency matrices. *)
module Matrix : sig
module type S = sig
(** Vertices are integers in [0..n-1].
A vertex label is the vertex itself.
Edges are unlabeled. *)
include Sig.I with type V.t = int and type V.label = int
and type E.t = int * int
(** Creation. graphs are not resizeable: size is given at creation time.
Thus [make] must be used instead of [create]. *)
val make : int -> t
(** Note: [add_vertex] and [remove_vertex] have no effect.
[clear] only removes edges, not vertices. *)
end
module Digraph : S
(** Imperative Directed Graphs implemented with adjacency matrices. *)
module Graph : S
(** Imperative Undirected Graphs implemented with adjacency matrices. *)
end
(****
(** Faster implementations for abstract (un)labeled (di)graphs
when vertices are _not shared_ between different graphs.
This means that, when using the following implementations, two different
graphs (created with two calls to [create]) must have disjoint sets of
vertices. *)
module UV : sig
(** directed graphs *)
module Digraph : sig
module Abstract(V: ANY_TYPE) :
Sig.IM with type V.label = V.t and type E.label = unit
module AbstractLabeled (V: ANY_TYPE)(E: ORDERED_TYPE_DFT) :
Sig.IM with type V.label = V.t and type E.label = E.t
end
(** undirected graphs *)
module Graph : sig
module Abstract(V: ANY_TYPE) :
Sig.IM with type V.label = V.t and type E.label = unit
module AbstractLabeled (V: ANY_TYPE)(E: ORDERED_TYPE_DFT) :
Sig.IM with type V.label = V.t and type E.label = E.t
end
end
****)
(*
Local Variables:
compile-command: "make -C .."
End:
*)
|