View source for L-system generator

[http://en.wikipedia.org/wiki/L-systems L-systems] are generally known as iterative computational methods used to generate self-similar fractals, usually plants and other biological organisms. Wandora's L-system generator is used to construct [http://en.wikipedia.org/wiki/Graph_%28mathematics%29 graphs] and more specifically [http://en.wikipedia.org/wiki/Topic_maps topic map] graphs. Wandora's L-system generator is divided into two parts: a string generator and a string interpreter. The string generator builds an L-system string using a given initiator and rules and the string interpreter builds a graph out of the created L-system string.

Wandora's L-system generator starts with a menu option '''File > Generate > L-system generator...'''. The menu option opens a dialog with two tabs: '''L-system''' and '''Parser'''. By default the L-system tab is active. The L-system tab is used to enter actual L-system to the string generator. Below is a snapshot of the L-system tab view. The tab contains also a drop-down-selector to select ready-made L-systems. The user can also store his/her own L-system by clicking a '''new''' button. Wandora stores L-systems to the [[Wandora options|options]].


[[Image:L_system.gif|center]]


An L-system contains

* An initiator
* One or more rules

The initiator is first line in the L-system. It is usually an alphabet or a set of alphabets. The initiator initializes the L-system string. For example, the screen capture above has an L-system with initiator '''x'''.

Remaining lines in the L-system are rules. The L-system rules have always two parts: a predecessor and a successor. The L-system rule is executed whenever L-system generated string contains the predecessor. The predecessor is replaced by the successor string during the rule execution. For example, the screen capture L-system above contains a rule where the predecessor is '''x''' and the successor '''a[xx]'''. Wandora assumes the predecessor and the successor are separated with '''-->'''.

L-system execution continues limited time. Each execution step is called an iteration. A text field below the L-system text area contains a number representing the L-system iterations. As the L-system string may grow very rapidly, we suggest you not to use more than 10 iterations unless you are sure about the outcome of the L-system.

Looking at the screen capture above and it's L-system, the initiator string is changed step by step:

 0: x
 1: a[xx]
 2: a[a[xx]a[xx]]
 3: a[a[a[xx]a[xx]]a[a[xx]a[xx]]]
 4: a[a[a[a[xx]a[xx]]a[a[xx]a[xx]]]a[a[a[xx]a[xx]]a[a[xx]a[xx]]]]
 etc.

As you may notice, the string grows very rapidly.

L-system itself carries no interpretation of the generated string. The generated strings are semantic free, you could say. This reflects to Wandora's L-system generator feature too. The L-system string generation is separated from the interpretation. The interpretation is handled by a special L-system string parser that reads the generated string and interprets each token in the string. You can also use the parser independently of the L-system string generation by selecting the Parser tab. You can parse the hand-made L-system string with the parser, for example.

== L-system string interpretation ==

Typically the L-system string is interpreted as a set of turtle commands such as move forward, draw line, and turn left or right. However, such interpretation has an implicit assumption of external environment where you can express ideas of left and right direction. If you think of plain graphs, there is no such external world we could refer. Turtle command "turn left" has no meaning in a plain graph as we have no external coordinate system outside the graph. Wandora interprets the L-system string little different compared to the turtle interpretation. The vocabulary and it's interpretation is explained in the table below.

General principle is that each alphabet in the vocabulary creates a topic i.e. a node in the graph and associates it with some other topics, usually at least the previously created topic. An association is a graph edge in the topic map world. When a topic (excluding named topics) is created, a global variable called ''topic counter'' is increased by one. When L-system string parsing starts, the ''topic counter'' is 0. The ''topic counter'' is used to derive topic's identity. Thus, a topic is merged with an existing topic with the same ''topic counter'' number.

Different parenthesis are used to control graph branching. Branching means that at least the first topic in the branch is associated to the "body". A branch typically ends (closes) somewhere in the string and the graph generation returns to the "body".

Capital alphabets are used to create ''named topics''. The ''named topic'' has strong identity. This means that the ''named topic'' is always same. The ''named topics'' allow you to refer same topic everywhere in the L-system string.

Coloring of associations and topics refers association and topic typing. When we say a topic is colored by '''e''' then the topic is typed by a topic derived from alphabet '''e'''. Same applies to associations. When an association is colored by '''e''' then the association type topic is derived from alphabet '''e'''.


{| border="1" cellpadding="4"
|-
| ''Alphabet(s)''
| ''Interpretation''
|-
| '''a''' 
| Creates a topic and associates it with previously created topic. If no previous topic exists, no association is created.
|-
| '''A-V'''
| Create named topic and associate it with previously created topic. Named topic merges with previously created topic with same name. Unfortunately vocabulary supports only 23 different named topics.
|-
| '''eiouy''' 
| Create a colored topic and associate it with previously created topic using colored association. Colored topic means here that topic is typed. Colored association means here that the association type is different. Notice the set is equal to vowel characters ('''a''' taken out).
|-
| ''':''' followed with any of '''a-zA-Z1-9''' 
| Change global color i.e. topics and associations are colored after this point.
|-
| ''':0''' 
| Reset global color.
|-
| '''('''
| Start sequential block. First topic in the sequential block is associated with the preceding topic.
|- 
| ''')''' 
| Close sequential block. When sequential block is closed next topic will be associated to the topic preceding the block.
|-
| '''[''' 
| Start parallel block. All topics in the parallel block are associated with the preceding topic.
|-
| ''']''' 
| Close parallel block. When block closes all next topics are be associated to the topic preceding the block.
|-
| '''{''' 
| Start cyclic block. First topic in the sequential block is associated with the preceding topic. Last topic in the cycle block is associated with first topic in block. 
|-
| '''}''' 
| Close cyclic block. When block closes all next topics are be associated to the topic preceding the block.
|-
| '''-''' 
| Subtract topic counter by one. The effect is that next topic is merged with previous topic.
|-
| '''+''' 
| Add topic counter by one. The effect is that there is a gap in topic numbering.
|-
| '''0''' 
| Reset topic counter.
|}

Other alphabets have no explicit semantic and are silently passed by parser. Other alphabets, such as '''x''' and '''z''' are usually used as L-system rule predecessors. However, notice the '''y''' alphabet is reserved for colored topic creation.

== Examples ==

Next table illustrates the interpretation of the L-system generated strings. Left column presents the L-system generated string and right column the graph that is created when the string is parsed. In this example we are not interested in the actual L-systems that generate the left column strings. Graph circles represent topics. A number (or letter) in the circle is topic's identity. Lines between the circles represent associations. Notice that same graph can be generated with several different strings. The table doesn't list all possible strings that could generate the right column graph.

{| border="1" cellpadding="4" 
|-
| ''Parsed String''
| ''Generated Graph''
|-
| 
'''aa''' or
'''a(a)''' or
'''a[a]''' or
'''a{a}'''
| 
[[Image:lsystem_aa.gif]]
|-
| 
'''aaa''' or
'''a(aa)''' or
'''a(a(a))'''
| 
[[Image:lsystem_aaa.gif]]
|-
| 
'''a(a)a''' or
'''a[a]a''' or
'''a{a}a'''
| 
[[Image:lsystem_a(a)a.gif]]
|-
| 
'''a(aa)a''' or '''a(a(a))a'''
| 
[[Image:lsystem_a(aa)a.gif]]
|-
| 
'''a(aaa)a''' or
'''a(a(aa))a''' or
'''a(a(a(a)))a'''
| 
[[Image:lsystem_a(aaa)a.gif]]
|-
| 
'''a[aa]a'''
| 
[[Image:lsystem_a_aa_a.gif]]
|-
| 
'''a[aaa]a'''
| 
[[Image:lsystem_a_aaa_a.gif]]
|-
| 
'''a{aa}a'''
| 
[[Image:lsystem_a-aa-a.gif]]
|-
| 
'''a{aaa}a'''
| 
[[Image:lsystem_a-aaa-a.gif]]
|-
| 
'''a{aaaa}a'''
| 
[[Image:lsystem_a-aaaa-a.gif]]
|-
| 
'''a(a(a)a)a''' or '''a(a[aa])a'''
| 
[[Image:lsystem_a(a(a)a)a.gif]]
|-
| 
'''a(aaa)aaa'''
| 
[[Image:lsystem_a(aaa)aaa.gif]]
|-
| 
'''a(aaA)aaA'''
| 
[[Image:lsystem_a(aaA)aaA2.gif]]
|-
| 
'''A(aa++)aaA'''
| 
[[Image:lsystem_A(aa--)aaA.gif]]
|-
| 
'''aaa---a'''
| 
[[Image:lsystem_aaa---a.gif]]
|}

Next images illustrate actual L-systems and equivalent topic map graphs visualized in Wandora. Grey boxes represent topics and lines associations between topics. A table expressing L-system initiator, rules, and number of iterations is next to the graph.

[[Image:lsystem_btree.gif]]

[[Image:lsystem_plant.gif]]

[[Image:lsystem_clover.gif]]

[[Image:lsystem_adder.gif]]

[[Image:lsystem_dandelion.gif]]

[[Image:lsystem_shining_star.gif]]

[[Image:lsystem_lasso_collection.gif]]

== Additional notes ==

* The L-system vocabulary interpretation was an [http://en.wikipedia.org/wiki/Ad_hoc ad hoc] invention. It is likely that the current vocabulary interpretation doesn't cover all possible graphs. In other words there are graphs that can not be generated with this L-system interpretation. Wandora Team welcomes all [http://www.wandora.net/forum/index.php criticism, feedback, and ideas]. Evident limitations are
** The L-system interpretation allows only binary associations. You can't generate hyperedges -- associations with three players, for example.
** The L-system interpretation supports only 23 [A-V] different "static" topics.
* L-system generator creates numbered topics and numbering starts always from 0. Thus, L-systems generates same topics and associations created during previous round. This feature may confuse the user if she tries the L-system generator many times consequently without resetting Wandora's topic maps. To avoid L-system interference the user has to initialize Wandora between L-system generations with '''File > New Project''' option or create new topic map layer for each L-system.
** The user should not see this as a bug but a feature as it allows the user to apply several different L-systems consequently to one topic map.
* It was expressed above that used interpretation of the L-system does not use any external coordinate system to place nodes and edges of the generated graph. Now, watching nicely rendered graph examples above may suggest something very different. Example graphs look carefully rendered. However, the carefully rendered look was achieved using Wandora's [[Graph topic panel]]. The panel has it's own mechanism to unwrap and clear up complex graphs. Although the mechanism results topologically similar graphs, it is very likely that trying out provided example L-systems generates different renderings.