Type graph
AGG supports the possibility to create a typed graph grammar. In a typed graph grammar the type description by the well-known 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 -> 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. An edge type can be compared to an association and a node type can be compared to a class in a UML class diagram. 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 assotiation'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.
Using a typed graph grammar has several positive effects:
- The number of negative application conditions for rules might decrease due to multiplicities..
- The number of consistency conditions might decrease due to mulitplicities.
- The efficiency of the critical pair analysis increases, since a number of overlapping graphs are ruled out according to multiplicities given, especially upper bounds of multiplicites.
Graphical user interface
A new type graph can be created from the File menu of the AGG menu bar or with item New Type Graph of popup menu GraGra after pressing the right mouse button on the gragra node in the GraGras tree view. After selecting the type graph in the GraGras tree view, it will be loaded in the AGG graph editor. Editing the type graph is similar to editing the host graph of a grammar. Using popup menu Type Graph allows us to set a kind of type graph check. The popup menu is available after pressing the right mouse button on the type graph node in the GraGras tree view. Type Graph popup menu
It describes the behavior of the type graph check and defines how the type graph is used.
disabled The type graph is ignored, thus all graphs can 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 can 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 can only contain objects with types defined in the type graph. Multiplicities in all graphs should satisfy the defined maximum constraints. enabled with min and max The type graph is used completely, thus all graphs can only contain objects with types defined in the type graph. Multiplicities in all graphs must satisfy the defined maximum constraints and aditionally the working graph must satisfies the defined minimum constraints. Delete The type graph is destroyed. All graphs can contain objects with types defined in the type set of the grammar. If the type graph check is set, the defined type graph is used during all changes of the grammar.
The multiplicity of the source and target of an edge type can be set in a multiplicity dialog which can be accessed by the popup menu of edges when you are editing a type graph.
The multiplicity dialog is shown in Figure 1.
Figure 1. The multiplicity dialog.
Some examples of input possibilities and interpretations are shown in table 1. Please note that the interpretation of multiplicities is as in UML.
Src_min Src_ max Tar_min Tar_max Source Target UML TypeGraph
* * * * * *
1
1 0..1 0..1 0..1 0..1 0..1 0..1
*
* * * * * * * 3
2
3..* 2..* 3..* 2..* 3..* 2..* 0
0
0..* 0..* 0..* 0..* 0..* 0..* 1 1 1 1 1..1 1..1 1 1 ^M1 1 ^M1 3 1 5 1..3 1..5 1..3 1..5 1..3 1..5 Table 1. Multiplicity examples.
An example: As an example of TG we use the grammar ''MarryGoRound`` described in Graph consistency checking in AGG. The type graph of this grammar is shown in Figure 1.
Figure 1. The type graph.
The start graph of the grammar is shown in Figure 2.
Figure 2. The start graph.
The whole graph grammar ''MarryGoRound`` is shown in Graph consistency checking in AGG.
Revision: