A Dynamic Graph Library

Politechnika Poznańska – April 24th 2018


Codes and Presentations are on GitHub

Sources for Codes and Presentations
Sources for Codes and Presentations


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

First, static graphs


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

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?
Weighted Network
Weighted Network

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.
Time-Varying Network
Time-Varying Network

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.

Aggregative Methods
Aggregative Methods


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.



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

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


Public API

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

Organised into sub-projects

  • 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

On Github

On Maven

Use any version of GraphStream with

GraphStream’s Event Model

The dynamics of the graph is expressed by an event model


  • 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


Produce streams of events.


Receive streams of events.


Both source and sink. A graph is a pipe.


Sources send events to sinks.

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

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

Example Pipeline
Example Pipeline


File-Graph-Viewer Pipeline
File-Graph-Viewer Pipeline


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.

Proxy Pipe
Proxy Pipe


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

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.



random searches, shortest paths, spanning trees, etc.


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


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

Focus on Dynamic Connected Components

Focus on Dynamic Shortest Paths


Some tutorials to go further


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


Extra visual information



Extra visual information

CSS classes

Extra visual information

CSS classes

…and of course it is dynamic.
…and of course it is dynamic.

Extra visual information


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

Sprites are also customised with CSS pin


Interactions with other Tools

Offline interactions

File formats

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

OnLine interactions


  • 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
NetLogo Extension
NetLogo Extension