# 8. Data Formats¶

This page gives an overview of the *external* data formats that MØD works with.
For the formats that describe graphs and rules there are details on how
the external format is interpreted when creating the corresponding in-memmory
data structure. The in-memory model is described in Graph, Rule, and Molecule Model.

## 8.1. GML¶

MØD uses the Graph Modelling Language (GML) for general specification of graphs and rules. The parser recognises most of the published specification, with regard to syntax. The specific grammar is as follows.

GML::= (`key`

`value`

)*key::=`identifier`

value::= int float quoteEscapedString`list`

list::= '[' (`key`

`value`

)* ']'identifier::= a word matching the regex "[a-zA-Z][a-zA-Z0-9]*"

A `quoteEscapedString`

is zero or more characters surrounded by double
quotation marks. To include a `\"`

character it must be escaped. Tabs,
newlines, and backslashses can be written as `\t`

, `\n`

, and `\\`

.
GML code may have line comments, starting with `#`

.
They are ignored during parsing.

### 8.1.1. Graph¶

A graph can be specified as GML by giving a list of vertices and edges
with the key `graph`

.
The following grammar exemplifies the required key-value structure.

graphGML::= 'graph [' (`node`

|`edge`

)* ']'node::= 'node [ id' int 'label' quoteEscapedString ']'edge::= 'edge [ source' int 'target' int 'label' quoteEscapedString ']'

Note though that list elements can appear in any order.

### 8.1.2. Rule¶

A rule \((L\leftarrow K\rightarrow R)\) in GML format is specified
as three graph fragments; `left`

, `context`

, and `right`

.
From those
\(L\) is constructed as `left`

\(\cup\) `context`

,
\(R\) as `right`

\(\cup\) `context`

, and
\(K\) as `context`

\(\cup\) (`left`

\(\cap\) `right`

).
Each graph fragment is specified as a list of vertices and edges, similar to a
graph in GML format.
The key-value structure is exemplified by the following grammar.

ruleGML::= 'rule [' [ 'ruleID' quoteEscapedString ] [ 'labelType "'`labelType`

'"' ] [`leftSide`

] [`context`

] [`rightSide`

]`matchConstraint`

* ']'labelType::= 'string' | 'term'leftSide::= 'left [' (`node`

|`edge`

)* ']'context::= 'context [' (`node`

|`edge`

)* ']'rightSide::= 'right [' (`node`

|`edge`

)* ']'matchConstraint::=`adjacency`

|`labelAny`

adjacency::= 'constrainAdj [' 'id' int [ 'nodeLabels ['`labelList`

']' ] [ 'edgeLabels ['`labelList`

']' ] 'op "'`op`

'"' 'count' unsignedInt ']'labelAny::= 'constrainLabelAny [' 'label' quoteEscapedString 'labels ['`labelList`

']' ']'labelList::= ('label' quoteEscapedString)*op::= '<' | '<=' | '=' | '>=' | '>'

Note though that list elements can appear in any order.

For details on the constraints, see Application Constraints.

#### 8.1.2.1. A Note on Term Labels¶

As described in Switching Category — First-Order Terms as Labels it is possible to interpret the
ordinary vertex and edges labels as first-order terms.
When using the label `*`

it will be interpreted as an unnamed term variable.
Consider the rule:

```
rule [
left [ node [ id 0 label "*" ] ]
right [ node [ id 0 label "*" ] ]
]
```

In string mode this is simply an identity rule, but in term mode each `*`

is interpreted as an unnamed variable. Be careful that in this case the
two labels are interepreted as *the same* variable. That is, it is equivalent
to:

```
rule [
left [ node [ id 0 label "_A" ] ]
right [ node [ id 0 label "_A" ] ]
]
```

If you wish to replace any vertex label with an explicit new variable, you can write it as:

```
rule [
left [ node [ id 0 label "_A" ] ]
right [ node [ id 0 label "_B" ] ]
]
```

## 8.2. SMILES¶

The Simplified molecular-input line-entry system is a line notation for molecules. MØD can load most SMILES strings, and converts them internally to labelled graphs according to a specific molecule encoding. For graphs that are sufficiently molecule-like, a SMILES string can be generated. The generated strings are canonical in the sense that the same version of MØD will print the same SMILES string for isomorphic molecules.

The reading of SMILES strings is based on the OpenSMILES specification, but with the following notes/changes.

Only single SMILES strings are accepted, i.e., not multiple strings separated by white-space.

Up and down bonds are regarded as implicit bonds, i.e., they might represent either a sngle bond or an aromatic bond. The stereo information is ignored.

Atom classes are (mostly) ignored. They can be used to specify unique IDs to atoms.

Wildcard atoms (specified with

`*`

) are converted to vertices with label`*`

. When inside brackets, only the hydrogen count and atom class is then permitted.Abstract vertex labels can be specified inside brackets. The bracket must in that case only contain the label and an optional class label. The label must be a non-empty string without

`:`

and with balanced square brackets.Charges of magnitude 2 and 3 may be specified with repeated

`-`

and`+`

.The bond type

`$`

is currently not allowed.Aromaticity can only be specified using the bond type

`:`

or using the special lower case atoms. I.e.,`c1ccccc1`

and`C1:C:C:C:C:C:1`

represent the same molecule, but`C1=CC=CC=C1`

is a different molecule. The lower-case atoms are converted to normal case when used as a label.Ring-bonds and branches may appear in mixed order. The normal order is to have all ring-bonds first and all branches, e.g.,

`C123(O)(N)`

. The parser accepts them in mixed order, e.g.,`C1(O)2(N)3`

.Implicit hydrogens are added following a more complicated procedure (see below).

A bracketed atom can have a radical by writing a dot (

`.`

) between the position of the charge and the position of the class.

The written SMILES strings are intended to be canonical and may not conform to any “prettyness” standards.

### 8.2.1. Implicit Hydrogen Atoms¶

When SMILES strings are written they will use implicit hydrogens whenever they
can be inferred when reading the string back in.
For the purposes of implicit hydrogens we use the following definition of
valence for an atom.
The valence of an atom is the weighted sum of its incident edges, where single
(`-`

) and aromatic (`:`

) bonds have weight 1, double bounds (`=`

) have
weight 2, and triple bonds (`#`

) have weight 3.
If an atom has an incident aromatic bond, its valence is increased by 1.
The atoms that can have implicit hydrogens are
B, C, N, O, P, S, F, Cl, Br, and I.
Each have a set of so-called “normal” valences as shown in the following table.
The atoms N and S additionally have certain sets of incident edges that are
also considered “normal”, which are also listed in the table.

Atom |
Normal Valences and Neighbourhoods |
---|---|

B |
3 |

C |
4 |

N |
3, 5, \(\{-, :, :\}\), \(\{-, -, =\}\), \(\{:, :, :\}\) |

O |
2 |

P |
3, 5 |

S |
2, 4, 6, \(\{:, :\}\) |

F, Cl, Br, I |
1 |

If the set of incident edges is listed in the table, then no hydrogens are added. If the valence is higher than the highest normal valence, then no hydrogens are added. Otherwise, hydrogens are added until the valence is at the next higher normal valence.

When writing SMILES strings the inverse procedure is used.

## 8.3. DFS Line Notation¶

The DFS formats are intended to provide a convenient line
notation for general undirected labelled graphs and rules.
Thus it is in many aspects similar to SMILES strings and reaction SMILES
strings, but a string being both a valid (reaction SMILES) string and
GraphDFS/RuleDFS string **does not mean they represent the same objects**.
In particular, the semantics of ring-closures/back-edges are not the same.

### 8.3.1. GraphDFS¶

graphDFS::=`chain`

chain::=`vertex`

`evPair`

*vertex::= (`labelVertex`

|`ringClosure`

)`branch`

*evPair::=`edge`

`vertex`

labelVertex::= '[' bracketEscapedString ']' [`defRingId`

]`implicitHydrogenVertexLabels`

[`defRingId`

]implicitHydrogenVertexLabels::= 'B' | 'C' | 'N' | 'O' | 'P' | 'S' | 'F' | 'Cl' | 'Br' | 'I'defRingId::= unsignedIntringClosure::= unsignedIntedge::= '{' braceEscapedString '}'`shorthandEdgeLabel`

shorthandEdgeLabel::= '-' | ':' | '=' | '#' | '.' | ''branch::= '('`evPair`

+ ')'

A `bracketEscapedString`

and `braceEscapedString`

are zero or more
characters except respectively `]`

and `}`

. To have these characters in
each of their strings they must be escaped, i.e., `\]`

and `\}`

respectively.

Whitespace is ignored, except inside `bracketEscapedString`

and
`braceEscapedString`

.

The parser additionally enforces that a `defRingId`

may not be
a number which has previously been used.
Similarly, a `ringClosure`

may only be a number which has
previously occured in a `defRingId`

.

A vertex specified via the `implicitHydrogenVertexLabels`

rule
will potentially have ekstra neighbours added after parsning. The rules are the
exact same as for implicit hydrogen atoms in SMILES.

#### 8.3.1.1. Semantics¶

A GraphDFS string is, like the SMILES strings, an encoding of a depth-first
traversal of the graph it encodes. Vertex labels are enclosed in square
brackets and edge labels are enclosed in curly brackets. However, a special
set of labels can be specified without the enclosing brackets.
An edge label may additionally be completely omitted as a shorthand for a dash
(`-`

).

A vertex can have a numeric identifier, defined by the
`defRingId`

non-terminal.
At a later stage this identifier can be used as a vertex specification to
specify a back-edge in the depth-first traversal.
Example: `[v1]1-[v2]-[v3]-[v4]-1`

, specifies a labelled \(C_4\)
(which equivalently can be specified shorter as `[v1]1[v2][v3][v4]1`

).

A `vertex`

being a `ringClosure`

can never be
the first vertex in a string, and is thus preceded with a
`edge`

. As in a depth-first traversal, such a back-edge is a
kind of degenerated branch. Example: `[v1]1[v2][v3][v4]1[v5][v6]1`

, this
specifies a graph which is two fused \(C_4\),
\(v_1, v_2, v_3, v_4\) and \(v_4, v_5, v_6, v_1\),
with a common edge, \((v_1, v_4)\).

Warning

The semantics of back-edges/ring closures are **not** the same as
in SMILES strings. In SMILES, a pair of matching numeric identifiers denote
the individual back-edges.

A branch in the depth-first traversal is enclosed in parentheses.

The `shorthandEdgeLabel`

`.`

indicates a non-edge,
i.e., a jump to a new vertex without creating an edge.
For example `[v1].[v2]`

encodes a graph with two vertices and no edges,
while `[v1]{.}[v2]`

encodes a graph with two vertcies connected with an edge
with label `.`

.

#### 8.3.1.2. Abstracted Molecules¶

The short-hand labels for vertices and edges makes it easier to specify partial molecules than using GML files.

As example, consider modelling Acetyl-CoA in which we wish to abstract most of
the CoA part. The GraphDFS string `CC(=O)S[CoA]`

can be used and we let the
library add missing hydrogen atoms to the vertices which encode atoms. A plain
CoA molecule would in this modelling be `[CoA]S`

, or a bit more verbosely as
`[CoA]S[H]`

.

The format can also be used to create completely abstract structures (it can encode any undirected labelled graph), e.g., RNA strings. Note that in this case it may not be appropriate to add “missing” hydrogen atoms. This can be controlled by an optional parameter to the loading function.

### 8.3.2. RuleDFS¶

The rule format builds on the graph format by using two GraphDFS strings to encode a rule:

ruleDFS::= [`graphDFS`

] '>>' [`graphDFS`

]

The two (possibly empty) GraphDFS strings encode the left-hand and right-hand side of a rule, with the vertex IDs being used to relate them. That is, a pair of vertices in the left side and right side with the same ID will be identified and the vertex put in the context graph of the rule as well. A similar pair of edges where both end-points are in the context graph will be put in the context graph as well.

Examples:

`>>`

: the empty rule.`[A]>>`

: a rule with a single vertex in \(L\), and empty \(K\) and \(R\).`[A]>>[B]`

: a rule with empty \(K\) but with a vertex in \(L\) which is removed by the rule, and a vertex in \(R\) being created by the rule.`[A]1>>[B]1`

: a rule with a vertex changing label from “A” to “B”.

Note

Currently it is not possible to use vertices with implicit hydrogens in RuleDFS.

## 8.4. MOL and SD¶

MØD can load graphs stored in the
CT File formats
MOL (single structure) and SD (multiple structures).
See the loading functions in `graph::Graph`

/`Graph`

for
the API.
The loaded structures are converted to labelled graphs according to a specific
molecule encoding.

The reading of structures is based on the published specification, but with the following notes/changes.

the

`MDLOptions`

/`MDLOptions`

can be used to customize the loading procedure.radical value 2 is converted to

`.`

in the vertex labels.the atom symbols “LP” and “L” are used as is, as an atom with an abstract label.

the atom symbols “A”, “Q”, and “*” are all considered as wildcard atoms and are converted to vertices with label

`*`

. See the use of first-order terms as labels.the bond orders 5, 6, and 7 for constrained wildcard bonds are converted to edges with labels starting with

`_Q`

, i.e., term variables. See the use of first-order terms as labels.the bond order 8 for unconstrianed bonds are converted to edges with label

`*`

. See the use of first-order terms as labels.

## 8.5. Abstract Derivation Graphs¶

Sometimes it is really convenient to quickly write down a few equations to describe a “derivation graph”, without associating actual graphs and rules to it. That is, only specifying the underlying network. The network description is a string adhering to the following grammar:

description::=`derivation`

{`derivation`

}derivation::=`side`

("->" | "<=>")`side`

side::=`term`

{ "+"`term`

}term::= [ unsignedInt ]`identifier`

identifier::= any character sequence without spaces

Note that the `identifier`

definition
in particular means that whitespace is important between coefficients and
identifiers. E.g., `2 A -> B`

is different from `2A -> B`

.

See also `DG.Builder.addAbstract()`

/`dg::Builder::addAbstract()`

.

## 8.6. Tikz¶

Both graphs and rules are visualized through PostMØD by the library generating Tikz code and compiling it with Latex.

The visualisation style is controlled by passing instances of
`mod::graph::Printer`

/`mod.GraphPrinter`

to the printing functions.
The drawing style is inspired by ChemFig
and Open Babel.

The coordinates for the layout is either generated using Open Babel when the graphs a chemical enough, but otherwise Graphviz is invoked to generate coordinates.

For visualizing a rule or DPO diagram, the position of vertices is used to indicate how morphisms map vertices to each other.

## 8.7. DOT (Graphviz)¶

The DOT format (from Graphviz) is used for generating vertex coordinates for the Tikz format, when Open Babel can not be used.