org.graphstream.algorithm

Interface Algorithm

All Known Subinterfaces:

DynamicAlgorithm, FlowAlgorithm, SpanningTree

All Known Implementing Classes:

AbstractCentrality, AbstractSpanningTree, APSP, AStar, BellmanFord, BetweennessCentrality, Centroid, ChartConnectivityMeasure, ChartConnectivityMeasure.ChartEdgeConnectivityMeasure, ChartConnectivityMeasure.ChartVertexConnectivityMeasure, ClosenessCentrality, CommunityDistribution, CommunityMeasure, CommunityRelativeMeasure, ConnectedComponents, ConnectivityMeasure.EdgeConnectivityMeasure, ConnectivityMeasure.VertexConnectivityMeasure, DecentralizedCommunityAlgorithm, DegreeCentrality, DegreeMeasure, Dijkstra, DStar, DynamicOneToAllShortestPath, Eccentricity, EdmondsKarpAlgorithm, EigenvectorCentrality, ElementCountMeasure, ElementCountMeasure.EdgeCountMeasure, ElementCountMeasure.NodeCountMeasure, EpidemicCommunityAlgorithm, FlowAlgorithmBase, FordFulkersonAlgorithm, Kruskal, Leung, Modularity, NetworkSimplex, NormalizedMutualInformation, PageRank, Prim, RandomWalk, Spectrum, SurpriseMeasure, SyncEpidemicCommunityAlgorithm, TarjanStronglyConnectedComponents, VariationOfInformation, WelshPowell

public interface Algorithm

Algorithms are used to compute properties on graphs or graph elements. These properties could be a measure, color, spanning tree, etc... Algorithms are divided into two steps :

1. initialization, that initialize or reset the algorithm ;
2. computation, that computes a property or updates a previous result.

Algorithm interface aims to define algorithms that do no handle dynamics of the graph, whereas algorithms implementing the DynamicAlgorithm interface (an extended version of Algorithm) are able to handle this dynamics.

This following is an example of an algorithm that computes max, min and average degrees of a 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, d);
                                maxDegree = Math.max(maxDegree, d);
                                avgDegree += d;
                        }
 
                        avgDegree /= theGraph.getNodeCount();
                }
 
                public int getMaxDegree() {
                        return maxDegree;
                }
 
                public int getMinDegree() {
                        return minDegree;
                }
 
                public int getAverageDegree() {
                        return avgDegree;
                }
 }
 

Complexity of algorithms can be specify in the documentation with the help of the "@complexity" tag.

Method Summary

Methods

Modifier and Type	Method and Description
void	compute() Run the algorithm.
void	init(org.graphstream.graph.Graph graph) Initialization of the algorithm.

Method Detail

init

void init(org.graphstream.graph.Graph graph)

Initialization of the algorithm. This method has to be called before the compute() method to initialize or reset the algorithm according to the new given graph.

Parameters:

graph - The graph this algorithm is using.

compute

void compute()

Run the algorithm. The init(Graph) method has to be called before computing.

See Also:

init(Graph)