In this tutorial we will learn how to use some basic and often used algorithms on graph instances.
Algorithm, algorithms
There are two kinds of algorithms in GraphStream :
- stand-alone algorithms implemented by one or more classes ;
- and a set of simple and often used algorithms that come in a single class.
We will explore here this second set of algorithms.
But why putting these algorithms in one single class ? The idea is to provide them easily and quickly at any time where a Graph instance is used. Therefore an instance of this class can be obtained from any Graph instance using the algorithm() method. For example :
Graph g = new DefaultGraph(); Node n = g.algorithm().getRandomNode()
You may have noticed that in fact Algorithms is not a class but an interface. The idea with this interface and the Graph.algorithm() method is to provide an Algorithms implementation that best suits the Graph implementation.
Indeed some Graph implementations use specific techniques to store the graph in memory and some algorithms can take advantage of this. Therefore, for these highly important and often used algorithms the Algorithms implementation can be modified to provide ad-hoc methods.
An example of this is the Algorithms.getRandomNode() method illustrated above. For some Graph implementations fetching a random node can be done in O(1), while for others it must be done in O(n). If would be a shame to always take the default implementation in O(n) when one in O(1) is possible !
Therefore in the future the Algorithms interface may be extended, but only to provide very general and simple algorithms. Others will be implemented as stand alone classes that work on the general Graph interface, not the underlying implementation.
The available algorithms via Graph.algorithm()
Random node
Node Algorithms.getRandomNode()
This simply returns a node picked at random in the graph.
Degree distributions
int[] Algorithms.getDegreeDistribution()
The degree distribution tells home many nodes have which degree. The returned array contains the number of nodes having a degree equal to the index of the array cell. For example the value at index 0 in the array gives the number of nodes without edges. The value at index 6 gives the number of nodes having degree 6. The length of the array minus one gives the degree maximum seen in the graph.
Average degree
float Algorithms.getAverageDegree()
The average of all the nodes degrees.
Degree average deviation
float Algorithms.getDegreeAverageDeviation()
Deviation from the average degree.
Density
float Algorithms.getDensity()
The density is the ratio "number of edges" / "maximum number of edges". A graph with the same nodes, each having an edge toward each other node is a complete graph. This is the ratio between the actual number of edges and the number of edges of this complete graph.
Modularity
float Algorithms.modularity(String)
The modularity idea is to give an indicator on how the graph is structured in "communities". A community can be described as a set of nodes more densely connected one to another than with the rest of the graph.
In GraphStream, the modularity is implemented in a stand-alone (more powerful) algorithm and as a fast algorithm like the one seen here.
To work, this algorithm needs some information in the graph : each node must be marked with a special attribute that tells to which community it pertains. This attribute is the value given to the Algorithms.modularity(String) method.
This attribute name can be arbitrarily chosen, and the values are arbitrary. They will only be compared for equality to know if two nodes are in the same community.
Clustering coefficient
double Algorithms.getClusteringCoefficient(Node node)
The clustering coefficient of a node is computed by considering the node and all its neighbour nodes. This is the ratio between the actual links between these nodes and the maximum number of edges between these nodes (as if they were forming a clique).
Node position
This is an utility that allows to easily retrieve the (x,y) or (x,y,z) coordinates of a node. Indeed you have several possibilities to store the position of a node as an attribute : you can use the "x", "y" and "z" attributes or the "xy" attribute (that takes two arguments) or the "xyz" attribute (that takes three arguments). However, once stored in a form, they remain as is, and it may become difficult to handle these attributes when reading them.
The Algorithms.getNodePosition() set methods help when dealing with this. You have several versions, mainly : those that return a newly allocated array of three floats and those that take this array as argument and fill it.
float[] Algorithms.getNodePosition(String id); float[] Algorithms.getNodePosition(Node node); void Algorithms.getNodePosition(String id, float xyz[]); void Algorithms.getNodePosition(Node node, float xyz[]);
For the methods that return the array, null is returned if the node has no position attribute.
Edge length
This is another utility method that takes the position of the two nodes of the edge and computes the distance between the two.
float Algorithms.getEdgeLength(String id); float Algorithms.getEdgeLength(Edge edge);