next up previous contents
Next: Graph Parser Up: Analyzing Graphs and Graph Previous: Post Application Conditions   Contents

Critical Pair Analysis

AGG provides the analysis technique of critical pair analysis3.

Critical pair analysis is known from term rewriting and used there to check if a term rewriting system is confluent. It has been generalized to graph rewriting. Critical pairs formalize the idea of a minimal example of a conflicting situation. From the set of all critical pairs we can extract the objects and links which cause conflicts or dependencies.

A critical pair is a pair of transformations $(p1, p2)$ , with $p1(m1) : G => H1$ and $p2(m2) : G => H2$ which are in conflict, such that graph $G$ being minimal. Roughly speaking, $G$ is the gluing of the left-hand sides of the rules $p1$ and $p2$. It can be computed by overlapping $L1$ and $L2$ in all possible ways such that the intersection of $L1$ and $L2$ contains at least one item that is deleted or changed by one of the rules and both rules are applicable to $G$ at their respective occurences.
The set of critical pairs represents precisely all potential conflicts. That means a critical pair $(p1, p2)$ exists iff, the application of $p1$ disables that of $p2$ or, vice versa.
After the computation of all critical pairs, the overall rule set can be structured into conflict-free and conflicting rules.

There are three reasons why rule applications can be conflicting. The first two are related to the graph structure while the last one concerns the graph attributes.

  1. One rule application deletes a graph object which is in the match of another rule application.
  2. One rule application generates graph objects in a way that a graph structure would occur which is prohibited by a negative application condition (NAC) of another rule application.
  3. One rule application changes attributes being in the match of another rule application.

Two rule applications are in conflict if at least one of the conditions above is fulfilled. To find all conflicting rule applications, minimal critical graphs are computed to which rules can be applied in a conflicting way.

According to three conflict conditions mentioned above we distinguish three kinds of conflicts:

  1. delete - use conflict: Here we consider overlapping graphs of the left-hand sides of two rules.
  2. produce - forbid conflict: Here we consider overlapping graphs of the right-hand side of the first rule and a NAC-graph of the second rule. Such a NAC-graph consists of the left-hand side and graph objects prohibited by a negative application condition of a rule.
  3. change - use attribute conflict: Here we consider overlapping graphs of the left-hand sides of two rules.
    In the case of a change - forbid attribute conflict we consider all overlapping graphs of the left-hand side of the first rule and a NAC-graph of the second rule.

Analogously, there are three reasons why rule applications can depend of one another. The first two are related to the graph structure while the last one concerns the graph attributes.

  1. One rule application produces graph objects which are consumed by another rule application.
  2. One rule application deletes graph objects in a way that a graph structure is deleted which is also prohibited by a negative application condition (NAC) of another rule application.
  3. One rule application changes an attribute which is read by another rule application.

One rule application is dependent of another one if at least one of the conditions above is fulfilled. To find all dependent rule applications, minimal critical graphs are computed which apply rules in a depending way.

According to three dependencies conditions mentioned above we distinguish three kinds of dependencies:

  1. produce - use dependency: Here we consider overlapping graphs of the right-hand side of the first rule and the left-hand side of the second rule.
  2. delete - forbid dependency: Here we consider overlapping graphs of the left-hand side of the first rule and a NAC-graph of the second rule.
  3. change - use attribute dependency: Here we consider overlapping graphs of the right-hand side of the first rule and the left-hand side of the second rule.
    In the case of a change - forbid attribute dependency we consider all overlapping graphs of the right-hand side of the first rule and a NAC-graph of the second rule.

Dependencies of two rules can be computed by inverting the first rule and finding its conflicts with the second rule and then by renaming

Additionally, in each case we consider the obvious matches and analyze the rule applications. All conflicting and depending rule applications we found are called critical pairs.

AGG provides the possibility to detect these two kinds of critical pairs:

The algorithm which computes conflicts and dependencies has been completely reworked. The new implementation is much faster and provides better results.

The graphical user interface (GUI) of critical pair analysis (CPA) was redesigned, too. In its new shape, the CPA GUI gives clear and sufficient information about critical pairs. The GUI is convenient to consider a critical pair in more detail. I.e. for each pair the two rules, all critical overlapping graphs and corresponding matches can be shown. The currently selected overlapping graph and the rule graphs used for this overlapping graph become highlighted in yellow. The overlapping graph objects (nodes and edges) are numbered to show embeddings of rule graphs. The critical graph objects are colored in green.

The menu Critical Pair Analysis in Fig. 45 is part of menu Analyzer. The availability of its items depends on the state of the critical pair analysis.

Figure 45: The Critical Pair Analysis menu
\begin{figure}\def
\epsfsize  ...

The items of menu Critical Pair Analysis are described below:

The options of the critical pair analysis are available in menu Preferences / Options... and shown in Figure 46.

Figure 46: The options of the critical pair analysis
\begin{figure}\def
\epsfsize  ...

The options are explaned here:

With AGG it is possible to show all conflicts and dependencies of rules within the so-called CPA graph. In this graph the nodes are rules, the red edges correspond to conflicts and the blue edges to dependencies between rules. The directed edges mean asymmetric and the undirected edges mean symmetric conflicts/dependencies between rules. A pop-up menu invoked on the background of the CPA graph allows to manipulate the graph view. Moreover, a pop-up menu on each entry of the critical pair table allows to hide/show appropriate node or edge(s) of the CPA graph.

The critical pair analysis GUI is shown in Figure 47 for example ''StateCharts''.
Clicking on a field of the certain rule pair in the table in the CPA panel has the following effect (the first rule is determined by the row, the second by the column):

  1. The first rule and the second rule are shown in the CPA panel.
  2. The computed critical graphs will be shown in the CPA panel.
  3. The mappings between graph objects will be shown through equal numbers.
  4. If no critical pairs exist, a message 'not critical' will be shown.

Figure 47: Critical Pair Analysis GUI
\begin{figure}\def
\epsfsize  ...

Figure 48 shows the critical pairs of rule addTrans_SaSaS with itself. This rule creats a new edge abs. Its NAC forbids multi-creation of this edge. So we can get a conflict situation during multi-application of this rule as shown by graphs in Figure 48.

Figure 48: Critical Pairs of addTrans_SaSaS with itself
\begin{figure}\def
\epsfsize  ...

Another critical rule pair of this grammar is shown in Figure 49.

Figure 49: Critical Pairs of delT2 with delT1
\begin{figure}\def
\epsfsize  ...

Here we can see critical graph objects. The conflict occurs, because the first rule deletes objects which the second rule needs.

In Figure 50 the complete set of generated critical pairs is shown as a table with red (critical) and green (non-critical) fields of rule pairs.

Figure 50: Critical Pairs of StateCharts
\begin{figure}\def
\epsfsize  ...

Critical pair analysis for grammar rules can be more efficient, if a type graph is defined containing multiplicity constraints. Upper bounds of multiplicity constraints are used to reduce the set of critical pairs by throwing out the meaningless ones. Dependent on the graph grammar, the number of critical pairs can be reduced drastically by the use of multiplicity constraints.
Moreover, the set of critical pairs can be reduced considerably by defining graph constraints. In the reduced set there are critical pairs with consistent overlapping graphs only.
Please note: Not all kinds of graph constraints are used for reduction, but only those which forbid the existence of graph structures.

Figure 51 shows the type graph of the StateCharts grammar.

Figure 51: Type graph of the StateCharts grammar
\begin{figure}\def
\epsfsize  ...

Figure 52 shows critical pairs of the StateCharts grammar with the type graph in Figure 51 and graph constraints in Figures 38 - 43.

Figure 52: Critical Pairs of StateCharts with a type graph and graph constraints
\begin{figure}\def
\epsfsize  ...

Please note: the critical pair analysis may take time, even for one particular rule pair.

As already said above, critical pairs show potential parallel conflicts and sequential dependencies between transformations. The computation of conflicts is started by menu item Generate/Conflicts, the computation of dependencies by menu item Generate/Dependencies.

Now we want to use a refactorings example ''BasicGraph'' to show not only these two kinds of conflicts, but also to introduce a graph representation based on computed critical pairs. The grammar ''BasicGraph.ggx'' can be found in the examples folder Refactorings when downloading AGG . This example was introduced in the PhD thesis of Tom Mens: ''A Formal Foundation for Object-Oriented Software Evolution.'' (PhD thesis, Department of Computer Science, Vrije Universiteit Brussel, Belgium, September 1999.) ''BasicGraph'' is a very general case study. The models that can be represented by this grammar are directed, attributed, typed graphs. The rules are very simple, but allow to make arbitrarily complex changes to any given graph structure. There are the following rules : AddNode, AddEdge, DeleteNode, DeleteEdge, RenameNode, RenameEdge, RetypeNode and RetypeEdge. Figure 53 shows conflicts between the rule applications.

Figure 53: Minimal conflicts between rules of ''BasicGraph''
\begin{figure}\def
\epsfsize  ...
We want to get a closer look at the rule pair DeleteNode and AddEdge. The rules and two delete-use conflict situations are shown in Fig. 54. It is clear that the node to delete could be a source or a target node of a new edge to add. After the rule DeleteNode is applied, the rule AddEdge cannot be applied to previous two nodes.

Figure 54: Conflict of DeleteNode with AddEdge
\begin{figure}\def
\epsfsize  ...

Another example in Fig. 55 shows two attribute conflicts of rule RenameNode with itself.
In the case of a change - use attribute conflict this rule changes the name of a node which is in the match of its other application. In the case of a change - forbid attribute conflict the new name of the node can occur in a graph structure that is prohibited by a negative application condition of the rule and its application is not possible anymore.

Figure 55: Attribute conflicts of RenameNode with itself
\begin{figure}\def
\epsfsize  ...

The table of critical pair analysis in Fig. 56 shows all those critical pairs reporting sequential dependencies between rule applications.

Figure 56: Minimal dependencies between rules of ''BasicGraph''
\begin{figure}\def
\epsfsize  ...

Now we have a look at the rule pair AddNode and AddEdge. The rules and two produce-use dependency situations are shown in Fig. 57. As we can see, first a special node should be added and then the desired edge.

Figure 57: Sequential dependency AddEdge on AddNode
\begin{figure}\def
\epsfsize  ...

An example of a change - use attribute dependency is shown in Fig. 58. The application of rule RetypeNode may read the value of the attribute name after the application of rule RenameNode has changed this attribute in suitable way.

Figure 58: Attribute dependency of RetypeNode on RenameNode
\begin{figure}\def
\epsfsize  ...

As said above, AGG provides the possibility to visualize conflicts and dependencies within the so-called CPA graph. This graph is automatically computed by considering all critical pairs for conflicts and dependencies. The CPA graph for example ''BasicGraph'' is shown in Fig. 59.

Figure 59: CPA graph for ''BasicGraph''
\begin{figure}\def
\epsfsize  ...

Using the pop-up menu of this graph we can get a view on conflicts or dependencies only. Such views on the CPA graph are shown in Figures 60 - 61.

Figure 60: CPA graph for ''BasicGraph'' with conflicts only
\begin{figure}\def
\epsfsize  ...

Figure 61: CPA graph for ''BasicGraph'' with dependencies only
\begin{figure}\def
\epsfsize  ...

The CPA graph can be very complex if the given rules have many conflicts and dependencies. In order to get a better understanding of all conflicts and dependencies it is useful to hide certain edges and nodes dynamically. This can be done by right-clicking on a node or an edge and choosing item Hide Node/Edge of the appearing pop-up menu. Another possibility to manipulate the CPA graph is by using pop-up menus on the entries of the conflict and dependency tables and choosing item Hide Relation or Hide Rule. A certain rule has to be hidden in each table, before it becomes hidden in the CPA graph.

Analysing the CPA graph, the user can get some help about the order in which the transformations should be performed. For example, Fig. 61 shows that DeleteEdge should be performed before DeleteNode. On the other hand, in Fig. 60 one can see that the rules DeleteNode, RenameNode, RetypeNode and AddEdge are all in symmetrical conflict with each other.

The automatic conflict resolution analysis in AGG is left to future work.

Critical pair analysis is described in:

Critical pair analysis is used in:


next up previous contents
Next: Graph Parser Up: Analyzing Graphs and Graph Previous: Post Application Conditions   Contents
Olga Runge 2006-08-16