Building the Arcs

 Directed labelled arcs are added to the graph, representing the geometric relationship between the nodes they link. Instead of making a complete graph, with arcs between every pair of nodes, it is restricted so that only ``reasonable'' arcs are put in. The constraint on having only ``reasonable'' arcs simplifies the resulting graph. The fewer arcs in a graph, the less likely it is to represent multiple formulae. For example, if a 2 is linked so that a single x node is both to it's ``right'' and ``top-right'', it simultaneously represents the formula 2x and 2^x. On the other hand, too few arcs and the graph will not represent a valid formula at all, either because it is not connected or an essential arc is missing. Depending on the graph matching algorithm used by the graph-rewriting parser, having fewer edges in the graph may also result in a speed increase.

Every time the graph is changed, in later preprocessing and parsing steps, the arcs are rebuilt. While graph grammars can have rules that specify how arcs are handled as nodes are replaced and added, for a formula processing application the arcs have to be rebuilt every time the graph changes. This is because you need to check if arcs that may not have originally been in the graph have to be added. For example, in the formula:

x^-y

there would be no link between the original x and - nodes, as the arc construction type check, described below, does not allow the expression x^-. After collapsing the - and y to make a single -y node, this node has to be linked to the x for it to continue parsing. Without globally recomputing all the arcs in the graph, it is not possible to automatically determine whether or not new links such as this should be added.

As each arc represents a geometric relationship between the two nodes it connects, various checks are made to confirm that the link makes sense. There are three tests, related to the types, the geometric relationship between them, and whether or not there is anything else between them.