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 theory. Show all posts
Showing posts with label theory. 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
Alligator Eggs revisited (again)
The video about the animated editor for Alligator Eggs has raised some questions on where the editor is available for download. Therefore, Torsten has provided an executable jar. Feel free to try it out yourself!
Actually, the success of this video on youtube (more than 3.000 views already) really motivates me to implement syntax-based assistance for the language of alligator eggs. The language is tree-based, i.e., context-free, so that the developed approach is applicable. I hope to find some time in the near future to this end.
Actually, the success of this video on youtube (more than 3.000 views already) really motivates me to implement syntax-based assistance for the language of alligator eggs. The language is tree-based, i.e., context-free, so that the developed approach is applicable. I hope to find some time in the near future to this end.
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 19, 2008
Usability
In this post I briefly discuss usability. First of all, I have to say that there is so much research that it is nearly impossible to write a short blog post about this topic. For instance, Jakob Nielsen, a popular usability expert, writes about usability for years. So I will just give you a quick impression by introducing the GOMS approach, which I found very straightforward and easy to apply. I especially use it to evaluate the task performance of my approach to diagram completion.
GOMS is an acronym for Goals, Operators, Methods, and Selection rules. The approach, however, is much easier than these terms suggest. The key idea is, that you write down all operations that have to be performed in order to achieve a given goal. Depending on its kind a predetermined execution time is attached to each of these operations. For instance, a keystroke takes 0.28 seconds for an average user, pointing with the mouse to an object on the screen lasts round about 1.1 seconds. There are several more kinds of actions and appropriate average times (determined on an empirical base). Summing up the times for all necessary operations finally yields the task execution time. Once you have this time you can compare different user interfaces, you can evaluate changes to the user interface and so on. It's that easy.
Note that in the context of the Visual Week (15.-21.09.08 in Herrsching am Ammersee, Germany) there will be a tutorial on another popular usability approach called Cognitive Dimensions. Here, usability is evaluated on a much higher level. To quote from the tutorial website (accessed 19 July 2008):
The Cognitive Dimensions of Notations (CDs) framework is the world's leading approach to understanding the usability of programming tools. It provides an analytic framework and design vocabulary that can be used to evaluate and improve, not only programming languages, but a wide variety of environments and notations for design, problem-solving, and creative work.
Currently I apply usability evaluation methods to my approach on diagram completion. In my talk "Exploiting the Layout Engine to Assess Diagram Completions" to be held at the layout workshop LED 2008 (satellite event of VL/HCC 2008) I will present a first improvement: in certain situations a special shortcut can more than double the task performance (to speak in terms of GOMS). Stay tuned!
Further reading:
GOMS is an acronym for Goals, Operators, Methods, and Selection rules. The approach, however, is much easier than these terms suggest. The key idea is, that you write down all operations that have to be performed in order to achieve a given goal. Depending on its kind a predetermined execution time is attached to each of these operations. For instance, a keystroke takes 0.28 seconds for an average user, pointing with the mouse to an object on the screen lasts round about 1.1 seconds. There are several more kinds of actions and appropriate average times (determined on an empirical base). Summing up the times for all necessary operations finally yields the task execution time. Once you have this time you can compare different user interfaces, you can evaluate changes to the user interface and so on. It's that easy.
Note that in the context of the Visual Week (15.-21.09.08 in Herrsching am Ammersee, Germany) there will be a tutorial on another popular usability approach called Cognitive Dimensions. Here, usability is evaluated on a much higher level. To quote from the tutorial website (accessed 19 July 2008):
The Cognitive Dimensions of Notations (CDs) framework is the world's leading approach to understanding the usability of programming tools. It provides an analytic framework and design vocabulary that can be used to evaluate and improve, not only programming languages, but a wide variety of environments and notations for design, problem-solving, and creative work.
Currently I apply usability evaluation methods to my approach on diagram completion. In my talk "Exploiting the Layout Engine to Assess Diagram Completions" to be held at the layout workshop LED 2008 (satellite event of VL/HCC 2008) I will present a first improvement: in certain situations a special shortcut can more than double the task performance (to speak in terms of GOMS). Stay tuned!
Further reading:
- Stuart Card, Thomas P. Moran and Allen Newell: The Psychology of Human Computer Interaction. 1983.
- GOMS Model Work, comprehensive website about GOMS maintained by David E. Kieras.
July 18, 2008
RTA 2008
I am just back from the RTA 2008 (Rewriting Techniques and Applications) conference in Linz. My talk has been on Wednesday and was about Functional-logic Graph Parser Combinators. I already have written on this blog about graph parser combinators, but this purely functional approach had several problems we solved using functional-logic programming techniques. In particular, the new framework can be used as a back-end for my approach to diagram completion.
Hagenberg, the conference location, is a nice little village 20km away from Linz. It has a romantic, medieval castle in which the conference took place. Furthermore, an important branch of the FH Oberösterreich is located here.
From the talks I attended I especially liked the invited one by Thomas Hillenbrand about the theorem prover Waldmeister which is known to be very fast and powerful. Recently, the popular computer algebra system Mathematica even incorporated the Waldmeister approach to equational theorem proving into its tool suite.
Although I do not know much about automatic theorem proving there have been some impressive facts I remember from the talk. First of all, it is still very important to think about the most efficient data structures for a particular application. In theorem proving execution time and memory usage are really a big issue, so every little improvement of the data structures might make a decisive difference. And second, there is no all-in-one algorithm suitable for every application domain. Thus, it is important to provide a flexible framework that can be parameterized by the users. In Waldmeister one has to choose among several weighting functions from which each one is superior for some special domains. Finally, automatic theorem proving has advanced a lot in the last years. Even for some "real proofs" there is a good chance that they can be found without much manual investigation.
Hagenberg, the conference location, is a nice little village 20km away from Linz. It has a romantic, medieval castle in which the conference took place. Furthermore, an important branch of the FH Oberösterreich is located here.
From the talks I attended I especially liked the invited one by Thomas Hillenbrand about the theorem prover Waldmeister which is known to be very fast and powerful. Recently, the popular computer algebra system Mathematica even incorporated the Waldmeister approach to equational theorem proving into its tool suite.
Although I do not know much about automatic theorem proving there have been some impressive facts I remember from the talk. First of all, it is still very important to think about the most efficient data structures for a particular application. In theorem proving execution time and memory usage are really a big issue, so every little improvement of the data structures might make a decisive difference. And second, there is no all-in-one algorithm suitable for every application domain. Thus, it is important to provide a flexible framework that can be parameterized by the users. In Waldmeister one has to choose among several weighting functions from which each one is superior for some special domains. Finally, automatic theorem proving has advanced a lot in the last years. Even for some "real proofs" there is a good chance that they can be found without much manual investigation.
July 12, 2008
Course on Visual Languages
I already have written several posts about our previous course on graph and model transformation conducted in autumn last year and the practical afterwards. Next autumn we will hold another course, this time directly on visual languages. We will discuss approaches to language definition like extended positional grammars, constraint multiset grammars, hyperedge replacement grammars, and, of course, metamodels. I look forward to report on these approaches here soon.
Similar courses and practicals have been conducted at several universities in the past (e.g. at Universität Bremen (Berthold Hoffmann), CAU Kiel (Hauke Fuhrmann), RWTH Aachen (Manfred Nagl), Philipps-Universität Marburg (Gabriele Taentzer)). I would appreciate very much any comments on the lessons learned while conducting these courses.
Similar courses and practicals have been conducted at several universities in the past (e.g. at Universität Bremen (Berthold Hoffmann), CAU Kiel (Hauke Fuhrmann), RWTH Aachen (Manfred Nagl), Philipps-Universität Marburg (Gabriele Taentzer)). I would appreciate very much any comments on the lessons learned while conducting these courses.
July 05, 2008
Constraint Logic Programming and Diagram Completion
I got stimulating feedback after my last post on diagram completion. For instance, I was not aware of the SmartEMF project of Anders Hessellund et al. They aim at extending EMF with an inference engine to facilitate reasoning about models. Interestingly, they also get some guidance that way. A similar approach has been realized in the AToM3 tool by Sagar Sen et al. They also employ constraint logic programming to infer model completions.
The diagram completion presented in my last post has been incorporated into the DiaGen tool which is based on hyperedge replacement grammars. However, metamodels are more popular nowadays for language specification. I already introduced the DiaMeta tool on this blog. It is based on DiaGen, but allows the generation of free-hand editors out of a metamodel-based specification. Syntax analysis then can be mapped to the solution of a constraint satisfaction problem. It would be interesting to see if the approaches of Hessellund and Sen could be used to get similar diagram completion for DiaMeta.
Dear readers, please continue to comment on my posts or give feedback by mail. I appreciate this very much. If your own project is related somehow to visual languages, do not hesitate and send me a short summary. I gladly post and/or discuss it here on this blog.
Further reading:
The diagram completion presented in my last post has been incorporated into the DiaGen tool which is based on hyperedge replacement grammars. However, metamodels are more popular nowadays for language specification. I already introduced the DiaMeta tool on this blog. It is based on DiaGen, but allows the generation of free-hand editors out of a metamodel-based specification. Syntax analysis then can be mapped to the solution of a constraint satisfaction problem. It would be interesting to see if the approaches of Hessellund and Sen could be used to get similar diagram completion for DiaMeta.
Dear readers, please continue to comment on my posts or give feedback by mail. I appreciate this very much. If your own project is related somehow to visual languages, do not hesitate and send me a short summary. I gladly post and/or discuss it here on this blog.
Further reading:
- Anders Hessellund, Krzysztof Czarnecki, Andrzej Wasowski: Guided Development with Multiple Domain-Specific Languages. In Proc. of MODELS'07, 2007
- Sagar Sen, Benoit Baudry, and Hans Vangheluwe: Domain-specific model editors with model completion. In Multi-paradigm Modelling Workshop at MoDELS'07, 2007.
- Mark Minas: Syntax analysis for diagram editors: A constraint satisfaction problem. In Proc. of the Working Conference on Advanced Visual Interfaces (AVI'2006), 2006.
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
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 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:
December 15, 2007
DiaMeta
So, today I continue blogging here. Kindly excuse the fairly long period without a post. The submission deadline for the conference GTVMT was so rapidly approaching...
The next talk in our seminar was about DiaMeta, the successor of the diagram editor generator DiaGen. In contrast to DiaGen DiaMeta is based on a metamodel instead of a hypergraph grammar. Not that metamodels are more powerful: this truly is not the case. But people are so familiar with drawing class diagrams aka metamodels that nowadays metamodel-based tools are more popular.
DiaMeta is based on the Eclipse Modeling Framework we already have discussed (there also is an experimental version based on MOF, see references below). This is very benefitial from an application integration point of view, because the abstract syntax of diagrams can be serialized in standard compliant XMI.
The most interesting point to know about syntax analysis is that it is basically performed by solving a constraint satisfaction problem. This important correlation has been noticed by Minas 2006. Therefore DiaMeta has to make heavy use of the powerful reflective features EMF provides.
The picture shows the overall DiaMeta architecture. There are two important differences to DiaGen. The first one is that the reducer does not create a reduced hypergraph model any more, but instead a so-called instance graph. This is a graph whose nodes are marked with class names of the metamodel and whose edges represent references. However, these annotations do not have to be the concrete object types (they even can be names of abstract classes). It is the task of the so-called checker, the second important difference!, to map these nodes to non-abstract classes and instantiate corresponding objects. The instance graph is therefore used as a constraint net that can be solved using the information given in the metamodel, e.g. references, inheritance relationships, cardinalities, etc. This is described in detail in the first paper mentioned in Further reading.
Further reading:
The next talk in our seminar was about DiaMeta, the successor of the diagram editor generator DiaGen. In contrast to DiaGen DiaMeta is based on a metamodel instead of a hypergraph grammar. Not that metamodels are more powerful: this truly is not the case. But people are so familiar with drawing class diagrams aka metamodels that nowadays metamodel-based tools are more popular.
DiaMeta is based on the Eclipse Modeling Framework we already have discussed (there also is an experimental version based on MOF, see references below). This is very benefitial from an application integration point of view, because the abstract syntax of diagrams can be serialized in standard compliant XMI.
The most interesting point to know about syntax analysis is that it is basically performed by solving a constraint satisfaction problem. This important correlation has been noticed by Minas 2006. Therefore DiaMeta has to make heavy use of the powerful reflective features EMF provides.
The picture shows the overall DiaMeta architecture. There are two important differences to DiaGen. The first one is that the reducer does not create a reduced hypergraph model any more, but instead a so-called instance graph. This is a graph whose nodes are marked with class names of the metamodel and whose edges represent references. However, these annotations do not have to be the concrete object types (they even can be names of abstract classes). It is the task of the so-called checker, the second important difference!, to map these nodes to non-abstract classes and instantiate corresponding objects. The instance graph is therefore used as a constraint net that can be solved using the information given in the metamodel, e.g. references, inheritance relationships, cardinalities, etc. This is described in detail in the first paper mentioned in Further reading.
Further reading:
- Generating meta-model-based freehand editors. Minas, Proc. of 3rd International Workshop on Graph Based Tools (GraBaTs'06), 2006.
- Syntax analysis for diagram editors: A constraint satisfaction problem. Minas, In Proc. of the Working Conference on Advanced Visual Interfaces (AVI'2006), 2006.
- Generating visual editors based on Fujaba/MOFLON and DiaMeta. Minas, Proc. Fujaba Days 2006
- DiaMeta website
November 15, 2007
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)