Here is a screencast:
And here is the executable jar.
The underlying hyperedge replacement grammar is very straightforward and close to the textual lambda grammar:
Showing posts with label gratra. Show all posts
Showing posts with label gratra. Show all posts
July 18, 2009
Alligator Eggs (for the last time)
Now I have also constructed an editor for alligator eggs. This editor is different from Torsten's editor with the nice animation discussed some days ago. My editor provides syntax-based user assistance instead, i.e. the user gets help in creating syntactically correct alligator eggs expressions. Whereas Torsten's editor has been created with DiaMeta (syntax defined by a class diagram), my approach relies on the DiaGen framework (syntax defined by a graph grammar).
Here is a screencast:
And here is the executable jar.
The underlying hyperedge replacement grammar is very straightforward and close to the textual lambda grammar:
Here is a screencast:
And here is the executable jar.
The underlying hyperedge replacement grammar is very straightforward and close to the textual lambda grammar:
July 15, 2009
Business Process Models
In the last weeks I have developed an editor for business process models with syntax-based user assistance as described in previous blog posts. A screencast of this editor is shown below:
The editor is provided for download as an executable jar.
Concepts and realization are described in S. Mazanek, M. Minas. Business Process Models as a Showcase for Syntax-based Assistance in Diagram Editors. Appears in Proc. of the ACM/IEEE 12th International Conference on Model Driven Engineering Languages and Systems (MODELS 2009), 2009. The original publication will be available at www.springerlink.com.
The editor is provided for download as an executable jar.
Concepts and realization are described in S. Mazanek, M. Minas. Business Process Models as a Showcase for Syntax-based Assistance in Diagram Editors. Appears in Proc. of the ACM/IEEE 12th International Conference on Model Driven Engineering Languages and Systems (MODELS 2009), 2009. The original publication will be available at www.springerlink.com.
November 18, 2008
Graph Transformation Day Bremen
Directly after the World Usability Day in Dresden I attended the Graph Transformation Day in Bremen. Here, I gave a talk about the generation of correctness-preserving editing operations for diagram editors. More on this later...
The other talks have been given by my supervisor Prof. Mark Minas (about using triple graph grammars for analysis in diagram editors), Dr. Rubino Geiß, the architect of the GrGen graph transformation engine (and indeed his talk was about the implementation and application of GrGen), and finally Edgar Jakumeit, who described the realization of recursive matching rules for GrGen. I have found these recursive "star" rules particularly interesting, because they actually allow to write parsers with GrGen in a declarative style. In a sense, this is quite similar to my approach to graph parsing via combinators.
It was a nice workshop. I learned a lot about the GrGen system. In particular I now have an idea how they managed to build the fastest (at least in quite some cases) graph transformation tool in the wild. Thank you Berthold for organizing this...
The other talks have been given by my supervisor Prof. Mark Minas (about using triple graph grammars for analysis in diagram editors), Dr. Rubino Geiß, the architect of the GrGen graph transformation engine (and indeed his talk was about the implementation and application of GrGen), and finally Edgar Jakumeit, who described the realization of recursive matching rules for GrGen. I have found these recursive "star" rules particularly interesting, because they actually allow to write parsers with GrGen in a declarative style. In a sense, this is quite similar to my approach to graph parsing via combinators.
It was a nice workshop. I learned a lot about the GrGen system. In particular I now have an idea how they managed to build the fastest (at least in quite some cases) graph transformation tool in the wild. Thank you Berthold for organizing this...
July 14, 2008
Logic gates
In previous posts I already have discussed several visual languages like VEX, Trees or ER diagrams. These languages have in common that all of them are used by computer scientists. Of course, visual languages also exist in other domains (in fact, visual notations are much older than computers).
In this post I show an editor for a language mainly used by electrical engineers: Logic gates. This is a visual notation for logic expressions that can be used in the domain of circuit design. Expression languages normally are context-free (although often some kind of sharing is used that cannot be described in a context-free way).
Again my approach to diagram completion is applicable, so we get a powerful editor for logical expressions. Here is a screencast demonstrating its use:
I also provide this screencast at an extra site, if this one is two small. You can also download this logic editor as an executable jar (however, keep in mind that this is still a research prototype).
Finally, let me admit that in the last time the most posts have been related to my own approach. I hope you forgive me this way too restricted focus. I will soon attend ICGT and VL/HCC conferences and the LED workshop, where I surely get inspiration for other interesting topics. You might also consider suggesting topics you are interested in for discussion. Of course, if you want to write something about a fancy tool, I gladly publish your description here as a guest contribution.
In this post I show an editor for a language mainly used by electrical engineers: Logic gates. This is a visual notation for logic expressions that can be used in the domain of circuit design. Expression languages normally are context-free (although often some kind of sharing is used that cannot be described in a context-free way).
Again my approach to diagram completion is applicable, so we get a powerful editor for logical expressions. Here is a screencast demonstrating its use:
I also provide this screencast at an extra site, if this one is two small. You can also download this logic editor as an executable jar (however, keep in mind that this is still a research prototype).
Finally, let me admit that in the last time the most posts have been related to my own approach. I hope you forgive me this way too restricted focus. I will soon attend ICGT and VL/HCC conferences and the LED workshop, where I surely get inspiration for other interesting topics. You might also consider suggesting topics you are interested in for discussion. Of course, if you want to write something about a fancy tool, I gladly publish your description here as a guest contribution.
July 01, 2008
Diagram Completion
Recently I have been working on an approach to diagram completion. This kind of assistance helps users in correcting and extending diagrams. That way they can learn new languages much more easily. Furthermore, the construction of complex diagrams is also greatly simplified.
Following my approach, completions are computed on the abstract syntax level with respect to a hyperedge replacement grammar. Thereafter, they are embedded into the diagram by the layout engine. The details are provided in the papers given below.
For motivation I provide a screencast that shows how diagram completion actually has been realized in the DiaGen system. I also provide this screencast at an extra site, if this one is two small:
I also provide this editor for Nassi-Shneiderman diagrams as an executable jar.
If you are interested you might want to attend VL/HCC 2008 where I will give a talk about the overall approach. (If you are not interested in this you should join the conference anyhow. Early registration is still possible :-))
Further reading:
Following my approach, completions are computed on the abstract syntax level with respect to a hyperedge replacement grammar. Thereafter, they are embedded into the diagram by the layout engine. The details are provided in the papers given below.
For motivation I provide a screencast that shows how diagram completion actually has been realized in the DiaGen system. I also provide this screencast at an extra site, if this one is two small:
I also provide this editor for Nassi-Shneiderman diagrams as an executable jar.
If you are interested you might want to attend VL/HCC 2008 where I will give a talk about the overall approach. (If you are not interested in this you should join the conference anyhow. Early registration is still possible :-))
Further reading:
- S. Mazanek, S. Maier, M. Minas. Auto-completion for Diagram Editors based on Graph Grammars. Appears in Proc. of the 2008 IEEE Symposium on Visual Languages and Human-Centric Computing (VL/HCC 2008), 2008. IEEE Computer Society Press.
- S. Mazanek, S. Maier, M. Minas. An Algorithm for Hypergraph Completion according to Hyperedge Replacement Grammars. Appears in Proc. of the 4th International Conference on Graph Transformation (ICGT 2008), 2008. LNCS.
April 27, 2008
Sierpinski Triangles
I have already introduced my approach to graph parsing via Graph Parser Combinators on this blog recently. This time I provide a nice sample parser; at RTA I will present the concepts and how the used framework can actually be realized in the functional-logic programming language Curry.
The example I am going to discuss are Sierpinski triangles. This graph language is particularly interesting for several reasons. First of all, Sierpinski triangles are beautiful thanks to their self-similarity. Second, they can be described by a hyperedge replacement grammar as shown in the image below. And finally, depending on the generation, Sierpinski triangles grow exponentially in size making them an ideal candidate for tool benchmarks (see Taentzer et al. '08).
Note that the given grammar does not ensure that only regular Sierpinski triangles are generated. For instance, the graph shown below is also a member of its language. Regularity can be enforced by using a parallel replacement mechanism or control structures, though (see Habel, Kreowski '87).
Let's see how we can map this grammar to a parser using our framework:
The actual mapping is described in the RTA paper, but you will probably have no difficulties figuring out how it works. Note that inner nodes of a production are guessed using free variables. The regularity is ensured by a parameter depth. As a parser these functions are not very interesting, since parsing can't be done efficiently. However, due to the logic nature of the framework, it can be directly used for the generation of Sierpinski triangles. Compared to other tools (see Taentzer et al. '08) this generation even is reasonably efficient. For instance, we have generated a Sierpinski triangle of generation 11 with nearly 200.000 edges in about a minute.
Further reading:
The example I am going to discuss are Sierpinski triangles. This graph language is particularly interesting for several reasons. First of all, Sierpinski triangles are beautiful thanks to their self-similarity. Second, they can be described by a hyperedge replacement grammar as shown in the image below. And finally, depending on the generation, Sierpinski triangles grow exponentially in size making them an ideal candidate for tool benchmarks (see Taentzer et al. '08).
Note that the given grammar does not ensure that only regular Sierpinski triangles are generated. For instance, the graph shown below is also a member of its language. Regularity can be enforced by using a parallel replacement mechanism or control structures, though (see Habel, Kreowski '87).
Let's see how we can map this grammar to a parser using our framework:
s (Succ depth) (n1,n2,n3) = s depth (n1,n4,n5) *>
s depth (n4,n2,n6) *>
s depth (n5,n6,n3)
where n4,n5,n6 free
s One (n1,n2,n3) = edge ("line",[n1,n2]) *>
edge ("line",[n2,n3]) *>
edge ("line",[n3,n1])
sierpinski = s depth (n1,n2,n3)
where depth,n1,n2,n3 free
The actual mapping is described in the RTA paper, but you will probably have no difficulties figuring out how it works. Note that inner nodes of a production are guessed using free variables. The regularity is ensured by a parameter depth. As a parser these functions are not very interesting, since parsing can't be done efficiently. However, due to the logic nature of the framework, it can be directly used for the generation of Sierpinski triangles. Compared to other tools (see Taentzer et al. '08) this generation even is reasonably efficient. For instance, we have generated a Sierpinski triangle of generation 11 with nearly 200.000 edges in about a minute.
Further reading:
- Sierpinski Triangle for the AGTIVE 2007 Tool Contest
- G. Taentzer et al., Generation of Sierpinski triangles: A case study for graph transformation tools. In: Applications of Graph Transformations with Industrial Relevance AGTIVE ’07 (eds.: A. Schürr, M. Nagl, A. Zündorf), International Workshop Kassel, Oct. 10-12, 2007, LNCS, Springer, 2008
- A. Habel, H.-J. Kreowski, Pretty Patterns Produced by Hyperedge Replacement, Proceedings of the International Workshop on Graph-Theoretic Concepts in Computer Science, LNCS, Springer, 1987
- S. Mazanek, M. Minas, Functional-logic Graph Parser Combinators. To appear in Proceedings of 19th International Conference on Rewriting Techniques and Applications (RTA 2008), LNCS, Springer, 2008
April 22, 2008
Fujaba and Story Driven Modeling
Let's continue talk about our practical on graph and model transformation. In fact, it is already finished, but unfortunately I did not managed to write about the other stages in time. Remember, that in the first stage a UML class diagram editor had to be developed by the student teams using different meta-CASE-tools. The second stage, in contrast, was focused on transformations. The students had to deal with the simulation of finite state machines and pushdown automata using different research tools, namely AToM3, Tiger and Fujaba. At the end, all teams presented quite appealing solutions.
Fortunately, a student of the Fujaba-group, Thore Backen, has been willing to provide us a summary of his insights about the practical work with Fujaba:
In the second stage of our practical on graph and model transformation our group of three students had the objective to produce the simulation of deterministic as well as nondeterministic finite automata using Fujaba.
At first we needed quite some time (approx. 15 h) of practice to get used to Fujaba. To be honest we had some trouble deciding which version to use for our task. In the end we chose the Fujaba Tool Suite Version 4.3.2. The main reason why we chose this version over the more up-to-date version 5.0.4 was the easy-to-use already integrated Dynamic Object Browsing System (DOBS) in the older version. Since we wanted to use DOBS to simulate our finite automata, the outsourced eDOBS (in Fujaba 5) needing Eclipse did not offer any obvious advantages.
As usual, our first step has been the development of a model, i.e., a class diagram of our application domain (click image to enlarge):
The dynamic behavior of a system then can be specified via so-called story patterns. For instance, the story diagram for the firing of a deterministic finite state machine is shown in the screenshot below:
After getting used to modeling with story patterns, which by the way presented itself to be quite intuitional, we learned that simple, figurative designs produced powerful code. After all, we did not write one line of code ourselves throughout the whole phase of the practical. Having needed adequate time to adjust to a new way of thinking, i.e. modeling, Fujaba enabled us for the rapid production of a stable solution to our problem.
Although allowing us to solve our task conveniently, there were some drawbacks working with Fujaba as well. The integrated diagram editor was sometimes hard to use, e.g., the handles on associations were too small to move them comfortably and the automatic layout often scrambled diagrams even more rather than clarifying them. Manual adaption of the generated code, although not needed in the end, was not even possible. Furthermore, the integrated versioning support CoObRA did not work at all on our systems. Due to the fact that diagrams grow rather quickly utilizing story driven modeling we believe that the use of Fujaba is limited to small or medium-sized projects.
In summary, Fujaba offered us a quick, well visualized way to implement the simulation of finite automata. The simulation of these automata using the integrated DOBS is more practical than beautiful, but proved to be sufficient for our purposes.
Fortunately, a student of the Fujaba-group, Thore Backen, has been willing to provide us a summary of his insights about the practical work with Fujaba:
In the second stage of our practical on graph and model transformation our group of three students had the objective to produce the simulation of deterministic as well as nondeterministic finite automata using Fujaba.
At first we needed quite some time (approx. 15 h) of practice to get used to Fujaba. To be honest we had some trouble deciding which version to use for our task. In the end we chose the Fujaba Tool Suite Version 4.3.2. The main reason why we chose this version over the more up-to-date version 5.0.4 was the easy-to-use already integrated Dynamic Object Browsing System (DOBS) in the older version. Since we wanted to use DOBS to simulate our finite automata, the outsourced eDOBS (in Fujaba 5) needing Eclipse did not offer any obvious advantages.
As usual, our first step has been the development of a model, i.e., a class diagram of our application domain (click image to enlarge):
The dynamic behavior of a system then can be specified via so-called story patterns. For instance, the story diagram for the firing of a deterministic finite state machine is shown in the screenshot below:
After getting used to modeling with story patterns, which by the way presented itself to be quite intuitional, we learned that simple, figurative designs produced powerful code. After all, we did not write one line of code ourselves throughout the whole phase of the practical. Having needed adequate time to adjust to a new way of thinking, i.e. modeling, Fujaba enabled us for the rapid production of a stable solution to our problem.
Although allowing us to solve our task conveniently, there were some drawbacks working with Fujaba as well. The integrated diagram editor was sometimes hard to use, e.g., the handles on associations were too small to move them comfortably and the automatic layout often scrambled diagrams even more rather than clarifying them. Manual adaption of the generated code, although not needed in the end, was not even possible. Furthermore, the integrated versioning support CoObRA did not work at all on our systems. Due to the fact that diagrams grow rather quickly utilizing story driven modeling we believe that the use of Fujaba is limited to small or medium-sized projects.
In summary, Fujaba offered us a quick, well visualized way to implement the simulation of finite automata. The simulation of these automata using the integrated DOBS is more practical than beautiful, but proved to be sufficient for our purposes.
February 22, 2008
Bidirectional synchronization
The effort of blogging already seems to pay off as I start to get mails with interesting references to related work. Yesterday Miguel Garcia pointed me to his workshop paper Bidirectional Synchronization of Multiple Views of Software Models.
What I liked about the paper is its discussion of related work and the references that give a very comprehensive overview of the state of the art in this field, i.e., Miguel discusses with a bird's eye view approaches to solve the view update problem like program inversion, lenses, QVT, ATL and TGG (triple graph grammars, to be discussed in the future). Indeed, in my research on diagram editors I currently have to deal with the problem of reflecting changes on the abstract syntax level back to concrete syntax (and vice versa, of course).
Abstract of Miguel's paper:
Current best-practices for defining Domain-Specific Modeling Languages call for metamodeling techniques, which do not take into account the future use of such languages in multiview design environments. Tool implementers have tried a variety of ad-hoc techniques to maintain views in-synch, with modest results. To improve this state of affairs, a declarative approach is elaborated to automate multiview synchronization, building upon existing metamodeling techniques and recent advances in the field of function inversion for bidirectionalization. An application of these ideas to EMOF and a discussion of the resulting Declarative MVC software architecture are also provided. A significant benefit of the approach is the resulting comprehensive solution to a recurrent problem in the software modeling field.
I look forward to further external contributions!
What I liked about the paper is its discussion of related work and the references that give a very comprehensive overview of the state of the art in this field, i.e., Miguel discusses with a bird's eye view approaches to solve the view update problem like program inversion, lenses, QVT, ATL and TGG (triple graph grammars, to be discussed in the future). Indeed, in my research on diagram editors I currently have to deal with the problem of reflecting changes on the abstract syntax level back to concrete syntax (and vice versa, of course).
Abstract of Miguel's paper:
Current best-practices for defining Domain-Specific Modeling Languages call for metamodeling techniques, which do not take into account the future use of such languages in multiview design environments. Tool implementers have tried a variety of ad-hoc techniques to maintain views in-synch, with modest results. To improve this state of affairs, a declarative approach is elaborated to automate multiview synchronization, building upon existing metamodeling techniques and recent advances in the field of function inversion for bidirectionalization. An application of these ideas to EMOF and a discussion of the resulting Declarative MVC software architecture are also provided. A significant benefit of the approach is the resulting comprehensive solution to a recurrent problem in the software modeling field.
I look forward to further external contributions!
January 30, 2008
Graph Parser Combinators
This post is about a topic I am particularly interested in, namely Graph Parser Combinators. Among functional programmers parser combinators are very popular. They are fun to play with and a lot of research has been done to make them more practically relevant (mainly by improving efficiency). There is an abundance of different libraries, e.g., the HUT Parser Combinators, Parsec or polyparse.
Since I have to deal a lot with graph-grammar based visual languages (remember my post about the diagram editor generator DiaGen), the question arose whether parser combinators may also be useful for graph parsing. So I have implemented a prototypical Haskell library and several exemplary parsers. And although there are some fundamental differences between graph and string parsing it worked astoundingly well.
At IFL 2007 I have introduced this approach. Several people have asked me whether graph parser combinators actually are powerful enough to describe highly-meshed graph languages like, e.g., Flowgraphs, a graph language representing structured Flowcharts. Such languages can naturally be described using hyperedge replacement grammars. The answer is yes, and I am going to present a solution to this problem at GT-VMT 2008.
Further reading:
Since I have to deal a lot with graph-grammar based visual languages (remember my post about the diagram editor generator DiaGen), the question arose whether parser combinators may also be useful for graph parsing. So I have implemented a prototypical Haskell library and several exemplary parsers. And although there are some fundamental differences between graph and string parsing it worked astoundingly well.
At IFL 2007 I have introduced this approach. Several people have asked me whether graph parser combinators actually are powerful enough to describe highly-meshed graph languages like, e.g., Flowgraphs, a graph language representing structured Flowcharts. Such languages can naturally be described using hyperedge replacement grammars. The answer is yes, and I am going to present a solution to this problem at GT-VMT 2008.
Further reading:
- Graph Parser Combinators, Mazanek, S., Minas, M., 2008, Proceedings of IFL 2007, to appear
- Parsing of Hyperedge Replacement Grammars with Graph Parser Combinators, Mazanek, S., Minas, M., 2008, Proceedings of GT-VMT 2008, to appear
January 06, 2008
AToM3
I am back from vacation and continue reporting about the seminar talks. On 29.11.07 we discussed the tool AToM3, a research project of Hans Vangheluwe and Juan de Lara.
AToM3 is an acronym for "A Tool for Multi-formalism and Meta-Modelling". From my point of view its main features are:
AToM3 is a very interesting research tool. There are a lot of publications discussing particular aspects of the tool and its theoretical foundations. However, it seems not to be ready for production settings yet. Parts of the documentation are outdated and even the Hello-World example caused several exceptions (but I got it up and running) and useless warnings like "Bad things will happen". However, as a researcher in the area of graph transformation you have to deal with the tool or at least with the publications by all means.
Further reading:
AToM3 is an acronym for "A Tool for Multi-formalism and Meta-Modelling". From my point of view its main features are:
- meta CASE-tool: specify a visual language (formalism) and generate an environment
- homogeneous view on metamodelling: define models in a particular formalism and use them directly as a formalism again, for instance, a petri net formalism can be defined using the ER (entity relationship) formalism and in the following real petri nets can be drawn; most of AToM3 can be bootstrapped (even user interaction)
- model transformations: internally models are represented as graphs, graph grammars can be defined and used for model transformation
AToM3 is a very interesting research tool. There are a lot of publications discussing particular aspects of the tool and its theoretical foundations. However, it seems not to be ready for production settings yet. Parts of the documentation are outdated and even the Hello-World example caused several exceptions (but I got it up and running) and useless warnings like "Bad things will happen". However, as a researcher in the area of graph transformation you have to deal with the tool or at least with the publications by all means.
Further reading:
November 15, 2007
DiaGen
The next student presentation in our seminar was about DiaGen, the diagram editor generator developed at our department. It was also held on October 25, 2007.
The main advantages of DiaGen editors are (from my point of view):
DiaGen provides an editor framework as well as a so-called Designer for the specification of diagram editors. The editor developer specifies the editor (language), generates editor-specific code and together with the DiaGen editor framework a fully-fledged diagram editor can be launched immediately.
The editing process is not half as difficult as it may look at a first sight :-), so read on. The editor user draws components freely on the screen. In a first step the so-called modeler maps the diagram to its hypergraph representation as already mentioned in the last post. This hypergraph model already incorporates spatial relations as edges, e.g. to indicate, that a particular component is contained in another one. The next step is the reducer. In order to understand the reducer an analogy from string parsing is handy. Think of it as a lexer that provides a more abstract representation of the hypergraph model. The last important step is parsing the reduced hypergraph model and giving the user visual feedback about correct parts and errors. Parsing is done according to a hypergraph grammar as explained in the last post about Hyperedge Replacement Graph Grammars.
For motivational purposes here you can see an image of a DiaGen editor for flowcharts.
Further reading:
The main advantages of DiaGen editors are (from my point of view):
- combination of free-hand editing and syntax-directed editing
- on-line syntax checks of diagrams during the editing process, partially correct diagrams as intermediate steps are perfectly normal
DiaGen provides an editor framework as well as a so-called Designer for the specification of diagram editors. The editor developer specifies the editor (language), generates editor-specific code and together with the DiaGen editor framework a fully-fledged diagram editor can be launched immediately.
The editing process is not half as difficult as it may look at a first sight :-), so read on. The editor user draws components freely on the screen. In a first step the so-called modeler maps the diagram to its hypergraph representation as already mentioned in the last post. This hypergraph model already incorporates spatial relations as edges, e.g. to indicate, that a particular component is contained in another one. The next step is the reducer. In order to understand the reducer an analogy from string parsing is handy. Think of it as a lexer that provides a more abstract representation of the hypergraph model. The last important step is parsing the reduced hypergraph model and giving the user visual feedback about correct parts and errors. Parsing is done according to a hypergraph grammar as explained in the last post about Hyperedge Replacement Graph Grammars.
For motivational purposes here you can see an image of a DiaGen editor for flowcharts.
Further reading:
- DiaGen Website
- Concepts and realization of a diagram editor generator based on hypergraph transformation, Mark Minas, 2002, Science of Computer Programming, 44(2):157-180
Hyperedge Replacement Graph Grammars
The second talk was held on October 25, 2007. It was about Hyperedge Replacement Graph Grammars HRG. I know, I know, ... In the last post I promised to focus more on practical things. But: Hyperedge replacement is more practical than you might think. For instance, hypergraphs can be used as a model for visual languages as realized in the tool DiaGen. Following this approach a visual language can be defined via a HRG and syntax analysis of diagrams can be reduced to hypergraph parsing.
The main advantages of HRG are:
I cannot introduce the whole theory in a single blog post, so I give you an impression by showing some pictures.
This is a flowchart. It consists of statements (rectangles) and conditions (diamonds) that are linked with arrows indicating the flow of control. The presented algorithm is the so-called Hasse-Collatz problem but this is not so interesting here. More interesting is the fact, that due to their graph-like structure flowcharts can be described by a HRG quite straightforwardly.
However, before I can show you the HRG I first have to give a possible hypergraph model of the example flowchart. Every flowchart component is mapped to a hyperedge represented by a rectangle. In contrast to directed edges a hyperedge may connect an arbitrary number of nodes so that a representation by an arrow is not possible in general. The nodes are given by filled black circles. Nodes visited by a particular hyperedge are connected to this edge by a line called a tentacle of the edge. Each tentacle has a particular role, for instance, it has to be clear which tentacle of a cond edge represents the true and which one the false case. Hyperedges with the same label have to visit the same number of nodes called the type of the edge.
Now we can discuss the HRG of structured flowgraphs (the graphs behind a correct flowchart). A HRG is defined by a set of nonterminal labels N, a set of terminal labels T, a set of productions P and a starting label S that has to be an element of N. The productions are given in the picture in a notation similar to BNF. They are recursively defined in a quite intuitive manner. Note, that a HRG production always has a single nonterminal edge on the lhs. As a consequence HRGs have nice properties resulting from this kind of contextfreeness. However, it is also a restriction, because important graph languages cannot be described that way.
HRG is a kind of DPO (as introduced in the last post about the algebraic approach). The gluing graph consists just of the nodes that occur in both the lhs and the rhs of a production.
Due to the contextfreeness of HRG it is possible to construct derivation trees. Such a tree can be represented as shown in the picture (it is the tree for our example). All leafs are marked with terminal symbols and nodes with nonterminal symbols. The number of subtrees of a node depends on the number of hyperedges on the rhs of the applied production. The numbers in parentheses are the corresponding node numbers of the graph model.
Further reading:
The main advantages of HRG are:
- easy to grasp
- very close analogy to context-free string grammars
- straightforward syntax analysis possible
I cannot introduce the whole theory in a single blog post, so I give you an impression by showing some pictures.
This is a flowchart. It consists of statements (rectangles) and conditions (diamonds) that are linked with arrows indicating the flow of control. The presented algorithm is the so-called Hasse-Collatz problem but this is not so interesting here. More interesting is the fact, that due to their graph-like structure flowcharts can be described by a HRG quite straightforwardly.
However, before I can show you the HRG I first have to give a possible hypergraph model of the example flowchart. Every flowchart component is mapped to a hyperedge represented by a rectangle. In contrast to directed edges a hyperedge may connect an arbitrary number of nodes so that a representation by an arrow is not possible in general. The nodes are given by filled black circles. Nodes visited by a particular hyperedge are connected to this edge by a line called a tentacle of the edge. Each tentacle has a particular role, for instance, it has to be clear which tentacle of a cond edge represents the true and which one the false case. Hyperedges with the same label have to visit the same number of nodes called the type of the edge.
Now we can discuss the HRG of structured flowgraphs (the graphs behind a correct flowchart). A HRG is defined by a set of nonterminal labels N, a set of terminal labels T, a set of productions P and a starting label S that has to be an element of N. The productions are given in the picture in a notation similar to BNF. They are recursively defined in a quite intuitive manner. Note, that a HRG production always has a single nonterminal edge on the lhs. As a consequence HRGs have nice properties resulting from this kind of contextfreeness. However, it is also a restriction, because important graph languages cannot be described that way.
HRG is a kind of DPO (as introduced in the last post about the algebraic approach). The gluing graph consists just of the nodes that occur in both the lhs and the rhs of a production.
Due to the contextfreeness of HRG it is possible to construct derivation trees. Such a tree can be represented as shown in the picture (it is the tree for our example). All leafs are marked with terminal symbols and nodes with nonterminal symbols. The number of subtrees of a node depends on the number of hyperedges on the rhs of the applied production. The numbers in parentheses are the corresponding node numbers of the graph model.
Further reading:
- Handbook of Graph Grammars and Computing by Graph Transformation, Rozenberg (ed.), 1997, World Scientific Publishing: chapter 2
Algebraic approach to graph transformation
Let's start with the first talk of the seminar held on October 18, 2007 about the algebraic approach to graph transformation that can be subdivided in the single and the double pushout approach. These terms sound quite daunting, but the underlying concept is not hard to grasp. Both approaches are based on the concepts graph, production and graph grammar, that I will not introduce here in detail. Just note, that the concepts production and grammar can be understood quite closely to the analog notions in string rewriting.
In the double pushout approach DPO a production consists of three graphs. The left-hand side (lhs) graph L is the graph to be matched. The interface graph K is the so-called gluing graph, i.e. the subgraph of L that is not deleted by the production. And the right-hand side (rhs) graph R is the graph L should be replaced with. Between K and the graphs L and R morphisms l and r have to be given mainly because corresponding nodes and edges have to be identified. If this production should be applied to a host graph G a double pushout has to be constructed. Therefore we need to find a match of L in G (also a morphism, m). Next all parts of G have to be deleted that are not in L (of course we mean the images regarding the particular morphism). And finally we have to embed into the resulting graph D all parts of R that are not in L leading to the target graph H. A production can only be applied if the morphism diagram commutes and the universal pushout property holds twice -- this sounds complicated but it conforms to the intuitive understanding of graph transformation. The DPO is very nice from a mathematical point of view, however, it is not always applicable.
The single pushout approach SPO does not need a gluing graph K. A production just consists of a lhs graph L and a rhs graph R with a partial morphism inbetween. As in DPO a match of L in G has to be found. This match gets replaced by R. Nodes and edges not occurring in the rhs anymore are deleted rigorously.
The main difference between single and double pushout is the so-called dangling edge condition. Following the double pushout approach a node must not be removed if there are still edges to this node. In the single pushout approach this restriction is canceled: all dangling edges are just deleted. This deletion of edges makes the SPO quite difficult from a theoretical point of view.
Ok, so far for now. Sorry for starting with theory -- I promise that practical topics will be the focus of this blog in the future :-)
Further reading:
In the double pushout approach DPO a production consists of three graphs. The left-hand side (lhs) graph L is the graph to be matched. The interface graph K is the so-called gluing graph, i.e. the subgraph of L that is not deleted by the production. And the right-hand side (rhs) graph R is the graph L should be replaced with. Between K and the graphs L and R morphisms l and r have to be given mainly because corresponding nodes and edges have to be identified. If this production should be applied to a host graph G a double pushout has to be constructed. Therefore we need to find a match of L in G (also a morphism, m). Next all parts of G have to be deleted that are not in L (of course we mean the images regarding the particular morphism). And finally we have to embed into the resulting graph D all parts of R that are not in L leading to the target graph H. A production can only be applied if the morphism diagram commutes and the universal pushout property holds twice -- this sounds complicated but it conforms to the intuitive understanding of graph transformation. The DPO is very nice from a mathematical point of view, however, it is not always applicable.
The single pushout approach SPO does not need a gluing graph K. A production just consists of a lhs graph L and a rhs graph R with a partial morphism inbetween. As in DPO a match of L in G has to be found. This match gets replaced by R. Nodes and edges not occurring in the rhs anymore are deleted rigorously.
The main difference between single and double pushout is the so-called dangling edge condition. Following the double pushout approach a node must not be removed if there are still edges to this node. In the single pushout approach this restriction is canceled: all dangling edges are just deleted. This deletion of edges makes the SPO quite difficult from a theoretical point of view.
Ok, so far for now. Sorry for starting with theory -- I promise that practical topics will be the focus of this blog in the future :-)
Further reading:
- Handbook of Graph Grammars and Computing by Graph Transformation, Rozenberg (ed.), 1997, World Scientific Publishing: chapters 3 and 4
- Graph Transformation in a Nutshell, Reiko Heckel, Electronic Notes in Theoretical Computer Science, Volume 148, Issue 1, Proceedings of the School of SegraVis Research Training Network on Foundations of Visual Modelling Techniques (FoVMT 2004), 2006, Pages 187-198.
Subscribe to:
Posts (Atom)