Section: Software

Grph

Participants : Nathann Cohen, David Coudert, Luc Hogie [correspondant] , Aurélien Lancin, Grégory Morel, Issam Tahiri.

Around 20,000 lines of code, developed in Java.

The Grph project takes over Dipergrafs which was introduced in the activity report of 2010. A drastic change in the model of Dipergrafs justified the name change.

The objective of Grph is to provide researchers and engineers a suitable graph library for graph algorithms experimentation and network simulation. Grph is mainly a software library, but it also comes with a set of executable files for user interaction and graph format conversion; as such, it can be used autonomously. Performance and accessibility are the primary targets of the Grph library. At every stage, it is designed to be efficient in terms of: computation time (use of parallelism, caching, adequate data structures, native code, etc.); memory requirements (use of Java primitives); and portability (it is written in a Java and C). Its model considers mixed graphs composed of (un)directed simple- and hyper-edges. It can handle large dynamic graphs in the order of millions of nodes. Grph comes with a collection of base graph algorithms which are regularly augmented.

So far, most known users of the Grph library are part of INRIA and of the FP7 STREP EULER project. Grph is distributed under the terms of a license defined by its contributors and is available for download. This license allows free usage and access to the source code. See http://www-sop.inria.fr/mascotte/software/grph .

In 2011, Grph was augmented over Dipergrafs of a number of features suited to its usage within the Mascotte research team. These include: addition of numerous graph manipulation methods; introduction of an incidence-list data structure for the representation of graphs; introduction of an adaptive data structure for the representation of sets (based on hash-tables and bit-vectors); integration of implementations of "maximum clique" and "sub-graph isomorphism" algorithms by Christine Solnon (CNRS, INSA Lyon). These sources, written in C, are compiled on-the-fly; integration of implementation of "graph isomorphism" algorithm by Brendan McKay (Australian National University); iteration of implementation of "number of triangles" algorithm by Matthieu Latapy (LIP6); introduction of a bridge to the Mascopt/OpenGVE library; introduction of a bridge to the JUNG library; addition of numerous graph algorithms; introduction of a new layer atop Grph which allows the representation and manipulation of graph as Java objects, like it is done in other libraries such as Mascopt, Jung, etc.; introduction of an efficient mechanism for the definition of graph properties; addition of graph reporting facilities.

On-going works concern the distributed execution of graph algorithms, a bridge to Sage, and the graphical edition of graphs.