Hyperedge Replacement Graph Grammars

The second talk was held on October 25, 2007. It was about Hyperedge Replacement Graph Grammars HRG. I know, I know, ... In the last post I promised to focus more on practical things. But: Hyperedge replacement is more practical than you might think. For instance, hypergraphs can be used as a model for visual languages as realized in the tool DiaGen. Following this approach a visual language can be defined via a HRG and syntax analysis of diagrams can be reduced to hypergraph parsing.

The main advantages of HRG are:

• easy to grasp


• very close analogy to context-free string grammars


• straightforward syntax analysis possible

I cannot introduce the whole theory in a single blog post, so I give you an impression by showing some pictures.



This is a flowchart. It consists of statements (rectangles) and conditions (diamonds) that are linked with arrows indicating the flow of control. The presented algorithm is the so-called Hasse-Collatz problem but this is not so interesting here. More interesting is the fact, that due to their graph-like structure flowcharts can be described by a HRG quite straightforwardly.



However, before I can show you the HRG I first have to give a possible hypergraph model of the example flowchart. Every flowchart component is mapped to a hyperedge represented by a rectangle. In contrast to directed edges a hyperedge may connect an arbitrary number of nodes so that a representation by an arrow is not possible in general. The nodes are given by filled black circles. Nodes visited by a particular hyperedge are connected to this edge by a line called a tentacle of the edge. Each tentacle has a particular role, for instance, it has to be clear which tentacle of a cond edge represents the true and which one the false case. Hyperedges with the same label have to visit the same number of nodes called the type of the edge.



Now we can discuss the HRG of structured flowgraphs (the graphs behind a correct flowchart). A HRG is defined by a set of nonterminal labels N, a set of terminal labels T, a set of productions P and a starting label S that has to be an element of N. The productions are given in the picture in a notation similar to BNF. They are recursively defined in a quite intuitive manner. Note, that a HRG production always has a single nonterminal edge on the lhs. As a consequence HRGs have nice properties resulting from this kind of contextfreeness. However, it is also a restriction, because important graph languages cannot be described that way.

HRG is a kind of DPO (as introduced in the last post about the algebraic approach). The gluing graph consists just of the nodes that occur in both the lhs and the rhs of a production.



Due to the contextfreeness of HRG it is possible to construct derivation trees. Such a tree can be represented as shown in the picture (it is the tree for our example). All leafs are marked with terminal symbols and nodes with nonterminal symbols. The number of subtrees of a node depends on the number of hyperedges on the rhs of the applied production. The numbers in parentheses are the corresponding node numbers of the graph model.

Further reading:

• Handbook of Graph Grammars and Computing by Graph Transformation, Rozenberg (ed.), 1997, World Scientific Publishing: chapter 2