...and a tool to handle them

*Simtools Workshop*

Paris, June 5^{th} 2013

- Dynamic Graphs
- GraphStream
- The Event Model
- Algorithms
- Search, Metrics, Generators
- Focus on
*Dynamic Connected Components*&*Dynamic Shortest Paths*

- Visualisation
- Layout, Sprites, Style Sheets

- Realtime Interaction (NetStream)
- with NetLogo, with Gephi, and more...

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 that recomputing it from scratch.

- Dynamic Algorithms
- Dynamic Visualisation

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

Java library with a handy public API

Graph g = new DefaultGraph("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

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

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

- gs-core
- gs-algo
- gs-ui
- gs-netstream
- gs-deps
- gs-boids
- gs-netlogo
- gs-geography

- graphstream-project.org
- official releases (v1.1) 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.1</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.

Source

Sink

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:

File

Graph

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

File

Graph

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 tuneable 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.0/

A thorough tutorial on visualisation:

http://graphstream-project.org/doc/Tutorials/Graph-Visualisation_1.0/

**Interactions**

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

- 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

GraphStream is co-mentoring a *Google Summer of Code* project with *André Panisson* along with the *Gephi consortium*.

- Purpose : promote interactions between the 2 platforms.
- Communication enabled with NetStream & Gephi's Graph Streaming API.

Get the Slides and Materials online:

http://graphstream-project.org/doc/Tutorials/Lab-Sessions/Simtools-2013/