LaBRI/INRIA GRAVITÉ Team
Locations of visitors to this page
September 2009
<<     >>
Mon Tue Wed Thu Fri Sat Sun
  1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30  
Username

Password

Remember Me!
Welcome on GRAVITÉ's web site > Projects / Grants > Porgy > Scientific objectives

Scientific objectives



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.