# GraphStream

Politechnika Poznańska – April 24th 2018

# Sources

Codes and Presentations are on GitHub

# Outline

• General Presentation of GraphStream (this presentation)
• Dynamic Graphs
• GraphStream
• The Event Model
• Algorithms
• Visualisation
• Interaction with other tools
• Demonstrations and Examples

# First, static graphs

## Structure:

• Nodes, Vertices
• (undirected) Edges, Links
• (directed) Arcs

# First, static graphs

## Algorithms: Graphs Theory

• graph colouring problems
• routing problems
• flow problems
• covering problems
• sub-graphs problems

# When we add dynamics…

## What kind of dynamics?

• values/weight on edges or nodes?
• nodes and/or edges added/removed?

# When we add dynamics…

## Problem with algorithms

• As soon as it gets 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 dynamics in some ways. But they are usually bounded to their application domain.

• Is there a general-enough model that can be used in a broad range of applications?
• What about a Dynamic Graph Theory with algorithms for colouring, routing, flows, etc.?

# Complex Networks

1. Exploration: Analysis of “real world” networks (web graphs, biological networks, social networks)

2. Modelling: Build artificial networks (Barabasi-Albert, Watts-Strogatz, Dorogovtsev-Mendes, Golomb , etc.)

• Measures on graphs: community, distribution, dimensions, etc.
• Iterative Construction/Iteration: we see dynamic graphs here!

# Aggregative Methods

All the evolution is known in advance, the dynamic graph is aggregated into a static graph. (Temporal Networks, Evolving Graphs, Time-Varying Graphs, etc.)

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

# Re-optimisation

Build and maintain structures on dynamic graphs (e.g. spanning trees) without prior knowledge of the evolution.

Hypothesis: Updating an existing structure after some modifications is more effective that recomputing it from scratch.

# GraphStream

Study interaction networks and their dynamics

• Dynamic Algorithms
• Dynamic Visualisation

A free and open-Source project supported by the University of Le Havre.

# In a nutshell

A Java library with a handy public API

Graph g = new SingleGraph("MyGraph");
g.read("some-file.tlp");
System.out.println("Average Degree: "+g.getDegree());
g.display();

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

Interaction with over tools

• Offline: several import / export file formats
• Online: through the API or through a network connection

# Architecture

### Public API graphstream-project.org/doc/API

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

### Organised into sub-projects github.com/graphstream

• gs-core, gs-algo,
• gs-ui-swing, gs-ui-javafx, gs-ui-android
• gs-netstream, gs-boids, gs-netlogo, gs-geography, …

# Get GraphStream!

### On the Website

• graphstream-project.org
• legacy release (v1.3) of gs-core, gs-algo, gs-ui

### On Maven

Use any version of GraphStream with jitpack.io

<repositories>
<repository>
<id>jitpack.io</id>
<url>https://jitpack.io</url>
</repository>
</repositories>
<groupId>com.github..graphstream</groupId>
<artifactId>gs-core</artifactId>
<version>2.0</version>

# GraphStream’s Event Model

The dynamics of the graph is expressed by an event model

Events

• 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

Produce streams of events.

### Sinks

Receive streams of events.

### Pipes

Both source and sink. A graph is a pipe.

# Pipelining

Sources send events to sinks.

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

Sources, pipes and sinks can be connected to form pipelines.

# Pipelining

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

# Pipelining

The stream of events can flow between sources and sinks:

• across the network,
• processes,
• threads.

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

# Pipelining

Receive events from another some other process/thread/programme/machine

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

while (true) {
pipe.pump();
Thread.sleep(1);
}

# Graph components

### Various graph structures

• Single graph (1-graph),
• Multi-graph (p-graph), graphs where several edges can connect two given nodes.
• Directed and/or 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 key, value pair that can be any Java Object.
• You can place attributes on nodes, edges and on the graph itself.
g.setAttribute("My attribute", aValue);
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

### 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();
}

# Algorithms

Some tutorials to go further

graphstream-project.org/doc/Algorithms/

# Visualization

1. Dynamic Visualization: the graph is evolving, so does the visualization.
2. Get more information than the graph itself: sprites.

# Extra visual information

## CSS

graph { padding: 50px; }
node {
size-mode: fit; shape: rounded-box;
fill-color: white; stroke-mode: plain;
padding: 5px, 4px; icon-mode: at-left;
icon: url('data/Smiley_032.png');
}

# Extra visual information

## CSS classes

graph.setAttribute("stylesheet",
"graph {padding : 50px;}"
+ "node {size: 100px; fill-mode: image-scaled;}"
+ "node.fun {fill-image: url('fun.gif');}"
+ "node.dull {fill-image: url('dull.png');}");

Node a = graph.addNode("A");
Node b = graph.addNode("B");
Node c = graph.addNode("C");
graph.addEdge("AB", "A", "B");
graph.addEdge("CB", "C", "B");
graph.addEdge("AC", "A", "C");
a.setAttribute("ui.class", "fun");
b.setAttribute("ui.class", "fun");
c.setAttribute("ui.class", "dull");

# Extra visual information

## Sprites

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

SpriteManager sman = new SpriteManager(graph);
Sprite pin = sman.addSprite("pin");

Sprites are also customised with CSS

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

# Offline interactions

### File formats

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

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

# OnLine 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)

# NetLogo Extension

• NetLogo agents (turtles, links and observer) 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 NetLogo
• Agents can receive and use them to take their decisions