Búsqueda avanzada

Strategy-Driven Graph Transformations in PORGY


PORGY [2] is a visual and interactive tool designed to facilitate the specification and analysis of complex systems. PORGY uses graphs to represent the system modelled, and graph rewrite rules guided by strategies to describe the dynamics of the system.
Graphical languages are widely used for describing complex structures in a visual and intuitive way in a variety of domains, such as software modelling (e.g., UML diagrams), representation of proofs (e.g., proof nets), microprocessor design, XML documents, communication networks, and biological systems, amongst others. Graph transformations (or graph rewriting) are used to define the behaviour of the system modelled. From a theoretical point of view, graph rewriting has solid logic, algebraic and categorical foundations [3, 9], and from a practical point of view, it has many applications in specification, programming, and simulation [4, 5].
When the graphs are large or growing via transformations, or when the number of transformation rules is important, being able to directly interact with the rewriting system becomes crucial to understand the changes in the graph structure. From a naïve point of view, the output of a graph rewriting system is a dynamic graph: a sequence of graphs obtained through a series of modifications (addition/deletion of nodes/edges). However, the study of a rewriting system is actually much more complex. Reasoning about the system’s properties actually involves testing various rewriting scenarios, backtracking to a previously computed graph, possibly updating rules, etc. PORGY, developed in collaboration with INRIA Bordeaux-Sud Ouest (, addresses these issues.
Our approach is based on the use of port graphs and port graph rewriting rules [1]. Port-graphs are a specific class of labelled graphs introduced as an abstract representation of proteins, and used to model biochemical interactions and autonomous systems. We illustrate this concept by using port graph transformations to model biochemical systems (biochemical interactions that take part in the regulation of cell proliferation and transformation) and interaction nets. These case studies illustrate the need for highly dynamic graphs, and highlight interesting challenges for graph visualisation. PORGY provides support for the initial task of defining a set of graph rewriting rules, and the graph representing the initial state of the system (the «initial model» in PORGY’s terminology), using a visual editor.
Other crucial issues concern when and where rules are applied. To address this problem, PORGY provides a strategy language to constrain the rewriting derivations, generalising the control structures used in graph-based tools such as PROGRES [10] and GP [8], and rewritebased programming languages such as Stratego and ELAN. In particular, the strategy language includes control structures that facilitate the implementation of graph traversal algorithms, thanks to the explicit definition of «positions» in a graph, where rules can be applied (we refer the reader
M.M. Gallardo, M. Villaret, L. Iribarne (Eds.): PROLE’2012, pp. 253-254, ISBN:978-84-15487-27-2. Jornadas SISTEDES’2012, Almería 17-19 sept. 2012, Universidad de Almería.

Palabras Clave:





Este artículo tiene una licencia de uso CreativeCommons - Reconocimiento (by)

Descarga el artículo haciendo click aquí.