GraphStream

Modeling Interaction Networks
Using Dynamic Graphs

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

LITIS — University of le Havre

Outlook



  • GraphStream's principles and capabilities

    • The dynamic graph model
    • Algorithms from Graph Theory
    • Viewing capabilities
  • Example applications

    • A simple graph example
    • A dynamic graph example
    • Geographical data visualization
    • Working on geographical data

GraphStream

Modeling interaction networks using dynamic graphs.

GraphStream

Graph components

GraphStream

Graph components

GraphStream

The event model

GraphStream

The event model

  • Some components of GraphStream can produce such a stream of events. We call them Sources.
  • Some components can receive this stream of event to process it, we call them Sinks.
  • Some components are both source and sink, we call them Pipes.
  • A graph is a pipe.
Source
Sink
Pipe

GraphStream

Pipelining

File Graph Viewer

GraphStream

Pipelining

The stream of events can flow between sources and sinks:

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

Algorithms, metrology and generators

Various ways to operate on graphs

Algorithms:
  • observe and modify the graph and its dynamics.
  • Random Walks, Shortest paths, Spanning Trees, etc.
Metrology algorithms:
  • extract data from the graph and its dynamics.
  • Modularity, Centrality, Degree distribution, Connected components, etc.
Generators:
  • create graphs according to a model or from specific data.
  • Random, Preferential attachment, Small World, From GIS data, etc.

Graph Views

Several views on a graph or stream of graph event

View on data, metrology

  • Metrics allow to observe the graph and collect data during its evolution.

Graphical views

  • A rendering engine using CSS allows to represent graphs on screen.
  • The CSS allows to specify colors, sizes, shapes, images, labels, and interactive behaviour for nodes, edges and the graph itself.
  • A data rendering system based on symbols that can be attached to nodes or edges, or float anywhere on the drawing surface allows to render data attributes and to animate them.


Connection with other tools

GraphStream and simulations

GraphStream can be used...

Installation

We will be using eclipse to test GraphStream:

  1. You can find the files needed to work on the tutorial by connecting to the GraphStream Wi-Fi network.
  2. Open a web browser and go to the http://graphstream.local page.
  3. Download the eclipse package for your OS.
  4. Uncompress it in a place of your choice.
  5. Download the TutorialECSS2011.zip.
  6. Uncompress it in a place of your choice, this should create a TutorialECSS2011 directory.

Installation

The base code for the tutorials is available in a "workpace" for eclipse:

  1. Open the eclipse folder you uncompressed previously and launch eclipse.
  2. When it asks for a work space, browse the file system to select the TutorialECSS2011 folder then click OK.

Installation

  1. You should see eclipse appear with at the left the four parts of the tutorial.

Tutorial 1

Basic tasks with GraphStream

Tutorial 1: basis tasks with GS

Creating a basic graph and displaying it

Open Tutorial1 > src > eccs2011 > Tutorial1.java:

import org.graphstream.graph.*;
import org.graphstream.graph.implementations.*;

public class Tutorial1 {
	public static void main(String args[]) {
		Graph graph = new SingleGraph("Tutorial 1");
		
		graph.display();
		
		graph.addNode("A");
		graph.addNode("B");
		graph.addEdge("AB", "A", "B");
		graph.addNode("C");
		graph.addEdge("BC", "B", "C", true); // Directed edge.
		graph.addEdge("CA", "C", "A");
	}
}

Tutorial 1

Basic tasks with GS

We can improve the display with some CSS:

...
graph.display();

graph.addAttribute("ui.quality");
graph.addAttribute("ui.antialias");
graph.addAttribute("ui.stylesheet",
	"edge { fill-color: grey; }");

graph.addNode("A");
...

Tutorial 1

Basic tasks with GS

Tutorial 1

Basic tasks with GS

Tutorial 1

Basic tasks with GS

Edge ab = graph.getEdge("AB");
Edge bc = graph.getEdge("BC");
Edge ca = graph.getEdge("CA");

ab.setAttribute("ui.label", "AB");
bc.setAttribute("ui.label", "BC");
ca.setAttribute("ui.label", "CA");

Tutorial 1

Basic tasks with GS

ab.setAttribute("aNumber", 10);
bc.setAttribute("anObject", new Double(10));
ca.setAttribute("anArrayOfThings", 1, 2, 3);

Tutorial 1

Basic tasks with GS

int value1 = ((Number) ab.getAttribute("aNumber")).intValue();
double value2 = bc.getAttribute("anObject");
Object[] value3 = ca.getAttribute("anArrayOfThings");

double value4 = ab.getNumber("aNumber");
double value5 = bc.getNumber("anObject");

Tutorial 1

Basic tasks with GS

for(Node n: graph) {
	System.out.println(n.getId());
}

for(Edge e: graph.getEachEdge()) {
	System.out.println(e.getId());
}

Tutorial 1

Basic tasks with GS

Iterator<? extends Node> nodes = graph.getNodeIterator();

while(nodes.hasNext()) {
	System.out.println(nodes.next().getId());
}

Iterator<? extends Edge> edges = graph.getEdgeIterator();

while(edges.hasNext()) {
	System.out.println(edges.next().getId());
}		

Tutorial 1

Basic tasks with GS

import static org.graphstream.algorithm.Toolkit.*;
...
Node node = randomNode(graph);

for(Edge e: node.getEachEdge()) {
	System.out.printf("neighbor %s via %s%n",
		e.getOpposite(node).getId(),
		e.getId() );
}

Tutorial 1

Basic tasks with GS

Node node = getRandomNode(graph);
Iterator<? extends Edge> edges = node.getLeavingEdgeIterator();

Iterator<? extends Edge> edges = node.getEnteringEdgeIterator();

System.out.println(“Node degree %d (entering %d, leaving %d)%n”,
	node.getDegree(),
	node.getInDegree(),
	node.getOutDegree());

Tutorial 2

A first dynamic graph

Tutorial 2

A first dynamic graph

Tutorial 2

A first dynamic graph

An element sink must follow the interface:

public interface ElementSink {
	void nodeAdded( ... );
	void nodeRemoved( ... );
	void edgeAdded( ... );
	void edgeRemoved( ... );
	void graphCleared( ... );
	void stepBegins( ... );
}

Tutorial 2

A first dynamic graph

An attribute sink must follow the interface:

public interface AttributeSink {
	void graphAttributeAdded( ... );
	void graphAttributeChanged( ... );
	void graphAttributeRemoved( ... );

	void nodeAttributeAdded( ... );
	void nodeAttributeChanged( ... );
	void nodeAttributeRemoved( ... );

	void edgeAttributeAdded( ... );
	void edgeAttributeChanged( ... );
	void edgeAttributeRemoved( ... );
}

Tutorial 2

A first dynamic graph

A source is an interface that only defines methods to handle a set of sinks.

public interface Source {
	void addSink(Sink sink);
	void removeSink(Sink sink);
	void addAttributeSink(AttributeSink sink);
	void removeAttributeSink(AttributeSink sink);
	void addElementSink(ElementSink sink);
	void removeElementSink(ElementSink sink);
	void clearElementSinks();
	void clearAttributeSinks();
	void clearSinks();
}

Tutorial 2

A first dynamic graph



These three interfaces are the most important of GraphStream.

Tutorial 2

A first dynamic graph

Tutorial 2

A first dynamic graph

A DGS file looks like this. You can find it in the Tutorial2 > tutorial2.dgs

DGS003
"Tutorial 2" 0 0
an "A"
an "B"
an "C"
ae "AB" "A" "B"
ae "BC" "B" "C"
ae "CA" "C" "A"
ce "AB" label="AB"
ce "BC" label="BC"
ce "CA" label="CA"
  • an add a node and ae an edge.
  • ae "AB" "A" > "B" adds a directed edge.
  • cn, ce and cg change or add one or more attributes on a node, edge or graph.
  • dn and de allow to remove nodes, edges.

Tutorial 2

A first dynamic graph

Tutorial 2

A first dynamic graph

st 2
an "D"
an "E"
ae "BD" "B" "D"
ae "CE" "C" "E"
ae "DE" "D" "E"
de "AB"
dn "A"
st 3

Tutorial 2

A first dynamic graph

graph.read("tutorial2.dgs");

Tutorial 2

A first dynamic graph

public class Tutorial2 {
	public static void main(String args[]) {
		Graph graph = new SingleGraph("Tutorial2");
		graph.display();
		graph.addAttribute("ui.antialias");
		try {
			FileSource source = FileSourceFactory.sourceFor(
				"tutorial2.dgs");
			source.addSink(graph);
			source.begin("tutorial2.dgs");
			while(source.nextEvents());
			source.end();
		} catch(Exception e) { e.printStackTrace(); }
	}
}

Tutorial 2

A first dynamic graph

			while(source.nextEvents()) { Thread.sleep(1000); }

Tutorial 2

A first dynamic graph

an "A" x=0 y=1
an "B" x=1 y=-1
an "C" x=-1 y=-1

an "D" x=1 y=1 
an "E" x=-1 y=1

Tutorial 2

A first dynamic graph

		graph.display(false);

Tutorial 3

Geographic simulation and visualization

Tutorial 3

Geographic simulation and visualization

Goals:

Tutorial 3

Geographic simulation and visualization

The data models a part of the road network for the city of Le Havre.

Tutorial 3

Loading and viewing the data

We will start with: tutorial3/src/eccs211/LeHavre.java

		public class LeHavre {
			public static void main(String args[]) {
				new LeHavre();
			}
			public LeHavre() {
				Graph graph = new MultiGraph("Le Havre");
				try {
					graph.read("LeHavre.dgs");
				} catch(Exception e) {
					e.printStackTrace();
					System.exit(1);
				}
				graph.display(false);   // No auto-layout.
			}
		}

Tutorial 3

Loading and viewing the data

Tutorial 3

Adding style

Let's add some style !

We will use a style-sheet that instructs the viewer to hide the edge labels.

edge {
	text-mode: hidden;
}

This reads: for each edge, apply the property text-mode with value hidden.

Tutorial 3

Adding style

The style sheet is already present in the workspace under the name stylesheet1.css. You can open it with eclipse if you wish.

Add the following code before graph.display(false):

graph.addAttribute("ui.stylesheet", "url(file:stylesheet1.css)");
graph.display(false);

Tutorial 3

Adding style

Better, but not quite there yet:

Tutorial 3

Adding style

node {
    size: 3px;
    fill-color: #777;
    z-index: 0;
}
edge {
    shape: line;
    fill-color: #222;
    arrow-size: 3px, 2px;
    text-mode: hidden;
}

Tutorial 3

Adding style

This stylesheet is in stylesheet2.css change it, line 24.

Tutorial 3

Style classes

We can selectively change the appearance of elements using CSS classes. Here we will color some of the intersections in red or green depending on the traffic lights. To this end, we will:

Tutorial 3

Style classes

Just before graph.addAttribute(... add:

for(Node node: graph) {
	if(node.hasAttribute("tl")) {
		if(Math.random()>0.5)
		     node.addAttribute("ui.class", "red");
		else node.addAttribute("ui.class", "green");
	}
}

If the node has the attribute tl we add the special attribute ui.class that defines a styling class for the node. Node styles classes add (or replace) styling properties for nodes.

Tutorial 3

Style classes

We also need to define the styling classes in the style sheet. The changes are provided in the stylesheet3.css:

node.red {
	fill-color: red;
	size: 5px;
}
node.green {
	fill-color: green;
	size: 5px;
}

For example node.red reads: for all nodes having the class 'red'.

Tutorial 3

Style classes

With style classes you can assign a particular appearance to one or a set of nodes or edges, and change them dynamically using attributes:

Tutorial 3

Data dependant styling

Sometimes, you want to change the appearance of elements depending on numbers associated to elements.

→ For example color each edge depending on its maximal legal speed.

It would be tedious to define a class for each speed.

→ Instead you can use dynamic styles.

Dynamic styles are styles whose rendering depends on a given attribute stored on elements.

Tutorial 3

Data dependant styling

We first change the edge style to use dynamic coloring, and define a palette of colors, not only one (the changes are on lines 8 and 9). This stylesheet is in the file stylesheet4.css.

edge {
    shape: line;
    fill-mode: dyn-plain;
    fill-color: #222, #555, green, yellow;
    arrow-size: 3px, 2px;
    text-mode: hidden;
}

Tutorial 3

Data dependant styling

We will need to process each edge, after the loop on nodes, add:

for(Edge edge: graph.getEachEdge()) {
	double speedMax = edge.getNumber("maxspeed") / 28.0;
	edge.setAttribute("ui.color", speedMax);
}

The speed is stored in meters per second in the file, the maximum speed being 27.78 m/s.

We use the ui.color attribute to store a number between 0 and 1 indicating a color in the palette defined in the style. 0 means the first color, 1 the last color, and numbers in between an interpolated color in the palette.

Tutorial 3

Data dependant styling

This is fully dynamic: imagine coloring the edges depending on the current flow of vehicles of a simulation for example.

Tutorial 3

Adding symbols on the map

GraphStream provides a notion of symbols that can be placed anywhere on the rendering, or attached to nodes or edges, that we call sprites.

Let place some pins on the map ! We will:

Tutorial 3

Adding symbols on the map

First, we will need another graph viewer, that supports more graphic styles.

GraphStream provides a simple, portable and small viewer by default. A more powerfull but larger viewer is available, depending on the needs.

We can do this by adding:

System.setProperty("gs.ui.renderer",
      "org.graphstream.ui.j2dviewer.J2DGraphRenderer");

This is already done, with a recap of all the operations done above (minus the traffic lights) in the file LeHavre2.java.

Tutorial 3

Adding symbols on the map

We will fist add the sprites on the map, just after the loops on edges (this is already in the file LeHavre2.java):

SpriteManager sman = new SpriteManager(graph);

Sprite s1 = sman.addSprite("S1");
Sprite s2 = sman.addSprite("S2");

Node n1 = randomNode(graph);
Node n2 = randomNode(graph);

s1.attachToNode(n1.getId());
s2.attachToNode(n2.getId());

Tutorial 3

Adding symbols on the map

We will also need to define the appearance of sprites, we will use a pin image (stylesheet5.css). The image is provided in the workspace:

sprite {
	shape: box;
	size: 22px, 72px;
	fill-mode: image-scaled;
	fill-image: url('mapPin.png');
}

Tutorial 3

Adding symbols on the map

Tutorial 3

Finding a shortest path

Now that we have two random points in the map, lets try to find a shortest path between the two.

→ GraphStream provides an implementation of the famous Dijkstra algorithm for this.

Tutorial 3

Finding a shortest path

Let start with a new Dijkstra algorithm instance, add this at the end, after graph.display():

Dijkstra dijkstra1 =
    new Dijkstra(Dijkstra.Element.edge, "weight", n1.getId());
dijkstra1.init(graph);
dijkstra1.compute();

The Dijkstra algorithm is created considering informations on edges, and looking at their weight attribute to find the shortest path from start node n1.

Tutorial 3

Finding a shortest path

Path path1 = dijkstra1.getShortestPath(n2);

for(Edge edge: path1.getEdgePath()) {
	edge.addAttribute("ui.class", "shortesttime");
}

Then we get the computed path, and process each edge of the path to change their visual appearance, as defined in the stylesheet6.css (change it in the code).

Tutorial 3

Finding a shortest path

Tutorial 3

Finding a shortest path

Exercice: copy exactly the same code, but instead of using the weight attribute on edges, use the length attribute.

You have a predefined CSS class named shortestlength to highlight the new path in another color.