Abstract
AGG is a rule based visual language supporting an algebraic approach to graph transformation. It aims at the specification and prototypical implementation of applications with complex graph-structured data. AGG code may be used (implicit in "code") as a general purpose graph transformation engine in high-level JAVA applications employing graph transformation methods. Due to its rule based character AGG may also be near in the field of artificial intelligence; (we are looking for further evidence in that case).
Characteristic of AGG is: - Complex data structures are modeled as graphs. - The system's behavior is specified by graph rules using an if-then description style. - Moreover, AGG features rules with negative application conditions to express requirements for non-existence of substructures. - Application of a graph rule transforms the structure graph. - Applying the rules given by the graph grammar non-deterministically: rules to be applied and their matches are chosen randomly. - Application of several rules sequentially shows an application scenario. - AGG graphs may be attributed by (http://www.javasoft.com/) Java objects and types. Basic data types as well as object classes already available in Java class libraries may be used. - Moreover, new Java classes may be included. - The graph rules may be attributed by Java expressions which are evaluated during rule applications. It is possible to define typed attributed graph transformation with node type inheritance. This means that the attributed type graph can be enriched with an inheritance relation between nodes. Each node type can have more then one direct ancestor from which it inherits the attributes and edges.
In this context, it is possible to define abstract rules, containing ancestor (parents) nodes. These rules are equivalent to a number of concrete rules, resulting from the substitution of the ancestor nodes by the nodes in their inheritance clan. Therefore, rules become more compact and suitable for their use in combination with meta-modeling.
The tool environment provides graphical editors for graphs and rules and an integrated textual editor for Java expressions. Moreover, visual interpretation is supported. While step means performing direct derivations (transformation) for user-selected productions (rules) and occurrences (matches), a whole transformation sequence is executed in the interpretation mode. Furtheron, analysis tools for graph transformation systems are available.
Language Concepts
AGG programs consist of two main parts: a graph grammar attributed by Java objects which may come from user-defined Java classes. This set of classes forms the second part. Clearly, libraries of Java classes such as JDK are available, but are not considered to be part of an AGG program. Graph grammars contain a start graph and a set of rules which may have negative application conditions. The way graph rules are applied directly realizes the single-pushout approach to graph transformation. The attribution of nodes and arcs by Java objects an expressions essentially follows the ideas of attributed graph grammars, where Java classes and expressions replace algebraic specifications and terms.A graph consists of two disjoint sets containing the nodes and the arcs of the graph. As a whole, the nodes and arcs are called the objects of the graph. Every arc represents a directed connection between two nodes, which are called the source and target nodes of the arc. To allow for some further classification of a graph object, any object may be associated with exactly one label from a given label set. The labels are also called types and if an object o has the label l, we say o is of type l. Note that in our notion of a graph, we can have multiple arcs of the same type between a single pair of nodes, because every arc has an identity on its own, just like a node does. This distinguishes our view from another popular notion of graphs where an arc is described just as a relation between nodes. Note that in our idea of a graph, the position of a node or an arc in the plane holds neither syntactic nor semantic information, i.e., the layout of a graph is just a matter of presentation for the sake of readability to the user.An attribute in AGG is declared just like a variable in a conventional programming language: we specify a name and a certain type for the attribute, and then we may assign any value of the specified type to it. Of course, there can be multiple attributes for one object, even of the same type. Note that all graph objects of the same type also share their attribute declarations, i.e. the list of attribute types and selectors; only the values of the attributes may be chosen individually. From a conceptual point of view, attribute declarations have to be considered as an integral part of the definition of a type. This observation is not very surprising, since in many respects, the concept of a type with integral attribute declarations resembles the notion of a class with its member variables in object-oriented programming.
An action can be viewed as a state transition, and obviously, a transition of states can be specified by giving descriptions of the states before an after the action in question. Since states are modeled as graphs in AGG, it follows that basically an action can be described as a pair of two graphs modeling the ``before'' and ``after'' states. In the ``before'' state of an operation, we collect all the preconditions that have to be met for the operation to take place. The left-hand side of a graph rule states the necessary conditions for the specified operation to take place: A rule can only be applied if its conditions are fulfilled by the current concrete state graph. Quite obviously, this corresponds conceptually to an if-then clause with an empty else branch in a textual programming language. The checking of the conditions is accomplished by trying to find a match for the graph pattern given by the rule's left-hand side in the state graph, which is also called the host graph for the rule application. In terms of theory, matches and rules are graph-homomorphisms, i.e. mappings of the objects of one graph to those of another with certain compatibility commitments concerning source and target mappings. To indicate which objects are mapped to one another in the figures, we use numerical tags preceding an object's type name, separated by a colon.
The effect of a rule application at a given match is a state graph transformation, also called derivation or graph transformation step. Besides manipulating the nodes and arcs of a graph, a graph rule may also perform computations on the object attributes. Please note that AGG is not limited to injective morphisms. Any rule or match morphism may map two or more different objects to one single image object. By using non-injective rule-morphisms, for example, it is easy to declare a rule merging multiple nodes into one, contracting all the in- and outgoing arcs of the merged nodes at the single resulting node. The formal semantics of rule application is given in terms of category theory, by a single categorical construction known as a pushout in an appropriate category of attributed graphs with partial morphisms - hence the name Single-Pushout (SPO) approach.
We have already seen that the left-hand side of a rule states the necessary conditions that the current state must fulfill so that the rule can be applied. Therefore, we may also call them application conditions. Quite frequently though, the need arises to express that something must not be the case for a rule to be applicable. With a negative application condition (NAC) you specify exactly that fraction of a matching situation that you don't want to happen.
User's Manual of AGG
A brief manual of the AGG system is available as Postscript document with several comprehensive figures
(http://user.cs.tu-berlin.de/~gragra/agg/)
Further Documentation on AGG
Colimit Techniques: For the treatment of structuring mechanisms for categorical constructions, there is one most important concept in category theory: the colimit construction. In applications related to computer science, the colimit separates elements in different components and identifies elements which are connected via their relations. The colimit construction is not only relevant for scheme transformation. Recently, current oject oriented modeling methods like the UML, integrate structural and behavioural aspects with extensions of state machine formalisms. Category theory and especially the colimit construction, is suitable for both aspects, providing a unifying formal framework for object oriented design. Other application areas are Structuring and Refinement of formal specifications based on colimits in the category of signatures, Operational Semantics of functional logic programming languages based on the category of jungles, and Algebraic Development Techniques and their extensions (e.g. Statecharts, Graph Grammars, Algebraic High-Level Petri Nets, Action Nets or Dynamic Abstract Data Types). These applications can be based on colimit computation in two categories, namely signatures and graph signatures. Some main results are: A new constructive proof of co-completeness for sets, signatures and graph structures with partial morphisms. Proofs establishing (almost) linear complexity of the colimit constructions in all these categories. A library for colimit computations in these categories implemented in Eiffel, Java and C++. The algorithms are directly derived from the constructed proofs mentioned above. Additionally, the application of the colimit library in different a reas both in the context of specitfication languages and graph transformation is outlined. Performance tests and comparisons on several different development platforms establish the practical applicability of the colimit library. Reference: [D.Wolz: A Colimit Library for Graph Transformations and Algebraic Development Techniques. Doctoral-Dissertation, TU Berlin, 1998]Efficient Graph Pattern Matching: The AGG system represents -and solves- the problem of graph matching, a.k.a. subgraph homomorphism problem, as a constraint satisfaction problem (CSP). By de-coupling the solution algorithm from the graph model, this approach allows for variations of the employed graph model without affecting the CSP solution algorithm.
A paper on efficient graph pattern matching is available as Postscript document with several comprehensive figures
(http://user.cs.tu-berlin.de/~gragra/agg/match.ps)Furthermore, there are two master theses which describe the design concepts of AGG:
Michael Rudolf: Concepts and Implementation of an Interpreter for Attributed Graphtransformation (in german) (http://user.cs.tu-berlin.de/~gragra/agg/Diplomarbeiten/Rudolf.ps.gz) Boris Melamed: Design and Implementation of an Attribute Manager for Conditional and Distributed Graph Transformation (http://user.cs.tu-berlin.de/~gragra/agg/Diplomarbeiten/Melamed.ps.gz) Related Work
* Theory, Application, and Tools: G.Rozenberg et al. (Eds.), Handbook of Graph Grammars and Computing by Graph Transformation (vols.1,2,3). Published by World Scientific, Singapore 1997/1999
(http://www.worldscientific.com/books/compsci/specialpromotion.html)
* The PROGRES system:
(http://www-i3.informatik.rwth-aachen.de/research/progres/)
* And there is even more related work
(http://www-i3.informatik.rwth-aachen.de/research/progres/related.html)More information about AGG (http://user.cs.tu-berlin.de/~gragra/agg)