Environmental Engineering Reference
In-Depth Information
sylvatica
L.) which were modelled using an RGG with process-oriented compo-
nents (see Kniemeyer 2008). Another FSPM of this sort will be shown at the end
of this chapter.
RGG are a special case of
graph grammars
. As for L-systems, there exists an
established mathematical theory on graph grammars (Rozenberg 1997). L-Systems
form a special case of RGG, because strings can be interpreted as special graphs with a
linear structure, with edges of a certain, fixed type “successor” between consecutive
symbols. In XL, edges are generally written down in the form “-
edgelabel
-
”, where
“
edgelabel
” specifies the type of the edge. Since the edge type “successor” is so
frequently used, a simple blank symbol is allowed instead of “-successor-
>
>
”. This
convention allows us to write down L-system rules in XL in a familiar manner - and in
fact, all L-system examples shown above were directly taken from XL programmes.
In order to make them readable by an XL compiler (like that included in the software
GroIMP, see
http://www.grogra.de
), one has only to enclose the rules (without the
module declarations) in a surrounding frame of the form
public void run( ) [
]
This construction is necessary because RGG rules in XL can be organized in
several blocks in order to enable a better control of the order of rule application, like
in so-called table L-systems (Rozenberg 1973).
However, RGG have a capacity going far beyond that of L-systems. As an
illustration, Kniemeyer et al. (2004) show a graph transformation rule which
simulates the genetical process of “crossing over”. It cannot be expressed as a
simple L-system rule, but as an RGG rule.
Additional flexibility comes from the possibility offered by XL to derive new
relations between graph nodes from the given ones. For example, the search pattern
a -x-
...
b matches all pairs of nodes (a, b) in the graph (standing, e.g. for plant
organs) which are connected by two consecutive edges of type x and y, respec-
tively, whereas the pattern:
a (-x-
>
-y-
>
)* y
matches all pairs which are connected by an arbitrarily long path consisting of
edges of type x (in mathematics, this kind of relation is called the “reflexive-
transitive hull” of the relation x). Search patterns of this sort can be used in so-
called “graph queries” which, when evoked, give back all subgraphs of the current
structure which are consistent to the search pattern. Queries enable to carry out
calculations on all the results. Queries in XL are enclosed in starred parentheses
(*
...
*) - in fact, the optional “context” part of an RGG rule is also a graph query.
For example, the following expression in XL calculates the total area of all leaves
which are attached to the branching system emerging from a specific node n in a
tree crown:
sum((* n (- -
>
>
)* Leaf *)[area])
)*” denotes the reflexive-transitive hull of the relation “successor”
or “branch”, i.e. all nodes of type “Leaf” which can be reached via a directed path
Here, “(- -
>
