cc.redberry.core.graph

Class GraphUtils

java.lang.Object

cc.redberry.core.graph.GraphUtils

public class GraphUtils
extends java.lang.Object

This class implements useful graph algorithms.

Since:

1.0

Constructor Summary

Constructors

Constructor and Description
GraphUtils()

Method Summary

Modifier and Type	Method and Description
static int[]	calculateConnectedComponents(int[] _from, int[] _to, int vertices) Calculates connected components of the graph from its list of edges.
static int	componentSize(int vertex, int[] components) Returns the number of vertices belonging to the connected component containing specified vertex.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

GraphUtils

public GraphUtils()

Method Detail

calculateConnectedComponents

public static int[] calculateConnectedComponents(int[] _from,
                                                 int[] _to,
                                                 int vertices)

Calculates connected components of the graph from its list of edges. The list of edges is provided as two arrays (_from, which contains 'from' vertices indices, and array _to, which contains vertices indices connected with corresponding 'from' vertices). Vertices are indexed from zero to vertexes - 1, where vertexes is the total number of vertices of the graph. All indices in arrays _from and _to should be in the range [ 0 .. (vertices -1) ].

The resulting array have length equal to the total number of vertices plus one. Two vertices A and B belongs to the same connected component if the resulting array have equal values at positions A and B. The last element in the resulting array represents the total number of connected components.

Parameters:

_from - array of 'from' vertices

_to - array of 'to' vertices

vertices - total number of vertices in graph

Returns:

array of connected components and the total number of connected components at the last position

Throws:

java.lang.IllegalArgumentException - if _from.length() != _to.length

java.lang.IllegalArgumentException - if any element of _from or _to equal or greater then vertices

Since:

1.0

componentSize

public static int componentSize(int vertex,
                                int[] components)

Returns the number of vertices belonging to the connected component containing specified vertex.

Parameters:

vertex - vertex of the graph

components - the array, produced by calculateConnectedComponents(int[], int[], int)

Returns:

number of vertices belonging to the same connected component as specified vertex

Since:

1.0