grew_graph.mli 9.36 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
open Conll
12
open Yojson.Basic
13

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

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

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

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

  type t = {
    nodes: (Gid.t * (string * highlighted_feat list)) list;  (* a list of (node, (pattern_id, features of nodes implied in the step)) *)
    edges: (Gid.t * G_edge.t * Gid.t) list;        (* an edge list *)
  }
42

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

bguillaum's avatar
bguillaum committed
46
(* ================================================================================ *)
47 48
module P_graph: sig
  type t = P_node.t Pid_map.t
49

pj2m's avatar
pj2m committed
50
  val empty: t
bguillaum's avatar
bguillaum committed
51

52 53
  val to_json: ?domain:Domain.t -> t -> Yojson.Basic.json

54 55
  val find: Pid.t -> t -> P_node.t

bguillaum's avatar
bguillaum committed
56 57
  val roots: t -> Pid.t list

58
  val pid_name_list: t -> Id.name list
59

60 61
  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
62
      old_map: P_node.t Pid_map.t; (* a partial map for new constraints on old nodes "Old [...]" *)
63
    }
pj2m's avatar
pj2m committed
64

65
  (** It raises [P_fs.Fail_unif] exception in case of inconsistent feature structures. *)
pj2m's avatar
pj2m committed
66
  val build:
bguillaum's avatar
bguillaum committed
67
      ?domain:Domain.t ->
Bruno Guillaume's avatar
Bruno Guillaume committed
68
      Lexicons.t ->
bguillaum's avatar
bguillaum committed
69 70
      Ast.node list ->
      Ast.edge list ->
71
      (t * Id.table)
pj2m's avatar
pj2m committed
72

73
  (** It raises [P_fs.Fail_unif] exception in case of inconsistent feature structures. *)
74
  val build_extension:
bguillaum's avatar
bguillaum committed
75
      ?domain:Domain.t ->
Bruno Guillaume's avatar
Bruno Guillaume committed
76
      Lexicons.t ->
pj2m's avatar
pj2m committed
77
      Id.table ->
bguillaum's avatar
bguillaum committed
78 79
      Ast.node list ->
      Ast.edge list ->
80
      (extension * Id.table)
bguillaum's avatar
bguillaum committed
81
end (* module P_graph *)
82

bguillaum's avatar
bguillaum committed
83
(* ================================================================================ *)
84
module G_graph: sig
85
  type t
86 87

  val empty: t
pj2m's avatar
pj2m committed
88

89 90
  (** [find gid graph] return the g_node associated with [gid] in [graph].
      [Not_found] is raised if [gid] is not defined in [graph]. *)
91 92
  val find: Gid.t -> t -> G_node.t

bguillaum's avatar
bguillaum committed
93 94
  val equals: t -> t -> bool

95 96 97 98
  val node_exists: (G_node.t -> bool) -> t -> bool

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

bguillaum's avatar
bguillaum committed
99 100
  val get_highest: t -> int

101 102
  val push_rule: string -> t -> t

103 104
  (** [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
105 106 107 108 109

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

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

bguillaum's avatar
bguillaum committed
112
  val of_conll: ?domain:Domain.t -> Conll.t -> t
113
  val of_json: json -> t
bguillaum's avatar
bguillaum committed
114

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

119
  val of_pst: ?domain:Domain.t -> Ast.pst -> t
120

bguillaum's avatar
bguillaum committed
121 122 123 124 125 126 127 128 129
  (* ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ *)
  (* 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
130

bguillaum's avatar
bguillaum committed
131 132
  (** [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 *)
133
  val del_edge: ?edge_ident: string -> Loc.t -> t -> Gid.t -> G_edge.t -> Gid.t -> t option
134

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

139 140 141
  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
142

143 144 145 146 147 148 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
  (** 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
181

182
  (** [update_feat domain tar_id tar_feat_name concat_items] sets the feature of the node [tar_id]
183 184
      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 *)
185
  val update_feat: ?loc:Loc.t -> t -> Gid.t -> string -> Concat_item.t list -> (t * string)
pj2m's avatar
pj2m committed
186

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

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

bguillaum's avatar
bguillaum committed
193 194 195
  (* ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ *)
  (* Output functions *)
  (* ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ *)
196
  val to_gr: t -> string
197
  val to_dot: ?main_feat:string -> ?get_url:(string -> string option) -> ?deco:G_deco.t -> t -> string
198
  val to_sentence: ?main_feat:string -> ?deco:G_deco.t -> t -> string
199 200
  val to_dep: ?filter: (string -> bool) -> ?main_feat:string -> ?deco:G_deco.t -> t -> string
  val to_conll: t -> Conll.t
201
  val to_conll_string: ?cupt:bool -> t -> string
202
  val to_json: t -> json
Bruno Guillaume's avatar
Bruno Guillaume committed
203

Bruno Guillaume's avatar
Bruno Guillaume committed
204
  val cast: ?domain:Domain.t -> t -> t
205 206

  val is_projective: t -> (Gid.t * Gid.t) option
207 208

  val depth_first_search: t -> unit
209
end (* module G_graph *)
210

Bruno Guillaume's avatar
Bruno Guillaume committed
211
(* ================================================================================ *)
212 213 214 215 216 217
module Delta : sig
  type t

  val empty: t

  val del_node: Gid.t -> t -> t
218 219
  val add_edge: Gid.t -> G_edge.t -> Gid.t -> t -> t
  val del_edge: Gid.t -> G_edge.t -> Gid.t -> t -> t
220
  val set_feat: G_graph.t -> Gid.t -> feature_name -> value option -> t -> t
Bruno Guillaume's avatar
Bruno Guillaume committed
221
end (* module Delta *)
222

Bruno Guillaume's avatar
Bruno Guillaume committed
223
(* ================================================================================ *)
224 225 226 227 228
module Graph_with_history : sig
  type t = {
    seed: G_graph.t;
    delta: Delta.t;
    graph: G_graph.t;
229
    added_gids: (string * Gid.t) list;
230 231
  }

232 233
  val from_graph: G_graph.t -> t

234
  val compare: t -> t -> int
Bruno Guillaume's avatar
Bruno Guillaume committed
235
end (* module Graph_with_history *)
236

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