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 may be used (implicitly 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).
Having an AGG graph grammar at hand, it may be validated using AGG's analysis techniques, namely critical pair analysis and consistency checking.The tool environment provides graphical editors for graphs and rules and an integrated textual editor for Java expressions. Moreover, visual interpretation and validation is supported.
Characteristics of AGG are: - Complex data structures are modeled as graphs which may be typed by a type graph. - 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. - Application of several rules sequentially shows an application scenario. - AGG graphs may be attributed by 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.
- Additionally, rules may have attribute conditions being boolean Java expressions.
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 and expressions essentially follows the ideas of attributed graph grammars, where Java classes and expressions replace algebraic specifications and terms.
An extended description of the kernel AGG language concepts is available as Postscript document with several comprehensive figures 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.
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 object 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 areas 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. 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)
Boris Melamed: Design and Implementation of an Attribute Manager for Conditional and Distributed Graph Transformation 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
* The PROGRES system: http://www-i3.informatik.rwth-aachen.de/Research/PROGRES
* And there is even more related work
Revision: