Graphs definition

The graphs we consider in Grew are defined, as usual in mathematics, by two sets:


A node is described by a an identifier (needed to refer to nodes in edge definitions) and a feature structure: a finite list of pairs (feature_name, feature_value).

In many linguistic structures, the notion of word order plays a crucial role. To take this into account, nodes in a Grew graph are divided into two disjoint subsets:

In the node creation command add_node, the user can choose to add an unordered node or to place the new node before or after a existing one.


An edge is described by two nodes (called the source and the target of the edge) and by an edge label.

Before version 1.2, edge labels were atomic and had no internal structure. This was not very convenient for dealing with complex edges:

In all these cases, with atomic edge labels, it is not possible to treat any part of the label independently. Since version 1.2, the implementation of edge labels has changed to address this problem. Edge labels are now coded as feature structures.

In Grew graphs, an edge label is stored internally as a flat feature structure or, in other words, as a finite set of couples (f_1,v_1)(f_k,v_k) where all f_i are pairwise different. We will use the traditional notation f=v for these pairs.

For backward compatibility and for ease of use in practice, a compact notation can be used for edge labels.

The correspondence between compact notation and feature structure depends on the config parameter. Four predefined configurations are available: ud, sud, sequoia and basic.

The symbol : (used in ud, sud and sequoia) is interpreted as a separator, the left part is assigned feature name 1 and the right part is assigned feature name 2.

Further examples of correspondence between compact and internal representation are given in the tables below.


Relation Compact notation Internal representation
Simple relation obj 1=obj
relation with subtype aux:pass 1=aux, 2=pass
Enhanced UD relation E:nsubj 1=nsuj, enhanced=yes


Relation Compact notation Internal representation
Simple relation mod 1=mod
relation with subtype comp:aux 1=comp, 2=aux
SUD relation with deep feature compl:obl@agent 1=compl, 2=obl, deep=agent


Relation Compact notation Internal representation
Simple relation obj 1=obj
Deep-sequoia (both surf & deep) suj:obj 1=suj, 2=obj
Deep-sequoia (surf only) S:suj:obj 1=suj, 2=obj, kind=surf
Deep-sequoia (deep only) D:suj:obj 1=suj, 2=obj, kind=deep


Relation Compact notation Internal representation
Simple relation obj rel=obj

All other feature names (except a few reserved names) can be used freely in the edge label representation. However, if the internal representation does not correspond to one described in the tables above, there is no compact representation and the internal representation is used.

Reserved feature names are:

Graph input formats

To describe a graph in practice, Grew offers several input formats:

Graph output formats