# Working with algorithms and generators

## Algorithms

We see algorithms like something which can be initialized on a graph and then computed. For example, an algorithm can colorize nodes or edges of a graph ; an other can compute a spanned tree …

The `org.graphstream.algorithm.Algorithm` interface defines the structure of an algorithm. It contains two methods :

• `init( Graph g )`, which is the initialization step of the algorithm ;
• `compute()`, which launches the algorithm.

### Why does we not just use a `compute(Graph)` method ?

The initialization step and computing step are located in different methods because you may have to make a new computation of your algorithm without calling the initialization step again. This initialization step must contain code which is unique for a graph and it has to be called again only if you want to reset data linked to the algorithm or to change the graph.

This is a good way to use algorithm:

`````` Graph g = ... ;

// Creation of the graph

Algorithm a = ... ; // My algorithm
a.init(g);
a.compute();

// Others operations on g

a.compute(); // Update results
``````

### A basic algorithm example

The following is an example of a basic algorithm that computes min, max and average degree in the graph:

`````` public class DegreesAlgorithm implements Algorithm {
Graph theGraph;
int minDegree, maxDegree, avgDegree;

public void init(Graph graph) {
theGraph = graph;
}

public void compute() {
avgDegree = 0;
minDegree = Integer.MAX_VALUE;
maxDegree = 0;

for(Node n : theGraph.getEachNode() ) {
int deg = n.getDegree();

minDegree = Math.min(minDegree, deg);
maxDegree = Math.max(maxDegree, deg);
avgDegree += deg;
}

avgDegree /= theGraph.getNodeCount();
}

public int getMaxDegree() {
return maxDegree;
}

public int getMinDegree() {
return minDegree;
}

public int getAverageDegree() {
return avgDegree;
}
}
``````

### Dynamicity

On GraphStream, dynamicity is at the foreground so it is normal that algorithms can be dynamic to. The interface `org.graphstream.algorithm.DynamicAlgorithm` extends `Algorithm` and introduces a new method `terminate()` which defines the end of the algorithm.

Use of this kind of algorithms could be:

`````` Graph g = ... ;

// Creation of the graph

DynamicAlgorithm da = ... ;

da.init(g);

while( ... ) // something to do
da.compute();

da.terminate();
``````

### A basic dynamic algorithm example

In this example, computation is done continuously in a loop. One may want to make the computation when receiving events. This can be done with a Sink that will trigger the computation. For example, this is a dynamic algorithm where computation is done when a node is added:

`````` public class ApparitionAlgorithm extends SinkAdapter implements
DynamicAlgorithm {

Graph theGraph;
HashMap<String, Integer> apparitions;
double avg;

public void init(Graph graph) {
theGraph = graph;
avg = 0;
}

public void compute() {
avg = 0;

for (int a : apparitions.values())
avg += a;
avg /= apparitions.size();
}

public void terminate() {
graph.removeSink(this);
}

public double getAverageApparitions() {
return avg;
}

public int getApparitions(String nodeId) {
return apparitions.get(nodeId);
}

public void nodeAdded(String sourceId, long timeId, String nodeId) {
int a = 0;

if (apparitions.containsKey(nodeId))
a = apparitions.get(nodeId);

apparitions.put(nodeId, a + 1);
}

public void stepBegins(String sourceId, long timeId, double step) {
compute();
}
}
``````

In this last example, `init(..)` is use to set a link between the graph and the algorithm and `end()` removes this link.

## Generators

A generator is an algorithmic source of events that produce a graph according to criteria. Generators are composed of :

1. a `begin()` method that is called one time at the beginning,
2. a `nextEvents()` that produces some new events and that can be called as much as more events are available,
3. a `end()` method that closes the generation.

A trivial example is a generator producing a full connected graph that adds a new node at each iteration and connects it with all previous nodes.

Generator is a Source, so transmission of events is done in the classic Source/Sink way:

`````` Generator gen = ...;
Graph graph = ...;

gen.begin();
for(int i = 0; i < 100; i++)
gen.nextEvents();
gen.end();
``````

You can have a look on the overview on generators on this page.

### A basic generator example

A basic full generator can be created easily :

`````` public class MyFullGenerator extends SourceBase
implements Generator {

int currentIndex = 0;
int edgeId = 0;

public void begin() {
}

public boolean nextEvents() {
return true;
}

public void end() {
// Nothing to do
}