grew_graph.mli 9.46 KB
Newer Older
bguillaum's avatar
bguillaum committed
1 2 3
(**********************************************************************************)
(*    Libcaml-grew - a Graph Rewriting library dedicated to NLP applications      *)
(*                                                                                *)
Bruno Guillaume's avatar
Bruno Guillaume committed
4
(*    Copyright 2011-2018 Inria, Université de Lorraine                           *)
bguillaum's avatar
bguillaum committed
5
(*                                                                                *)
Bruno Guillaume's avatar
Bruno Guillaume committed
6
(*    Webpage: http://grew.fr                                                     *)
bguillaum's avatar
bguillaum committed
7 8 9 10
(*    License: CeCILL (see LICENSE folder or "http://www.cecill.info")            *)
(*    Authors: see AUTHORS file                                                   *)
(**********************************************************************************)

11 12
open Conll

13 14
open Grew_base
open Grew_types
bguillaum's avatar
bguillaum committed
15
open Grew_ast
16
open Grew_domain
17
open Grew_fs
pj2m's avatar
pj2m committed
18 19
open Grew_edge
open Grew_node
bguillaum's avatar
bguillaum committed
20
open Grew_command
pj2m's avatar
pj2m committed
21

bguillaum's avatar
bguillaum committed
22
(* ================================================================================ *)
23 24 25
module P_deco: sig
  type t =
      { nodes: Pid.t list;
26
        edges: (Pid.t * P_edge.t * Pid.t) list;
pj2m's avatar
pj2m committed
27
      }
28 29

  val empty:t
bguillaum's avatar
bguillaum committed
30
end (* module P_deco *)
31

bguillaum's avatar
bguillaum committed
32
(* ================================================================================ *)
33
module G_deco: sig
34 35 36 37
  (* value is (f, Some g) for combined request "f=v/g=u" and (j, None) else *)
  type highlighted_feat = string * string option

  type t = {
38 39 40 41 42
    (* a list of (node, (pattern_id, features of nodes implied in the step)) *)
    nodes: (Gid.t * (string * highlighted_feat list)) list;
    (* an edge list *)
    edges: (Gid.t * G_edge.t * Gid.t) list;
    pivot: Gid.t option;
43
  }
44

pj2m's avatar
pj2m committed
45
  val empty:t
bguillaum's avatar
bguillaum committed
46
end (* module G_deco *)
pj2m's avatar
pj2m committed
47

bguillaum's avatar
bguillaum committed
48
(* ================================================================================ *)
49
module P_graph: sig
50 51 52 53 54 55
  type map = P_node.t Pid_map.t

  type t = {
    map: map;
    pivot: Pid.t option;
  }
56

pj2m's avatar
pj2m committed
57
  val empty: t
bguillaum's avatar
bguillaum committed
58

Bruno Guillaume's avatar
Bruno Guillaume committed
59
  val to_json: ?domain:Domain.t -> t -> Yojson.Basic.t
60

61 62
  val find: Pid.t -> t -> P_node.t

bguillaum's avatar
bguillaum committed
63 64
  val roots: t -> Pid.t list

65
  val pid_name_list: t -> Id.name list
66

67 68
  type extension = {
      ext_map: P_node.t Pid_map.t; (* node description for new nodes and for edge "Old -> New"  *)
bguillaum's avatar
bguillaum committed
69
      old_map: P_node.t Pid_map.t; (* a partial map for new constraints on old nodes "Old [...]" *)
70
    }
pj2m's avatar
pj2m committed
71

72
  (** It raises [P_fs.Fail_unif] exception in case of inconsistent feature structures. *)
pj2m's avatar
pj2m committed
73
  val build:
bguillaum's avatar
bguillaum committed
74
      ?domain:Domain.t ->
Bruno Guillaume's avatar
Bruno Guillaume committed
75
      Lexicons.t ->
76 77
      Id.name option ->
      Ast.basic ->
78
      (t * Id.table)
pj2m's avatar
pj2m committed
79

80
  (** It raises [P_fs.Fail_unif] exception in case of inconsistent feature structures. *)
81
  val build_extension:
bguillaum's avatar
bguillaum committed
82
      ?domain:Domain.t ->
Bruno Guillaume's avatar
Bruno Guillaume committed
83
      Lexicons.t ->
pj2m's avatar
pj2m committed
84
      Id.table ->
bguillaum's avatar
bguillaum committed
85 86
      Ast.node list ->
      Ast.edge list ->
87
      (extension * Id.table)
bguillaum's avatar
bguillaum committed
88
end (* module P_graph *)
89

bguillaum's avatar
bguillaum committed
90
(* ================================================================================ *)
91
module G_graph: sig
92
  type t
93 94

  val empty: t
pj2m's avatar
pj2m committed
95

96 97
  (** [find gid graph] return the g_node associated with [gid] in [graph].
      [Not_found] is raised if [gid] is not defined in [graph]. *)
98 99
  val find: Gid.t -> t -> G_node.t

bguillaum's avatar
bguillaum committed
100 101
  val equals: t -> t -> bool

102 103 104 105
  val node_exists: (G_node.t -> bool) -> t -> bool

  val fold_gid: (Gid.t -> 'a -> 'a) -> t -> 'a -> 'a

bguillaum's avatar
bguillaum committed
106 107
  val get_highest: t -> int

108 109
  val push_rule: string -> t -> t

110 111
  (** [edge_out t id label_cst] returns true iff there is an out-edge from the node [id] with a label compatible with [label_cst] *)
  val edge_out: t -> Gid.t -> Label_cst.t -> bool
bguillaum's avatar
bguillaum committed
112 113 114 115 116

  (* ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ *)
  (* Build functions *)
  (* ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ *)

Bruno Guillaume's avatar
Bruno Guillaume committed
117
  val build: ?domain:Domain.t -> ?grewpy: bool -> Ast.gr -> t
bguillaum's avatar
bguillaum committed
118

bguillaum's avatar
bguillaum committed
119
  val of_conll: ?domain:Domain.t -> Conll.t -> t
Bruno Guillaume's avatar
Bruno Guillaume committed
120
  val of_json: Yojson.Basic.t -> t
bguillaum's avatar
bguillaum committed
121

122
  (** input : "Le/DET/le petit/ADJ/petit chat/NC/chat dort/V/dormir ./PONCT/."
123
      It supposes that "SUC" is defined in current relations *)
bguillaum's avatar
bguillaum committed
124
  val of_brown: ?domain:Domain.t -> ?sentid: string -> string -> t
125

126
  val of_pst: ?domain:Domain.t -> Ast.pst -> t
127

bguillaum's avatar
bguillaum committed
128 129 130 131 132 133 134 135 136
  (* ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ *)
  (* Update functions *)
  (* ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ *)

  (** [add_edge graph id_src label id_tar] tries to add an edge grom [id_src] to [id_tar] with [label] to [graph].
      if it succeeds, [Some new_graph] is returned
      if it fails (the edge already exists), [None] is returned
  *)
  val add_edge: t -> Gid.t -> G_edge.t -> Gid.t -> t option
pj2m's avatar
pj2m committed
137

bguillaum's avatar
bguillaum committed
138 139
  (** [del_edge ?edge_ident loc graph id_src label id_tar] removes the edge (id_src -[label]-> id_tar) from graph.
     Log.critical if the edge is not in graph *)
140
  val del_edge: ?edge_ident: string -> Loc.t -> t -> Gid.t -> G_edge.t -> Gid.t -> t option
141

bguillaum's avatar
bguillaum committed
142
  (** [del_node graph id] remove node [id] from [graph], with all its incoming and outcoming edges.
Bruno Guillaume's avatar
Bruno Guillaume committed
143 144
      None is returned if [id] not defined in [graph]*)
  val del_node: t -> Gid.t -> t option
145

146 147 148
  val add_before: Gid.t -> t -> (Gid.t * t)
  val add_after: Gid.t -> t -> (Gid.t * t)
  val add_unordered: t -> (Gid.t * t)
bguillaum's avatar
bguillaum committed
149

150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187
  (** shift all crown-edges ending in [src_gid] to edges ending in [tar_gid] *)
  val shift_in:
    Loc.t ->            (* localization of the command *)
    Gid.t ->            (* [src_gid] the source gid of the "shift_in" *)
    Gid.t ->            (* [tar_gid] the target gid of the "shift_in" *)
    (Gid.t -> bool) ->  (* a locality test: true iff the node is a pattern node *)
    Label_cst.t ->      (* what are the constraint on edge label *)
    t ->                (* input graph *)
      ( t *                                (* output graph *)
        (Gid.t * G_edge.t * Gid.t) list *  (* list of really deleted edges *)
        (Gid.t * G_edge.t * Gid.t) list    (* list of really added edges *)
      )

  (** shift all crown-edges starting from [src_gid] to edges starting from [tar_gid] *)
  val shift_out:
    Loc.t ->            (* localization of the command *)
    Gid.t ->            (* [src_gid] the source gid of the "shift_out" *)
    Gid.t ->            (* [tar_gid] the target gid of the "shift_out" *)
    (Gid.t -> bool) ->  (* a locality test: true iff the node is a pattern node *)
    Label_cst.t ->      (* what are the constraint on edge label *)
    t ->                (* input graph *)
      ( t *                                (* output graph *)
        (Gid.t * G_edge.t * Gid.t) list *  (* list of really deleted edges *)
        (Gid.t * G_edge.t * Gid.t) list    (* list of really added edges *)
      )

  (** move all incident crown-edges from/to [src_gid] are moved to incident edges on node [tar_gid] from graph *)
  val shift_edges:
    Loc.t ->            (* localization of the command *)
    Gid.t ->            (* [src_gid] the source gid of the "shift_edges" *)
    Gid.t ->            (* [tar_gid] the target gid of the "shift_edges" *)
    (Gid.t -> bool) ->  (* a locality test: true iff the node is a pattern node *)
    Label_cst.t ->      (* what are the constraint on edge label *)
    t ->                (* input graph *)
      ( t *                                (* output graph *)
        (Gid.t * G_edge.t * Gid.t) list *  (* list of really deleted edges *)
        (Gid.t * G_edge.t * Gid.t) list    (* list of really added edges *)
      )
pj2m's avatar
pj2m committed
188

189
  (** [update_feat domain tar_id tar_feat_name concat_items] sets the feature of the node [tar_id]
190 191
      with feature name [tar_feat_name] to be the contatenation of values described by the [concat_items].
      It returns both the new graph and the new feature value produced as the second element *)
192
  val update_feat: ?loc:Loc.t -> t -> Gid.t -> string -> Concat_item.t list -> (t * string)
pj2m's avatar
pj2m committed
193

194
  val set_feat: ?loc:Loc.t -> t -> Gid.t -> string -> string -> t
bguillaum's avatar
bguillaum committed
195

bguillaum's avatar
bguillaum committed
196
  (** [del_feat graph node_id feat_name] returns [graph] where the feat [feat_name] of [node_id] is deleted
197 198
      If the feature is not present, None is returned. *)
  val del_feat: t -> Gid.t -> string -> t option
pj2m's avatar
pj2m committed
199

bguillaum's avatar
bguillaum committed
200 201 202
  (* ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ *)
  (* Output functions *)
  (* ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ *)
203
  val to_gr: t -> string
204
  val to_dot: ?main_feat:string -> ?get_url:(string -> string option) -> ?deco:G_deco.t -> t -> string
205
  val to_sentence: ?only_pivot: bool -> ?main_feat:string -> ?deco:G_deco.t -> t -> string
206 207
  val to_dep: ?filter: (string -> bool) -> ?main_feat:string -> ?deco:G_deco.t -> t -> string
  val to_conll: t -> Conll.t
208
  val to_conll_string: ?cupt:bool -> t -> string
Bruno Guillaume's avatar
Bruno Guillaume committed
209
  val to_json: t -> Yojson.Basic.t
Bruno Guillaume's avatar
Bruno Guillaume committed
210

Bruno Guillaume's avatar
Bruno Guillaume committed
211
  val cast: ?domain:Domain.t -> t -> t
212 213

  val is_projective: t -> (Gid.t * Gid.t) option
214 215

  val depth_first_search: t -> unit
216
end (* module G_graph *)
217

Bruno Guillaume's avatar
Bruno Guillaume committed
218
(* ================================================================================ *)
219 220 221 222 223 224
module Delta : sig
  type t

  val empty: t

  val del_node: Gid.t -> t -> t
225 226
  val add_edge: Gid.t -> G_edge.t -> Gid.t -> t -> t
  val del_edge: Gid.t -> G_edge.t -> Gid.t -> t -> t
227
  val set_feat: G_graph.t -> Gid.t -> feature_name -> value option -> t -> t
Bruno Guillaume's avatar
Bruno Guillaume committed
228
end (* module Delta *)
229

Bruno Guillaume's avatar
Bruno Guillaume committed
230
(* ================================================================================ *)
231 232 233 234 235
module Graph_with_history : sig
  type t = {
    seed: G_graph.t;
    delta: Delta.t;
    graph: G_graph.t;
236
    added_gids: (string * Gid.t) list;
237 238
  }

Bruno Guillaume's avatar
Bruno Guillaume committed
239 240
  val from_graph: G_graph.t -> t

241
  val compare: t -> t -> int
Bruno Guillaume's avatar
Bruno Guillaume committed
242
end (* module Graph_with_history *)
243

Bruno Guillaume's avatar
Bruno Guillaume committed
244
(* ================================================================================ *)
245
module Graph_with_history_set : Set.S with type elt = Graph_with_history.t