The
goal of PORGY is to design and implement a visual environment for the
creation, transformation and analysis of dynamic graphs emerging from
port graph rewriting systems.
In port graphs, nodes have points, called ports, for attaching the edges,
thus providing an explicit partitioning of nodes connectivity. This
provides a general class of directed graphs allowing multiple edges and
loops, illustrated on an example below.

A mail system configuration depicted as a port
graph
PORGY
addresses the issue of dealing with port graph rewriting systems
visually. Taking benefit of the natural ability of the human eye to
locate complex graphical patterns, we want to design a visual and
interactive environment supporting the visual exploration, simulation
and analysis of port graph rewriting systems.
Background
Graphs are widely used for describing various and often complex
structures, like UML diagrams, textual representation of proofs,
microprocessor design, XML documents, communication networks, data and
control flow, neural networks, biological systems, etc., in a visual and
intuitive way. Graphical formalisms have clear advantages as modelling tools, in
particular in the earlier phases of the specification: graphical
formalisms are more intuitive and make it easier to visualise a system
and convey intuitions or ideas about it. For example, consider the
textual representation of proofs in the sequent calculus versus proof
nets, the entity-relationship diagrams that specify a relational
database versus the tables, etc.
Graph transformation:
For complex systems, in addition to providing a static
description, transformations of graphs allow the modeling of their
dynamic evolution. Computing by graph transformation is also a
fundamental concept for concurrency and distribution,
and for computational models in
general [EP05]. Different approaches have been proposed to formalize
graph transformation and applications [EEKR97, EKMR97].
From a theoretical point of view, there are solid logic, algebraic and
categorical foundations for graph rewriting [Courcelle90,CMREHL97],
and from a practical point of
view, graph transformations have many applications in specification,
programming, and simulation tools.
On the negative side, there
are some well-known implementation problems when dealing with graphical
formalisms (pattern-matching is not an easy problem, for instance), and
graph rewriting can be very inefficient if patterns have arbitrary
complexity.
We want to study graph transformations in two different highly dynamic
contexts:
interaction nets and biochemical networks.
In both case, there are interesting challenges for graph visualisation.
Interaction nets,
introduced by Lafont in 1990 [Lafont90] and used as a target language
for implementation of efficient lambda-calculus evaluators, are a
good computational solution to the complexity problems associated to
the implementation of graph transformations:
-
pattern-matching is easy in interaction nets, since patterns are graphs containing just two nodes, and
-
the transformations are local (the application of an interaction rule affects only two nodes in the graph).
|
 |
Interaction
nets are equipped with natural and efficient notion of evaluations (for
example, reduction to interface normal form [FM99]), and there are
efficient interaction net machines (running in parallel or sequential
architectures) [Pinto00]. Moreover, theories of operational equivalence
of nets are available, which can be used to justify program
optimisations [FM03]. Interaction nets are a convenient formalism when
we want to give an operational view of a system, for instance, cut
elimination in proof nets, reduction in term rewriting systems,
etc. They can be seen as a visual programming language, but no
graphical programming environment is available to support the full
software development cycle. One of the goals of this project is to
provide such an environment.
Biochemical networks
gained much interest with the recent development of large scale
distributed systems such as service infrastructures and Grids. For such
systems, there is a crucial need for theories and formal frameworks to
model computations, to define languages for programming and to establish
foundations for verifying important properties of these systems.
Several approaches contributed to this ambitious goal. Without
exhaustivity, let us mention several formalisms inspired from biology
such as [CG00, RPS+04, LT07, QLF+06] or from chemistry [BFR07]. A
graphical formalism is proposed in [BYFH06] for modeling biochemical
networks where the protein complexes are represented by typed
attributed graphs and classes of reactions are modeled by graph
transformation rules. In the same vein, the Kappa-calculus [DL04] is a
language of formal proteins which models complexes as graphs-with-sites
and their interactions as a particular graph-rewriting operation. The
theory of bigraphs proposed by Milner [Mil01,Mil06] provides a model of
computation for reactive systems where connectivity as well as locality
are important.
 |
In [BCC+03,AIK06] graph models have been designed for simulating a
chemical reactor, using rule-based systems and strategies, for the
problem of automated generation of kinetics mechanisms following the
artificial chemistry approach. Both for a chemical reactor in [AIK06]
and for modeling protein interactions in [AK07b], molecules are
represented as graphs where the nodes correspond to atoms and to
proteins respectively, and the reactions rules create or break bonds
between the nodes. In [AndreiPhD08] the port graph structure is studied,
a suitable (strategic) rewriting relation as well as an
abstract calculus have been defined on them. This formalism is powerful
enough to model biochemical applications and generation of biochemical
networks, as well as self-management properties of autonomic
systems. |
Graph visualisation:
from a naïve point of view, the output of a graph rewriting systems is
a dynamic graph: a sequence of graphs obtained through a series of
topological modifications (addition/deletion of nodes/edges). From an
Information Visualisation perspective, the challenge posed by dynamic
graphs is to design a graphical representation (drawing) that complies
with the various changes operated on a graph while offering a view that
remains readable throughout its evolution. The InfoVis literature
contains but a few results in this area. [Ellson, Gansner et al. 2003]
had already suggested an algorithm dealing with directed acyclic graphs
providing an incremental version of a Sugiyama-type layout. [Frishman
and Tal 2007] is for now the best available algorithm for drawing a
dynamic graph. Their algorithm is a modified spring embedder based on a
simple requirement: already positioned nodes should remain as stable as
possible while additional nodes are introduced in the right place.
However, one pitfall of their algorithm is that positions are decided
after all topological modifications are known, thus producing an a posteriori graphical representation of a dynamic graph.
However,
the visualisation of dynamic graphs emerging from graph rewriting
systems does not fall under the assumptions made by [Frishman and Tal
2007]. The sequence of modifications cannot be known for sure since
there might be cases where multiple rules may apply. Moreover, the
problem of determining whether the rewriting of a graph terminates is
undecidable. Incidentally, these theoretical obstacles are at the heart
of our project. The visual and interactive environment we head for
should support the study of rewriting systems, helping experts to test
hypotheses, decide or prove properties on rules or infer properties on
graphs resulting form the processing of rules.
Other
crucial issues relate to interaction. Exploring how rules operate on
graphs implicitly require the ability to backtrack and change earlier
decisions. This requires that the visual environment offers a view on
the rewriting history and eventually ways to select points back in
time. To our knowledge, the only known results for dynamic graphs do
not address these issues and do not appear as possible ingredients for
a solution to the visualisation of graph rewriting systems.
Goals
The goal of the project is to develop an environment that will allow us to:
create a graph using a visual editor;
trigger a series of transformations on the graph using graph rewriting rules to describe transformations;
display
a sequence of graphs obtained by application of transformation rules as
well as the sequence of rules underlying these transformations;
design analysis and verification tools to check static and dynamic properties of graphs.
The environment that we propose to develop
will be used to model, visualise and simulate biological systems as
well as to program using graphical languages such as interaction
nets.
Although graph editors are available, and graph rewriting machines
exist (working on textual representations of graphs), the combination
of a graphical editor with a graph transformation engine that we
propose in this project is unique.
Studying and building this environment is a first challenging step
towards goals which are even more ambitious:
Interaction nets have proved useful
as back-end compiler technology; by providing a suitable graph editor
with debugging functionalities (for instance, through the above
mentioned visualisation of transformation sequences and the analysis
tools) we hope that interaction nets and, more generally, graph-based
programming and specification languages, will also take a prominent
place as front-end compiler technology.
Autonomic computing with biologically inspired
formalisms is yet an emerging field and lacks of visual programming
language and environment. PORGY will contribute to this issue by
providing an environment for experimenting visual programming with port-graph
rewrite rules and for simulating program execution.
-
The development of this environment will be kept
consistent with the current Tulip modular architecture and principles,
so that we can benefit from the already developed tools.
Accordingly, we will provide dedicated applications for our
fields of interest, in particular for biochemical applications.
But we also aim at providing flexible and easily tunable primitives
and concepts to develop new applications.
Main tasks over the three years:
Year 1:
-
Design
of the global system: equivalent for port graphs and port graph
rewriting systems in terms of dynamic graphs, that is usual multiple
edge graphs enriched with time-stamped attributes; encoding of
rewriting rules as graph sets, design of all relevant interaction
between rewriting rules and graphs to be rewritten in pragmatic terms;
-
Design of a relevant graph drawing strategy (first iteration): need to take the dynamic aspect into account
-
Development of a prototype of the environment, including edition, graph rewriting.
Year 2:
-
Design
of a history mecanism with underlying management of the rewriting
process to allow interaction on the rewriting process: backtracking,
exploration of alternative sequence of rules;
-
Design
of a relevant graph drawing strategy (second iteration): need to take
the impact of backtracking on the possible drawing and necessary
transitions
-
Development of simulation and debugging tools.
Year 3:
- Development
of Analysis and Verification tools, including typing systems and visual
checking tools, and tools to analyse the potential for parallelism.
References
[AndreiPhD08] Oana Andrei – “Un calcul de réécriture de graphes:
applications à la biologie et aux systèmes autonomes.”, PhD thesis,
Institut National Polytechnique de Lorraine, novembre 2008.
[AIK06] Oana Andrei, Liliana Ibanescu and Hélène Kirchner –
“Non-intrusive Formal Methods and Strategic Rewriting for a Chemical
Applicationw.”, Algebra, Meaning, and Computation, Essays Dedicated to
Joseph A. Goguen on the Occasion of His 65th Birthday (K. Futatsugi,
J.-P. Jouannaud and J. Meseguer, eds.), Lecture Notes in Computer
Science, vol. 4060, Springer, 2006, p. 194–215.
[AK07b] — , “Graph Rewriting and Strategies for Modeling Biochemical
Networks.”, SYNASC '07: Proceedings of the Ninth International
Symposium on Symbolic and Numeric Algorithms for Scienti?c Computing,
IEEE Computer Society, 2007, p. 407–414.
[BCC+03] Olivier Bournez, Guy-Marie Côme, Valérie Conraud, Hélène
Kirchner and Liliana Ibanescu – “A Rule-Based Approach for Automated
Gener- ation of Kinetic Chemical Mechanisms.”, Rewriting Techniques and
Applications (RTA 2003) (R. Nieuwenhuis, ed.), Lecture Notes in
Computer Science, vol. 2706, Springer, 2003, p. 30–45.
BFR07] Jean-Pierre Banâtre, Pascal Fradet and Yann Radenac —
“Programming Self-Organizing Systems with the Higher-Order Chemical
Language”, International Journal of Unconventional Computing 3 (2007),
no. 3, p. 161–177.
[BYFH06] M. L. Blinov, J. Yang, J. R. Faeder and W. S. Hlavacek –
“Graph Theory for Rule-Based Modeling of Biochemical Networks.”,
Transactions on Computational Systems Biology VII (C. Priami, A.
Ingólfsdóttir, B. Mishra and H. R. Nielson, eds.), Lecture Notes in
Computer Science, vol. 4230, Springer, 2006, p. 89–106.
[CG00] Luca Cardelli and Andrew D. Gordon – “Mobile ambients.”, Theoretical Computer Science 240 (2000), no. 1, p. 177–213.
[CMREHL97] A. Corradini, U. Montanari, F. Rossi, H. Ehrig, R.
Heckel and M. Lowe. "Algebraic Approaches to Graph Transformations,
part 1: basic concepts and double pushout approach". Handbook of Graph
Grammars and Computing by Graph Transformations,
< Volume 1, Foundations. G. Rozenberg Ed. World Scientific, 1997.
[Courcelle]B. Courcelle, Graph rewriting: An algebraic and logic
approach. Chapter 5, Handbook of Theoretical Computer Science, Volume
B: Formal Models and Semantics. J. van Leeuwen, ed., Elsevier Science
Publishers and MIT Press, 1990.
[DL04] Vincent Danos and Cosimo Laneve – “Formal Molecular Biology.”,
Theoretical Computer Science 325 (2004), no. 1, p. 69–110.
[EEKR97] H. Ehrig, G. Engels, H.-J. Kreowski and G. Rozenberg (eds.) –
Handbook of Graph Grammars and Computing by Graph Transformations,
Volume 2: Applications, Languages, and Tools, World Scienti?c, 1997.
18, 19, 55
[EKMR97] H. Ehrig, H.-J. Kreowski, U. Montanari and G. Rozenberg (eds.)
– Handbook of Graph Grammars and Computing by Graph Transformations,
Volume 3: Concurrency, Paral lelism, and Distribution, World Scienti?c,
1997. 18, 55
[Ellson, Gansner et al. 2003] Ellson, J., E. Gansner, L. Koutsofios, S.
North and G. Woodhull (2003). Graphviz and Dynagraph - Static and
Dynamic Graph Drawing Tools. Graph Drawing Software . M. Junger and P.
Mutzel (eds) : 127-148, Springer-Verlag.
[EP05]
Hartmut Ehrig and Ulrike Prange – “Modeling with Graph Transformation”,
Advances in Multiagent Systems, Robotics and Cybernetics: Theory and
Practice. Proceedings of Intern. Conf. on Systems Research, Informatics
and Cybernetics (G. Lalsker and J. Pfalzgraf, eds.), 2005.
[FM99] M. Fernandez and I. Mackie. A Calculus for Interaction
Nets. Proceedings, Principles and Practice of Declarative Programming,
Lecture Notes in Computer Science, Springer 1999.
[FM03] M. Fernandez and I. Mackie. Operational Equivalence for
Interaction Nets. Theoretical Computer Science, Volume 297, numbers
1-3, pages 157-181, 2003.
[Frishman and Tal 2007] Frishman, Y. and A. Tal (2007). Online Dynamic
Graph Drawing . Eurographics / IEEE VGTC Symposium on Visualization
(EuroVis): 75-82.
[Lafont90] Yves Lafont. Interaction Nets. Proceedings, 17th ACM Symposium on
Principles of Programming Languages, pages 95--108, 1990.
ACM Press.
[LT07]
Cosimo Laneve and Fabien Tarissan – “A simple calculus for proteins and
cells.”, Electronic Notes in Theoretical Computer Science 171 (2007),
no. 2, p. 139–154.
[Mil01] Robin Milner— “Bigraphical
Reactive Systems.”, CONCUR (K. G. Larsen and M. Nielsen, eds.), Lecture
Notes in Computer Science, vol. 2154, Springer, 2001, p. 16–35.
[Mil06] Robin Milner — “Pure bigraphs: Structure and dynamics.”, Inf. Comput. 204 (2006), no. 1, p. 60–122.
[QLF+06] Zhengwei Qi, Minglu Li, Cheng Fu, Dongyu Shi and Jinyuan You –
“Membrane Calculus: a formal method for Grid transactions”, Concurrency
and Computation: Practice and Experience 18 (2006), no. 14, p.
1799–1809.
[RPS+04] Aviv Regev, Ekaterina M. Panina, William Silverman, Luca
Cardelli and Ehud Y. Shapiro – “BioAmbients: an abstraction for
biological compartments.”, Theoretical Computer Science 325 (2004), no.
1, p. 141–167.