Defining a Type Graph

AGG supports the possibility to create a typed graph grammar. In a typed graph grammar the type description by type sets (label sets) for nodes and edges is extended by a type graph. One major disadvantage of type sets is that edge types do not prescribe the types of source and target nodes. This additional information can be given by type graphs: A fixed graph TG, called type graph, represents the type information, and the typing of a graph G over TG is given by a total graph morphism $t: G \to TG$.

In general, nodes and edges of TG represent nodes and edges types, while attributes are attribute declarations. The edges in TG represent a structural relationship among objects. A node type can be compared to a class in UML class diagram and an edge type can be compared to an association. It is important to state how many objects may be connected through an instance of an edge type. This ''how many`` is called the multiplicity of an association's role in UML, and is specified by a range of values or an explicit value.

When you state a multiplicity at the target end of an edge type, you specify the number of nodes which may be connected to one source node across edges of the given edge type. A multiplicity at the source end of an edge type is interpreted similarily. It is also possible to state a multiplicity at a node.

Using typed graph grammar has several positive effects since multiplicities pose additional graph constraints on a graph:

• the number of negative application conditions for rules might decrease,
• the number of consistency conditions might decrease,
• the efficiency of the critical pair analysis might increases, since a number of overlapping graphs might be ruled out according to multiplicities given. Especially upper bounds of multiplicites are useful to reduce the number of overlapping graphs.

A new type graph can be created by item New Type Graph of the pop-up menu of GraGra. An empty type graph will be loaded in the graph editor. Editing this graph is similar to editing the host graph of a grammar.

Using the pop-up menu of TypeGraph shown in Figure 2 we can define the usage of the type graph.

Figure 2: Pop-up menu of TypeGraph

The meaning of the items is :

• disabled - the type graph is ignored. Thus, all graphs contain objects with types defined in the type set of the grammar. Multiplicities are also ignored.
• enabled - the type graph is basically used. Thus, all graphs only contain objects with types defined in the type graph, but multiplicities are not checked.
• enabled with max - the type graph is basically used. Thus, all graphs only contain objects with types defined in the type graph. Multiplicities in all graphs should satisfy the defined maximum bounds.
• enabled with min and max - the type graph is used completely. Thus, all graphs only contain objects with types defined in the type graph. Multiplicities in all graphs must satisfy the defined maximum bounds and additionally the host graph must satisfy the defined minimum bounds.
• Delete - the type graph will be destroyed and thus not active anymore.

If the type graph check is set to enabled, enabled with max or enabled with min and max, the defined type graph is used during all changes of the grammar.

The multiplicity of a node type or of the source and target of an edge type can be set in a multiplicity dialog which is accessed by the pop-up menu Operations of nodes and edges when you are editing a type graph.