AbstractAGGis arule based visual languagesupporting an algebraic approach to graph transformation. It aims at the specification and prototypical implementation of applications with complex graph-structured data.AGGmay 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 characterAGGmay 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.

Characteristics of AGG are:-Complex data structures are modeled asgraphswhich may be typed by atype graph.-The system's behavior is specified bygraph rulesusing an if-then description style.-Moreover,AGGfeatures rules withnegative application conditionsto 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.-AGGgraphs may beattributed byJavaobjectsand 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 haveattribute conditionsbeing boolean Java expressions.The tool environment provides graphicaleditorsfor graphs and rules and an integrated textual editor for Java expressions. Moreover, visualinterpretationandvalidationis supported.

Language ConceptsAGGprogramsconsist of two main parts: agraph grammarattributed by Java objects which may come from user-definedJava 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 anAGGprogram. 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 AGGlanguage concepts is available as Postscript document with several comprehensive figuresA graphconsists of two disjoint sets containing thenodesand thearcsof 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 calledtypesand if an objectohas the labell, we sayois of typel. Note that in our notion of a graph, we can havemultiple arcsof 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 attributeinAGGis declared just like a variable in a conventional programming language: we specify anameand a certaintypefor the attribute, and then we may assign anyvalueof 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 actioncan 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 inAGG, it follows that basically an action can be described as apair of two graphsmodeling 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 anif-thenclause with an emptyelsebranch 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 thehost graphfor the rule application. In terms of theory, matches and rules aregraph-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 arule applicationat a given match is a stategraph transformation, also calledderivationor graph transformationstep. Besides manipulating the nodes and arcs of a graph, a graph rule may also perform computations on the object attributes. Please note thatAGGis 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. Theformal semanticsof rule application is given in terms ofcategory theory, by a single categorical construction known as apushoutin an appropriate category of attributed graphs with partial morphisms - hence the nameSingle-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 themapplication conditions. Quite frequently though, the need arises to express that something mustnotbe the case for a rule to be applicable. With anegative application condition (NAC)you specify exactly that fraction of a matching situation that you don't want to happen.

Further Documentation onAGGColimit 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:TheAGGsystem 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

* ThePROGRESsystem: http://www-i3.informatik.rwth-aachen.de/Research/PROGRES

* And there is evenmore related work

Revision: