Grammar rules are stored in GraphSynth in a similar
manner to how
graphs are stored. Within the
grammarRule class (under the 1.Representation folder) a rule is comprised of the following main fields:

††††††† public string name;

††††††† public designGraph L;

††††††† public designGraph R;

††††††† public Boolean spanning;

††††††† public Boolean induced;

††††††† public Boolean containsAllGlobalLabels;

††††††† public List<string> recognizeFunctions ;

††††††† public List<string> applyFunctions ;

††††††† public List<embeddingRule> embeddingRules;


The rule contains a simple name and two designGraphs, one representing the left-hand-side, or L (what is used for recognition), and one representing the right-hand-side, or R (what is used for application). It is likely that the rule should have some overlap in the elements that are in L and R. However, these are stored twice as separate elements of both L and R. These elements represent the K or common graph between in the rule and play a crucial role in rule application. This is followed by three Booleans: spanning, induced, containsAllGlobalLabels which are defined as part of the recognition (see Table 1 under Recognition).

Parametric Rule Files

The next two lists represent the names of functions, for C# functions that have been written to add to the recognition or application criteria. These are especially useful in parametric rulesórules that are in some way based on the local variables (stored as doubles) stored in the nodes and arcs of the graph.


Grammar: Saving & Opening

When drafting a rule in GraphSynth, one can access many of these rule properties by invoking the properties window (shown to the right). This is the properties window for the rule named seedBurst1Rule4 (seedBurst1Rule4 .xml in the rules directory). It is a fairly simple rule with one Parametric Recognize Function called isALeafNode and one Parametric Apply Function called distributeTo1NewRoot. When this rule was created, a template for these functions were automatically created in the .cs file called seedBurstParamRules.cs. When GraphSynth creates these templates all Parametric Apply Functions will look like the following:

/* This is APPLY for the rule entitled: swirlRule1 */

public designGraph distributeTo1NewRoot(designGraph Lmapping,
†††††† †††††† †
designGraph host, designGraph Rmapping,
†††††† †††††† †
double[] parameters)


††† /* here is where the code for the APPLY function
†††† * is to be located. Please modify host (or
†††† * located nodes) with the input from parameters. */

††† return host;


This means that one can draft any functions on the resulting host that results after all other rule modifications have occurred (see Application). The Lmapping and Rmapping are needed to identify elements locations within the host. The examples in the rules directory are a good place to start to understand what can be done with this function.

The Parametric Recognize Functions are more restrictive. The template for a parametric recognize rule looks like the following:


/* This is RECOGNIZE for the rule entitled:† */

public double isALeafNode (designGraph L, designGraph host,
†††††† †††††† †
List<node> locatedNodes, List<arc> locatedArcs)


††† /* here is where the code for the RECOGNIZE function
†††† * is to be located. Please remember that returning
†††† * a positive real (double) is equivalent to a
†††† * constraint violation. Zero and negative numbers
†††† * are feasible. */

††† return 0.0;


As the template shows, these functions return a double instead of a Boolean, which may seem to be the more obvious type for whether or not a rule is recognized. Only non-positive-valued real's will qualify as a successful match. This is to meet with negative null form of constraints used in numerical optimization. Constraints are usually written in the form gi(x) 0.0 to comply with penalty function and Karush-Kuhn Tucker conditions. Fortunately, understanding the reasons are not necessary for creating meaningful rules. Just remember that a positive number in NOT a match. Example of these rules can be found in the rules directory.


Embedding Rules

As described in Application, there are certain arc modifications that cannot be represented in the L and R graphs. These free-arc embedding rules are stored in a class under 1.Representation called embeddingRule.cs. When drafting a rule one can specify in the Properties Window (as shown above) how many embedding rules to create for the rule. However, the actual drafting of embedding rule values must be done in XML. Once the rule is saved and opened in an XML editor one will see the following line added to the file:

† <embeddingRules>

††† <embeddingRule>

††††† <freeArcLabel />

††††† <LNodeName />

††††† <neighborNodeLabel />

††††† <RNodeName />

††††† <originalDirection>0</originalDirection>

††††† <newDirection>0</newDirection>

††††† <allowArcDuplication>false</allowArcDuplication>

††† </embeddingRule>

† </embeddingRules>

This means that for the list of embedding rules (<embeddingRules>), there is one free-arc embedding rule (<embeddingRule>) with the following properties. The only field that must be filled in this rule is the RNodeName since that specifies what new node (following the node produced from the Rmapping) are the free-arcs to be connected to. Any number of rules may be created and rules may have many of the same values. Be careful though, the modifications performed by embedding rules are hard to debug!