Thibaut Démare - LITIS

thibaut.demare@univ-lehavre.fr

thibaut.demare@univ-lehavre.fr

GraphStream - Introduction

NeX Days' 2015

28 - 30 April 2015

28 - 30 April 2015

Thibaut Démare

LITIS - Université du Havre

NeX Days' 2015 - Agadir, Morocco

28 - 30 April 2015

- Dynamic graphs
- GraphStream
- The Event Model
- Algorithms
- Visualization
- Interactions with other tools
- Demo
- Basic Demo
- Demo of interactions with GAMA

Structure:

- Nodes, Vertices
- (undirected) Edges, Links
- (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?
- nodes and/or edges added/removed?

Problem with algorithms

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

Many graph models consider in some ways the dynamics

but they are bounded to their application domain

What about *Dynamic Graph Theory*?

**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

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.

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.

- Dynamic Algorithms
- Dynamic Visualization

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

Java library with a handy public API

```
Graph g = new SingleGraph("MyGraph");
g.read("some-file.tlp");
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

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

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

- graphstream-project.org
- official releases (v1.3) of gs-core, gs-algo, gs-ui
- nightly-builds

- github.com/graphstream
- bug tracker of gs-core

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

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.**

They produce such stream of events.

They can receive such stream of event and process it.

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

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

```
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();
```

Graph

File

Viewer

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.

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);
}
```

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.

- 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.

```
g.addAttribute("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");
```

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.*

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

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

- Dynamic Visualization: the graph is evolving, so does the visualization.
- Get
*more*information than the graph itself.

```
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');
}
```

```
graph.addAttribute("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.addAttribute("ui.class", "fun");
b.addAttribute("ui.class", "fun");
c.addAttribute("ui.class", "dull");
```

...and of course it is dynamic.

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 tunable with CSS:

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

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/

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

- 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
```

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

```
import org.graphstream.stream.netstream.NetStreamReceiver;
//...
NetStreamReceiver net = new NetStreamReceiver(2001);
ThreadProxyPipe pipe = net.getDefaultStream();
pipe.addSink(graph);
while (true) {
pipe.pump();
Thread.sleep(100);
}
```

- 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

Get the Slides and Materials on-line:

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

NeX2015)