We consider the seed graph, the grammar rules and the rule sets to provide the designer with the Representation for a particular problem domain. On top of this representation, GraphSynth provides us the basic framework to generate candidate solutions through a recognize, choose and apply cycle shown here. 

The code for this particular generation function is found in the 2.Generation directory under the filename RecognizeChooseApply.cs. This is actually an abstract class and cannot be invoked directly, as a result on must produce an inherited class to use this function. Two such inherited classes are shown in that same directory: chooseViaHumanGui.cs and randomChoose.cs. Mainly these inherited classes answer a difficult question of graph synthesis: how or who will make the decisions to synthesize new graphs?

Once an inherited class is established, a creation of that class (constructor) will be required to populate the fields of the recognize, choose, and apply process. These fields are:

int[] maxNumOfCalls : the number of calls or cycles specified for each rule set. This is an array of length specified by the number of rule sets.
If it is not set, the value of maxRulesToApply will be used.

candidate seed : Often the same seed is used as a starting point with the generation process. That seed is stored here as a global field of the class.

ruleSet[] rulesets : The ruleSet array used to perform the generation process is stored here.

Boolean display : A simple Boolean used for debugging or interactive generation. If true then the host will be re-plotted after each apply action.

After the creation of the generation methods, one can invoke the generation by calling one of the existing RecognizeChooseApply.cs invoked functions:

public candidate generateOneCandidate()
public void runGUIOrRandomTest()
public candidate[] GenerateArrayOfCandidates(int
   numToCandidates)
public List<candidate> GenerateListOfCandidates(int
   numToCandidates)

or by writing your own invoking function in the derived class (see example at bottom of randomChoose.cs).

 

Over the past thirty years, two separate fundamental approaches to graph application have been derived. The two approaches have been distinguished from one another as: algebraic versus algorithmic, gluing versus connecting, or context-sensitive versus context-free and both have been incorporated into GraphSynth. Figure 1 shows an overall flowchart for this application procedure. This flowchart captures in a rigorous way all graph transformations that may occur; addition, subtraction, or modification to nodes, arcs, and labels. The thick dotted line in the figure shows the algorithmic path of the application procedure while the long ‘U’ shaped lines indicate subgraph distinctions, where A Ì B indicates that A is a subgraph of B. The input to application includes the three items on the left of Figure 1. The rule and the L-mapping (or locations) are the result of the previous choose function that results from recognition (see Generation for description). These along with the host graph, G, represent the first elements of what is commonly referred to as the Double-Pushout method, which is discussed in detail in the following subsection. Following the pushout that removes elements from the host (Step 1 in Figure 1); a second pushout adds new elements to the graph (Step 2 in Figure 1). This concludes the traditional algebraic approach to graph transformation; however, for completeness, a third step is implemented to accomplish Free-Arc Embedding of possible dangling arcs. This third step (Step 3 in Figure 1), based on a previous approach referred to as edge-directed Neighborhood Controlled Embedding, is improved upon in the implementation of GraphSynth. It is described in more detail below.

 

The Algebraic Double Pushout Method

In general, the description of grammar rules contains some overlap in the two graphs L and R. This overlap is referred to as K, and indicates what parts of the L-mapping are to be kept through the rule application. Any elements (nodes, arcs, or labels therein) that are to be deleted in this rule transformation are therefore stored in L but not in K. One could view the DPO method as a function:
H=G – (L – R) + (R – L)
where the parts of L that are not in R are first deleted (L-R), followed by the addition of elements in R but not in L (R-L). This method of adding elements via graph transformation is sometimes referred to as the ‘gluing’ method or the context-sensitive method given this approach at adding new elements to a host. One final change that can be made in this part of application is to modify the labels in the K elements. This modification happens in a similar way to the overall rule operation but is applied on a set as opposed to a graph. Within each element in K, we identify the labels that exist when in L that are no longer stated when in R and delete them. This is then followed by adding the new labels that are in R but not in L; the common labels are left alone. In terms of implementation, we represent L and R as independent graphs. As such there is no true intersection graph K that results. What is done to represent the K elements is to require that arcs and nodes with identical ‘names’ in L and R are the same element, when the user constructs a rule. This name tag is separate from labels which are used to describe qualities in the graph. Name is an implementation fix to storing K elements in two separate instances. As a result, the aforementioned modification of K labels can be easily performed. An example DPO rule application is shown below in Figure 2.

 

The Algorithmic Free-Arc Embedding

The second approach to graph application is often referred to as the ‘algorithmic approach’ or the ‘connecting approach.’ In many instances the two approaches are able to perform identical graph modifications, and in general the DPO method is preferred for its ease of representing graph modifications by simple graph subtractions and additions. The algorithmic method is ‘context-free’ which on a low-level relates to the lack of the common or context graph, K, but on a higher-level this means that the rules can be applied in more generic way. Consider the example in Figure 2. The three nodes of the left hand side, L, are removed leaving two dangling arcs and are replaced by two new nodes and a single connecting arc. The two dangling arcs are then connected following a condition that informs the transformation process of where these arcs are connected.

The approach used in GraphSynth is referred to as Free Arc Embedding and takes advantage of our ability to handle dangling arcs. Following the algebraic approach (see Figure 1), we gather the dangling arcs that were connected to the nodes deleted in the first part of DPO and check them with specific embedding conditions of the form:

if free arc ((contains label, freeArcLabel)

AND (was previously connected to the deleted node matched
with the L node, LNodeName)

AND (is currently attached to a neighbor node with label,
neighborNodeLabel))

AND (is in the direction of originalDirection))

then (connect to node, RNodeName in the direction of
newDirection).

The representation of embedding rules is accomplished by simply saving the these variables within a grammar rule. Any of the first four elements of this rule representation may be left blank to specify that the rule is not concerned about a particular quality. This embedding method differs from previous by reconnecting the free arcs as opposed to creating new arcs. An addition of a seventh quality, allowDuplication gives the approach the ability to create more arcs than what is originally contained in the host. Additionally, if none of the first four qualities of the rule are specified, then the rule will be matched to all free arcs (this is seen in the example of Figure 2). Any free arcs that meet no conditional rules are deleted as a final step in creating the new host, H'.

It is important to note that the order of the rules is important. Any combination of embedding rules can be used to identify a free arc. If two rules are recognized with the same free arc only the first one will modify it, as the arc will no longer be ‘free’ after the rule is applied; however, in cases when allowDuplication is set to true, a copy of the free arc will remain for the other rules to operate on. As a result, when a rule duplicates an arc in this way, it does not prevent further rules from being recognizing the free arc.

The act of recognizing when a rule can be applied is to identify a subgraph
within the host that matches with the graph depicted as the left hand side
of the rule (as shown in Figure 1). Within a label rich system, the number
of possible subgraphs reduces drastically. The labels within both the graph
L and graph H in Figure 1 constrain the recognition to a single subgraph
(node 2 and arc 10). However, if all of the labels are removed in L, then
there are 16 possible subgraphs. The corollary that is adopted here is that
the act of matching a node or arc to one in the host is that the labels
must be a subset. In the case of Figure 1, the subgraph is recognized even
though the matching location contains more labels than L.

 

 

 

 

 

Figure 1: The recognition requires that we find the subgraph of the left
hand side (a) of the rule within the host (b). In this example, nodes and
arcs are referred to by the corresponding number, and labels for nodes and
arcs are shown in parentheses.

 

 

 

 

 

 

 

Subgraph Booleans

For creative systems, rules are likely constructed to model or contain
particular heuristics or design rules. A label rich recognition like this
can be interpreted as, “if a state of the design contains all the characteristics
of a particular rule, then that rule is applicable.” However, there are
cases when rules may not be easily represented by subsets of labels. It
is for this reason that we additionally equip each node and arc within the
left hand side graphs with a Boolean, containsAllLocalLabels.
If this Boolean is set to true then we enforce that the set of labels must
be identical in both rule and host. In this case, the rule shown in Figure
1 will not be recognized within the host. If all the labels were removed
in the L graph, we would find only one location (node 5 and arc 14) as opposed
to the 16 discussed above.

It is clear from this example that by setting the label matching as “equal
to” as opposed to subset, the number of recognized location reduces significantly.
In addition to this restriction, there are number of additional Booleans
that can be implemented to better capture the intended rule recognitions.
For each node, one can limit the number of arcs that are connected to it.
In our implementation, a Boolean called strictDegreeMatch
is created. This essentially means that a node in a rule’s L will
match only with a node in the host that has the same number of arcs connecting
to it. In the preceding example of Figure 1 with the labels removed from
L and the strictDegreeMatch set to true,
there are only two locations that are properly matched (node 1 and arc 8,
and node 6 and arc 12).

For the arc we can provide an additional criteria on the direction of
the arc with the Boolean, directionIsEqual.
When this is set to false, we assume that undirected arcs can be matched
with directed arcs or doubly-directed arcs in the host. When set to true,
the Boolean limits matching undirected only with undirected, directed only
with other directed with the same sense, and doubly-directed with doubly-directed.
An additional Boolean related to arcs deals with handling the dangling nature
of arcs. The L in Figure 1, only includes a single node and arc; however,
many approaches to graph theory disallow arcs from having an unspecified
or dangling end. In the development of the methodology and implementation
presented here, both cases are handled. In the examples that have played
out from Figure 3, the missing node at the bottom of L is treated as a wildcard
that matches with any node regardless of its characteristics. If one creates
a rule that seeks to match an arc to a similar dangling arcs in the host,
then the Boolean, nullMeansNull can be set
to true for the arc. This prevent this from matching with arcs that are
defined between two nodes. In the example, this Boolean set to true would
again prevent the rule from recognizing a legitimate subgraph with the host.

Finally, the subgraph recognition ambiguities can result in the graph-wide
Booleans, induced and
spanning.. A spanning subgraph is one that
contains all the nodes of the host graph but not necessarily all the arcs.
Clearly, this results in no recognition in the previous example. When the
induced Boolean is set to true the subgraph is required to be an induced
subgraph within the host. This means that L must contain all arcs that exist
between the recognized nodes in the host. These subgraph Booleans are commonly
accepted as fundamental to graph theory. Graphs can also have labels similar
to those in the nodes and arcs. As a result, we create a final Boolean that
relates to the global labels being a proper subset or equivalent to those
in the host. A final summary of these subgraph Booleans are shown in Table
1. While some of these have existed before in past graph theory literature,
we have expanded the set to include all possible ambiguities in what is
meant by subgraph. Since a graph can be defined in category theory as an
interacting set of sets (e.g. set of labels, sets of arcs, and sets of nodes)
the Booleans allow us to independently define how the subsets are determined
for each of these components.

 

 

 

 

 

 

 

Table 1:
A summary of the subgraph Booleans

Subgraph Boolean	Applies to what aspect of rule	when TRUE…
spanning	graph	host contains an equivalent set of nodes as L
induced	graph	host contains an equivalent set of arcs as L for the recognized set of nodes
containsAllGlobalLabels	graph	host contains an equivalent set of global labels as L
strictDegreeMatch	node	host node contains an equivalent set of arcs connected to it as L node (nodes have same degree)
containsAllLocalLabels	node	host node contains an equivalent set of labels as L node
containsAllLocalLabels	arc	host arc contains an equivalent set of labels as L arc
directionIsEqual	arc	host arc has equivalent direction characteristics as L arc
nullMeansNull	arc	host arc must be equivalently unconnected at ends as the L arc

 

 

Recognition Procedure

On the most general level this recognition takes two inputs: the L of
a rule, and the host graph. What is expected as a result is a list of subgraphs
where L is found in the host. For a particular rule and host, there may
be no subgraph, one subgraph, or many subgraphs. These resulting subgraphs
are often referred to as how L is mapped into the host. This becomes an
important consideration for the

application of a rule.

The approach developed in our implementation is a recursive search starting
with a single node in L. The first node in L is checked to see if it matches
with each of the nodes in the host. For those in which it is a successful
match, a modified depth-first-search (DFS) is invoked from each matching
node within the host. As creators of the grammar rules, one can impact the
efficiency of the recognition process by altering the order in which the
nodes are presented. The computational structure for a graph stores the
set of nodes as a list; by placing the most restrictive node (the node that
is hardest to match) first in the list of nodes one can eliminate wasted
search that would occur if a less restricted node is presented first. An
example of this is shown in Figure 2. The node I in L is more restrictive
than node III and the order of expansion is shown in Figure 2a and b. The
depth-first-search proves to be a more efficient approach to recognition
both in computational speed and memory.

An additional item to note in these mappings is that locations including
the same nodes and arcs are found multiple times. This is because our recognize-choose-apply
requires that we uniquely match each node and arc to one in the host. This
becomes more apparent in the discussion of rule application since the rule
essentially includes individual instructions for each of the elements matched
to the L graph.

 

 

 

Grammar rules are organized into sets, simply called rule sets. These are stored in compact XML files that contain references to each of the grammar rules in the set. All of the details of the rule set can be configured through GraphSynth’s ruleSetDisplay — there is no need to open a ruleset’s XML in an editor (I have only ever done it out of curiosity!).

The top of the pane is a list of the rules added to set. Any number of rules may be added to a rule set by clicking the add rule button. Once rules are in the set their order can be rearranged or they can be subsequently deleted. Along the bottom are three buttons that indicates what to do with the checked rules listed above. The checked rules are deleted by the “del” button, or moved up or down (“dn”) in the list.

Following the list of rules is a list of important rule set properties. Similar to graphs and grammar rules the name will simply be inherited from the filename, and is not internally used within GraphSynth. The next is a property called “triggerRule #.” A trigger rule is one that when invoked during the generation process causes a particular action to occur. Currently, only one triggerRule can be set per rule set. If there is no intention to use the trigger rule,  then the item should be set to –1. The triggerRule # corresponds to the rule # shown in the top pane.

The next seven properties deal with how the rule set behaves during Generation (It is recommended that this section is well understood before proceeding with this description). The “choiceMethod” is set to either Automatic or Design. An automatic rule set is one that will invoke the rule once it is recognized. This is the case in the example to the right (the example seedBurstRuleSet in the rules directory). When a rule set is set to Automatic, the random tests and user choose tests under the design drop down will not function. This is because the rules fire immediately, skipping the choose part of the generation cycle. Given the methodical approach followed by recognize, we will get the same resulting graph every time with an Automatic ruleset. It will first look for valid locations of the first rule and searching in the host from the first listed nodes on down. This continues for the remaining rules. The important thing to note in automatic rule sets is that latter rules will not be invoked unless all previous rules were unrecognized. This is illustrated well in the seedBurst example. Alternatively, if one knows that their rule set is confluent, then an automatic rule set will work as expected.

“Interim Candidates are” & “Final Candidates are” are properties developed to support latter automated searching of graphs. Often grammars rule sets are created so that only after all rules are invoked is a feasible solution achieved. For such rule sets, we would indicate that Interim Candidates are Developing and Final Candidates are Feasible—as is the case for the seedBurst example shown above. However, in other examples such as the fun swirlSeed example. We set both to Feasible. Users may want to create choosing methods that check these qualities to know if a candidate is complete and subsequent rules are simply modifying it, or if the candidate is Developing towards a Feasible candidate.

The next five properties correspond to the five ways that the Recognize→Choose→Apply generation cycle may end (see Generation). These each can be set to one of the five actions:
Stop : simply end the generation process,
Loop : restart Recognize→Choose→Apply,
  GoToPrevious : go to the previous rule set stored in the array Program.rulesets[],
  GoToNext : go to the next rule set,
  GoToRuleSet#n : go to rule set #n.

As a result of setting these five properties to any of these five actions, we can greatly control how the rule sets execute. Note that there may be any number of rule sets within a particular synthesis of a graph. We have noticed on several occasions that grammar rule are stored in sets that perform different actions within the overall synthesis. An example of multiple rule sets can be found in the Routes example (RouteGetToSpanningRuleSet.xml and RouteGetToCompleteRuleSet.xml in the rules directory). After the first rule set has run out of rules, then we know that we have created a spanning tree of the nodes in the seed graph (citiesDefaultSeedGraph.xml). Since “NoRules” is set to GoToNext, the next rule set is invoked to add additional routes between the cities.

Finally, the rule set has properties that list the filenames for recognize or apply parametric functions. These need to be established prior to creating templates for functions in the grammar rule property window. As is shown in the examples, a “.cs” file has been created for each ruleset. Each of these files contains all the functions used by that ruleset. This is not enforced by GraphSynth though. One may have multiple “.cs” files for a ruleset or multiple rulesets referencing the same source file.

Note: Because rule sets are stored in a fixed array
(Program.rulesets[]), please specify the number in advance in the settings (GraphSynthSettings.config).

Methodology Overview

Graph transformation systems, or graph grammars, are a branch of graph theory research that rigorously defines mathematical operations such as addition and intersection in graphs. Mathematicians have developed the foundations of this research, and engineering design researchers have appropriated the concept to formalize the creation of complex engineering systems. Electric circuits, truss structures, and chemical processes are just a few of the artifacts of engineering design that are easily represented by graphs. When viewing the artifact as a graph constructed from an initial simpler graph that describes the problem, one needs to develop a set of rules to capture the valid transformations that can occur. The grammar rules, organized into rule sets are then subject to a generation process. This process has three step steps: recognize, choose, and apply as illustrated in Figure 1.
 

Figure 1: For creative systems, we consider three distinct steps of 1) recognizing what rules are applicable, 2) choosing one of these rules to apply, and 3) the application of the rule which involves a graph transformation of the host to a newly synthesized state.

 

Representation

Rules and graphs in GraphSynth are stored in an XML format and are loaded into the program and instantiated as define graph object: nodes and arcs. Grammar rules are essentially constructed of two elements: application conditions (that, if met, are valid transitions in the state-space tree), and application instructions (how the graph is to be altered). These two elements are each represented as a graph: the conditional, recognition, or left-hand-side graph; and the application or right-hand-side graph. Figure 2 represents several rules created with GraphSynth thus far.

For more detail on recognition,
click here.

For more detail on application,
click here.

 

                                                                                                                                 Figure 2: Two example rules created with
                                                                                                                                               GraphSynth: a) this first rule is from sheet metal research, where a patch of sheet metal is removed by a side notching operation. In addition to drawing the graph in GraphSynth, the designer can also change important parameters within the properties window. b) The second rule is created for the research on NSF Grant IIS-0307665 (Creating a Computational Theory for Conceptual Design) wherein function structure elements are replaced with real components.

A rule set is essentially a set of rules that capture the space for a particular design problem. In implementing rules, the researchers have discovered that many applications require more than one rule set . Furthermore, when the number of rules becomes large it is easy to create inconsistencies amongst the rules. Therefore we allow for multiple rule-sets to capture the entire space of solutions. Figure 3 represents the graphical view of a rule set. These are described in more detail here.
 

The Big Picture

Figure 3: An example Rule-Set from the sheet-metal research. In addition, to the rules contained within a rule-set, there are additional properties such as how the rule-set terminates, and what additional rule-sets are to be invoked.

Within the source files of GraphSynth, you will find the details for classes like grammarRule.cs and ruleSet.cs are stored in the project named “Representation”. The other main projects are :  “Generation”, “GraphLayout”, “Evaluation”, “Guidance”, “Application_UI_and_Search.” This final one, is the main one, the ".exe" is found in its bin directory. The other projects compile to DLL's. The authors of GraphSynth theorize that the division of representation, generation, evaluation, and guidance is useful in almost all computational synthesis methods. This generalization can be captured by the flowchart shown in Figure 4.

Figure 4: The generic flowchart for Computational synthesis has four basic divisions: a representation of the design space, a method for generating new solutions, a method for evaluating solutions, and a method for guiding the search process.  

The representation is formulated by the programmer of the computational design method to capture the forms or attributes of the design space. For example, in genetic algorithms, the representation is usually a bit-string that represents the key decision variables in the process. Using this representation, candidate solutions are generated in the generation task. In genetic algorithms, this is done by mutating and “crossing over” existing or parent candidates. Each generated candidate is evaluated in the evaluation task to determine how well it meets the objectives and constraints of the design problem. Based on the objectives calculated for the candidates a guidance strategy is implemented to inform the search process of how to find better solutions in the subsequent iterations. In genetic algorithms, this is the “survival of the fittest” tournament selection where candidates with inferior fitness values are removed from the search process.

                                                              Other than these in GraphSynth, the
                                                              project named GraphLayout contains
                                                              custom layout algorithms that the
                                                              researcher may write for their
 resulting graphs. Within the Application_UI_and_Search project, there is folder called MainFormsAndSettings which include start up routines, and the display forms. The one file searchProcess.cs not included in the directory is likely where a researcher would write their main search routine. In fact, in each project the ".cs" file not included in a subdirectory is open to modification. These are searchProcess.cs, inheritedGraphClasses.cs, graphLayout.cs,  GetToOptimum.cs, and EvaluateSwirls.cs. The latter two or for the facetious example presented in the searchProcess.cs file. These should be studied and then deleted. They merely offer an example of how the projects are intended to  interact. For a particular application, one would create their own evaluation methods, and thus there is no general methods that can be provided for this. For guidance strategies, there are currently no such methods for graph synthesis. Our current research is developing a number of these. In the meantime, GraphSynth can be use to synthesize graphs, either through user-guided or random decisions. Future updates will include guidance methods, and thus a full optimization procedure can be made to design optimal graph topologies. Earlier, a description of the basic representation classes was provided. In addition to GraphSynth also provides a clear way that graphs are created through a main generation class. The details of this are described here.

Opening & Saving

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
recognizeFunctions;

public List
applyFunctions;

public List
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.

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:

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 g_i(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 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!

The Design drop down menu in GraphSynth provides functions to test and synthesize new graphs from the grammar rule sets described in earlier pages (graphs, grammars, rule sets). Firstly, the pane has commands to set the active seed and the first three active rule sets. These can also be set in the GraphSynthSettings.config file, through the settings drop-down under File,  so that they are

established on beginning the program (this proves to be a great time-saver!). The GUI will only allow one to assign the first three rule sets; however, if you want more, you will need to make the assignments in GraphSynthSettings.config or even during Program.runSearchProcess().

This is followed by the “Run Search Process” item, which is the main entry point for a search process that one may implement (more on this in a second). The bottom three items allow for the testing or rules, rule sets, and seeds. The “Recognize→User Choose→Apply” item invokes a dialog to choose the rules by hand. Within the options presented in that dialog, one can double-click a location to see what subgraph the rule is applying to. The “Recognize→Random Choose→Apply” item will continuously call random options on the seed until the process stops (stops by encountering a “Stop” in one of the 5 generation exits). Additionally the gray box that is labeled “#steps” can be changed to a set a integers that will be assigned to the generation cycle limits for each rule set (see int[] maxNumOfCalls). For example by replacing “#steps” with “4, 5 12”, the generation process will be invoked with set maxNumOfCalls to [4, 5, 12] (most common separators such as comma and space can be used).

Search Process Controller

When any of these lower items are clicked, a small controller window appears (often it is hidden for user and random testing). The controller allows one to change how the search process is executing. The snapshot to the right was taken while the process was executing. Notice that the “Play” button is disabled since the process is already in operation. The process can be paused, stopped , or aborted from this point. Pressing the “Stop” button will send a request to the process. This is to allow the process to end and still retain useful results. It will not always function if the search process is using the computational resources elsewhere. Thus as a last resort, the “Abort” button will attempt to kill the thread that the search process is running on.

Figure 2: The Search Process Controller allows on to dynamically control aspects of the search process. It is inspired by the transport bar of computer music applications.

In addition to these button, there are three displays that show pertinent information about the process. The time is implemented as part of the controller; it ‘pings’ the thread the search process is on in specific intervals. The rate at which it pings is based on the verbosity setting (described below). The top two displays shown the iterations and a miscellaneous field. These are set in the search process by setting the iteration and miscObject properties of the main Program.cs. At the bottom one can set the priority and verbosity for the search process. The computational processes in GraphSynth run on separate threads, and a thread can be given a priority over other threads. Set this high if you want to speed up the process but do not mind it slowly down other processes including the main thread (thus making GraphSynth appear as if it has locked up!). The verbosity is a highly useful UI that allows the user to adjust how much text is being output by the process. One is encouraged to implement many SearchIO.output statements in a search process to provide information about the progress of a long operation. However, such commands can greatly slow down the processing. By dynamically setting how verbose we want the search process to be, we can get the information we want when we need it.

The SearchIO.output function can be invoked with an object (usually a string) to print and a verbosity limit, which is an integer from 0 to 4. If the verbosity limit is set to 0, then the object will be printed all the time even for verbosity set to “lowest.” If it is set to 4, then it will only print when verbosity is set to “highest.”

Writing a Custom Search Process

Figure 3: The Representation is accomplished by the seed, and rule set; and the Generation by the R→C→A cycle. What remains in the search process is some method to evaluate the quality of candidate graphs (classes and functions to be stored in Evaluation), and methods to learn from these results to improve the next generation (classes and functions to be stored in Guidance).  

As discussed in the introduction, one may want to automate the creation of candidate solutions. This custom code can be written in under the function Program.runSearchProcess() in the file searchProcess.cs. In fact, any C# code can be written here. One may want to invoke functions or classes from another Visual Studio project, or invoke additionally GUI forms.   In the example code, the swirl seed and rule set are loaded (which encapsulates the representation) , and we create the generate, evaluate and guide methods for the search process: 

Generation.randomChoose GenerationApproach
      = new Generation.randomChoose
         (Program.seed, Program.rulesets,
          new int[1] { 50 }, false);
Evaluation.EvaluateSwirls EvaluationApproach
      = new Evaluation.EvaluateSwirls(); Guidance.DoNothingButDisplay GuidanceApproach
      = newGuidance.DoNothingButDisplay();

The initiation of these routines is done at the begin-
ning of the process in an attempt to make GraphSynth
modular for a wide range of applications. Throughout the
search process, one can take advantage of a number of fields
in the Program and SearchIO cclasses. These are listed below for your reference:

Program.settings : The class globalSettings is in the Application_UI_and_Search directory. These values are loaded in from the GraphSynthSettings.config file.

Program.mainForm :   this is the reference to the mainForm - the top/largest GraphSynth Window. It may be difficult to reference objects from a search process, as Visual Studio will view this as a cross threading operation (which apparently is a bad thing. See the SafeInvokeHelper class in Represenation→XMLandIO for a solution)

Program.seed : This is the seed graph (of class designGraph) indicated by the "Set Active as Seed" drop-down on the Design menu item or through the settings. It represents the top of the search tree.

Program.rulesets : An array of class ruleSet of length Program.settings.numOfRuleSets. These can be set in the same manner as Program.seed.

(The following can be called from either static class SearchIO or Program. Anything written in the searchProcess.cs file will likely already be in the Program class and the property may be reached without specifying the class. However, if you are in another project (i.e. within Evaluate) you will need to use SearchIO prefix, as you will not be able to see the Program class.)

SearchIO.output or Program.output : Use the various overloads of this statement to print messages to the sidebar text in the main form of GraphSynth. While a verbosityLimit is not mandatory, it is a "nice to have", take the time to put something here.

SearchIO.processNum or Program.processNum : A read-only integer that simply lists what search process one is currently on. Not really that useful, during search process. The integer simply increments for each new search started in a single run of GraphSynth.

SearchIO.terminateRequest or Program.terminateRequest : A read-only Boolean that indicates true when the user has clicked the stop button on the SearchProcessController.

SearchIO.timeInterval or Program.timeInterval : A read-only TimeSpan (a fundamental C# class)object that indicates how long the search has been going on.

SearchIO.iteration or Program.iteration : The number of iterations that have occured in the process. It can be read or set using this. The SearchProcessController will reflect the value in the first box. NOTE: Setting this value through Program.iteration causes an immediate update of the SearchProcessController. This is either a good thing or a bad thing. You will see immediately when the iteration changes, but if it is happening a lot then it may slow down your process.

SearchIO.miscObject or Program.miscObject: Any object that the researcher wants to store. It will be converted to a string and shown in the SearchProcessController.  NOTE: Setting this value through Program.miscObject causes an immediate update of the SearchProcessController. This is either a good thing or a bad thing. You will see immediately when the iteration changes, but if it is happening a lot then it may slow down your process.

Graphs are stored in GraphSynth as designGraph.cs. The “design” keyword is to distinguish it from other types that may be used within larger implementations. For example, in GraphSynth an open source library known as Netron is used for visualization. This compiled project (as a .dll) contains it’s own definition for graph. On opening designGraph.cs (under the 1.Representation folder), we see the following:

public partial class designGraph
   public string name;
   public List<string> globalLabels;
   public List < double > globalVariables;
   public List<node> nodes = new List<node>();

   public List<arc> arcs = new List<arc>();

The graph contains a name, labels (which are any number of strings), and variables (a list of any number of double-real's). Additionally, there are two lists: one for arcs and one for nodes. This is a “partial” description of the designGraph class, the rest is stored in the XMLandIO directory. The classes for arc and node are also fairly straightforward. Note that each of these contains references to the connecting elements (to and from in arc point to the two nodes connected to the arc; and arcsTo, arcsFrom, and arcs in node reference connecting arcs).

One can freely draw graphs in GraphSynth by clicking File→New→Graph or typing Ctrl+N. A small empty box appears for you to add nodes, arcs and their labels. There are five node shapes. These can be added by right-clicking and scrolling to “Basic Shapes” or by typing Ctrl+1, Ctrl+2, Ctrl+3, Ctrl+4, Ctrl+5, Ctrl+6, or Ctrl+7. Each of these shapes has one or more connection points. By hovering the mouse over a connection point, one and click-and-drag arcs between shapes. By double-clicking an arc or node, or clicking Properties from the right-click menu, one can access various properties of the element.

 

Figure 1: Creating a new graph in GraphSynth is accomplished by adding new nodes (with right-click or Ctrl+#), dragging arcs into places, and adjusting properties via the Properties Window.

 

 

 

 

 

 

 

 

 

 
 

Graphs like all other GraphSynth elements are stored as XML files. These files can be opened in a text editor and altered as well. The example graph in figure one is saved as the following:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 
 

Graphs like all other GraphSynth elements are stored as XML files. These files can be opened in a text editor and altered as well. The example graph in figure one is saved as the following:

Inherited Types

Inherited types can be created for nodes and arcs so that applications requiring more descriptive objects for nodes and arcs can be used. Note that in the XML, the second node is qualified by the vertex type. As an example of inherited classes, a basic implementation of vertex and edge are presented in the file, inheritedGeometryClasses.cs. Once these are created and properly compiled in GraphSynth, the classes can be placed in the Properties Window under the nodeType or arcType tags. Additionally, the types can be used in the creation of rules. If a rule is made for vertices and edges it will only be recognized on graphs that contain such classes.