A Sample Run

In Figure 1 the start graph of grammar ShortestPath.ggx is depicted, consisting of some cities connected by roads.
The rules of the grammar are shown in Figures 22 - 30.

Figure 22: Rule start

Figure 23: Rule expandStart

Figure 24: Rule expand

Figure 25: Further NACs of Rule expand

Figure 26: Rule expandMore

Figure 27: Further NACs of Rule expandMore

Figure 28: Rule setMax

Figure 29: Rule showRoad

Figure 30: Rule showRoad1

Figure 31: Further NACs of Rule showRoad1

Transformation options chosen for our example are injective matches which satisfy the dangling condition, rules with NACs, the completion strategy CSP and layered rules as shown in Figure 32.

Figure 32: Rule layers of grammar ShortestPath

To determine a start and a goal city, we have to define a partial match of rule start by mapping the two cities at the left-hand side. After completing this partial match and applying the rule, the transformation result is shown in Figure 33.

Figure 33: The host graph after applying start rule (in Fig. 22)

The match defines city $A$ to be the start and city $H$ to be the goal of the search. Additionally, rule start defines a maximal distance between start and goal cities. This is done by a node $State: Exp$ where attribute max is set to 10.
Figure 34 shows the host graph after applying rule expandStart three times. Three possible matches of this rule realize the expansion of the start city: for all three neighbours the corresponding edges are generated. The newly generated edges carry the start information of the paths with length from City $A$ to City $H$.

Figure 34: The host graph after applying expandStart rule (in Fig. 23) three times

In Figure 35, we see the host graph after applying rule expand nine times. New edges are generated to all possible cities on the way to the goal. The path lengths have been raised. This rule has an attribute condition $(y+x)<m$ that forbids to follow a path with a new length longer then max m. Four NACs of this rule prevent: 1. the current city is a start city, 2. the current city is a goal city, 3. the next city is a start city, 4. the path to the next city is already expanded.

Figure 35: The host graph after applying expand rule (in Fig. 24) eight times

The next rule to apply is expandMore. That rule compares already computed path lengths and takes the smallest as a best possible path. The NACs of the rule prevent: 1. the current city is a start city, 2. the current city is a goal city, 3. the next city is a start city. In our example this rule is not applicable for chosen the $Start$ - $Goal$ pair of cities.

Now the rule setMax is applicable. In Figure 36, we can see the host graph where attribute max of node State is changed from 10 first to 9 and then to 7.

Figure 36: The host graph after applying setMax rule (in Fig. 28) two times

Finally, Figure 37 shows the host graph after applying showRoad and showRoad1. Rule showRoad marks the last part of the path from start to goal cities and rule showRoad1 marks the next part of the path backwards.

Figure 37: The host graph after showRoad (in Fig. 29) and showRoad1 (in Fig. 30) applied once each

Figure 37 shows a successful result of the execution of our grammar.
You can see the shortest path from $Start$ to $Goal$ city with length $7 < 10$ : A - G - H with State max=7.