# Dynamic Graphs and a tool to handle them

## The GraphStream library

Thibaut Démare
LITIS - Université du Havre
NeX Days' 2015 - Agadir, Morocco
28 - 30 April 2015

## Overview

1. Dynamic graphs
2. GraphStream
3. The Event Model
4. Algorithms
5. Visualization
6. Interactions with other tools
7. Demo
1. Basic Demo
2. Demo of interactions with GAMA

# Dynamic graphs

## First, static graphs

Structure:

• Nodes, Vertices
• (directed) Arcs

Algorithms: Graphs Theory

• graph colouring problems
• routing problems
• flow problems
• covering problems
• subgraphs problems

What kind of dynamics?

• values/weight on edges or nodes?

Problem with algorithms

• As soon as computed the result has vanished.
• Can we stop the graph and recompute?
• Depends on the dynamic graph model.

## Dynamic Graph Models

Many graph models consider in some ways the dynamics

but they are bounded to their application domain

## Complex Networks

Exploration: analysis of "real world" networks (web graphs, biological networks, social networks)

Modelling: build artificial networks (preferential attachment)

Measures on graphs: community, distribution, dimensions, etc.

Iterative Construction/Iteration: graphs' dynamics

## Aggregative Methods

All the evolution is known in advance, the dynamic graph is aggregated into a static graph.

Why? Because it allows the use of classical graph theory.

## Re-optimisation

Build and maintain structures on dynamic graphs (e.g. spanning trees).

Updating an existing structure after some modifications is more effective than recomputing it from scratch.

# GraphStream

## GraphStream

### Study interaction networks and their dynamics

• Dynamic Algorithms
• Dynamic Visualization

• Stefan Balev
• Antoine Dutot
• Yoann Pigné
• Guilhelm Savin

## In a nutshell

Java library with a handy public API

``````
Graph g = new SingleGraph("MyGraph");
g.getDegree();
g.display();
``````

Based on an event model: Nodes and Edges are Added/Removed/Modified

Interaction with over tools

• Off-line: several import / export file formats
• On-line: through the API or through a network connection

## Architecture

### Public API

• org.graphstream
• .graph
• .stream
• .ui
• .algorithm
• .util

• gs-core
• gs-algo
• gs-ui
• gs-netstream
• gs-gama
• gs-netlogo
• gs-geography

## Get GraphStream!

### On Maven

``````
<groupId>org.graphstream</groupId>
<artifactId>gs-core</artifactId>
<version>1.2</version>
``````

# The Event Model

## GraphStream's Event Model

The dynamics of the graph is expressed by an event model

Events can be:

• Addition or removal of nodes
• Addition or removal of edge
• Addition, update or removal of data attributes
• Time steps

A stream of events modifies the structure of a graph.

## GraphStream's Event Model

### Sources

They produce such stream of events.

### Sinks

They can receive such stream of event and process it.

### Pipes

They are both source and sink. A graph is a pipe.

## Pipelining

Sources send their events to sinks.

• Observer design pattern
• Publish / Subscribe
• Java Swing listeners

Sources, pipes and sinks can be connected in a pipeline of elements.

Example of an often used pipeline:

Graph

File

Viewer

## Pipelining

``````
Graph graph = new SingleGraph("Some Graph");
graph.display();
FileSource source = new FileSourceDGS();
source.begin("someFile.dgs");
while( source.nextEvents() ){
// Do whatever between two events
}
source.end();
``````

Graph

File

Viewer

## Pipelining

The stream of events can flow between sources and sinks:

• across the network,
• processes,

For example a viewer can run in a distinct thread or machine, while a simulation on a graph runs on another.

## Pipelining

``````
Graph g = new SingleGraph("RWP");
ThreadProxyPipe pipe = getPipeFromElsewhere(); //fake function
g.display(false);

while (true) {
pipe.pump();
}
``````

## Graph components

Several classes for various graph structures.

• "Single" graphs (1-graph), "multigraphs" (p-graphs, that are graphs where several edges can connect two nodes).
• Directed, undirected graphs.

Several internal representations:

• fast data retrieval,
• data compactness.

Representation of a graph at a given time (static). But this representation can evolve.

## Data Attributes

• Any number of data attributes can be associated with any element of the graph.
• An attribute is made of an identifier and a value that can be any Java Object.
• You can place attributes on nodes, edges and on the graph itself.
``````
Node n = g.getNode("A");
n.setAttribute("xy", 23.4, 55.0);
Edge e = g.getEdge("AB");
e.removeAttribute("selected");
double w = e.getNumber("weight");
``````

# Algorithms

## Main Algorithms

### Searches

random searches, shortest paths, spanning trees, etc.

### Metrics

modularity, centrality, degree distributions, connectivity, density, etc.

### Generators

random, regular, preferential attachment, small world, from GIS, from the web, etc.

## Focus on Dynamic Connected Components

``````
import org.graphstream.algorithm.ConnectedComponents;
//...
ConnectedComponents cc = new ConnectedComponents();
cc.init(graph);
while(something) {
cc.getConnectedComponentsCount();
canDoSomethingWithGraph();
}
``````

## Focus on Dynamic Shortest Paths

``````
import org.graphstream.algorithm
.networksimplex.DynamicOneToAllShortestPath;
//...
DynamicOneToAllShortestPath algorithm =
new DynamicOneToAllShortestPath(null);
algorithm.init(graph);
algorithm.setSource("0");
while(something) {
algorithm.compute();
canDoSomethingWithGraph();
}
``````

# Visualization

## Visualization

### Aims

• Dynamic Visualization: the graph is evolving, so does the visualization.

## Extra visual information

### CSS

``````
graph {
}
node {
size-mode: fit; shape: rounded-box;
fill-color: white; stroke-mode: plain;
icon: url('data/Smiley_032.png');
}
``````

## Extra visual information

### CSS classes

``````
+ "node {size: 100px; fill-mode: image-scaled;}"
+ "node.fun {fill-image: url('fun.gif');}"
+ "node.dull {fill-image: url('dull.png');}");

``````

## Extra visual information

### CSS classes

...and of course it is dynamic.

## Extra visual information

### Sprites

Graphical objects that give extra information on the application you deal with.

``````
SpriteManager sman = new SpriteManager(graph);
``````

Sprites are also tunable with CSS:

``````
sprite#pin {
shape: box;
size: 32px, 52px;
fill-mode: image-scaled;
fill-image: url('mapPinSmall.png');
}
``````

## Extra visual information

### Some tutorials to go farther:

The CSS specification :
http://graphstream-project.org/doc/Tutorials/GraphStream-CSS-Reference_1.2/

A thorough tutorial on visualization:
http://graphstream-project.org/doc/Tutorials/Graph-Visualisation_1.1/

# Interactions with other tools

## Off-line interactions

• Tulip
• Gephi
• GML
• Pajek
• DOT
• LGL
• ncol
• DGS

### DataBase(s)

• Neo4J
``````
DGS004
"graph.dgs" 0 0
an A x:1 y:2.3 label:"Node A"
an B x:0 y:0
an C xy:2.3,1
an D xyz:1,1
ae AB A B weight:23.3
ae AC A C weight:2
st 1.0
ae BC B > C
ae BD B > D
st 1.1
dn B
``````

## On-line interactions: NetStream

• Export streams of events to other applications / machines / languages
• Both ways. From GS to other and from other to GS
• Binary network protocol
• TCP socket (and WebSocket) implementation
• Several languages (Java, C++, Python, JS)
``````
//...
while (true) {
pipe.pump();
}
``````

## GAMA and NetLogo Extension

• GAMA and NetLogo agents send graph events to external application
• The external application maintains a dynamic graph and runs algorithms on it
• It sends the computed results back to GAMA or NetLogo
• Agents can receive and use them to take their decisions

## Slides and Material

Get the Slides and Materials on-line:

https://github.com/graphstream/gs-talk/tree/NeX2015 (branch
`NeX2015`
)