org.jgrapht

## Class GraphMetrics

• public abstract class GraphMetrics
extends Object
Collection of methods which provide numerical graph information.
Author:
Joris Kinable
• ### Constructor Summary

Constructors
Constructor and Description
GraphMetrics()
• ### Method Summary

All Methods
Modifier and Type Method and Description
static <V,E> double getDiameter(Graph<V,E> graph)
Compute the diameter of the graph.
static <V,E> int getGirth(Graph<V,E> graph)
Compute the girth of the graph.
static <V,E> double getRadius(Graph<V,E> graph)
Compute the radius of the graph.
• ### Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
• ### Constructor Detail

• #### GraphMetrics

public GraphMetrics()
• ### Method Detail

• #### getDiameter

public static <V,E> double getDiameter(Graph<V,E> graph)
Compute the diameter of the graph. The diameter of a graph is defined as $\max_{v\in V}\epsilon(v)$, where $\epsilon(v)$ is the eccentricity of vertex $v$. In other words, this method computes the 'longest shortest path'. Two special cases exist. If the graph has no vertices, the diameter is 0. If the graph is disconnected, the diameter is Double.POSITIVE_INFINITY.

For more fine-grained control over this method, or if you need additional distance metrics such as the graph radius, consider using GraphMeasurer instead.

Type Parameters:
V - graph vertex type
E - graph edge type
Parameters:
graph - input graph
Returns:
the diameter of the graph.

public static <V,E> double getRadius(Graph<V,E> graph)
Compute the radius of the graph. The radius of a graph is defined as $\min_{v\in V}\epsilon(v)$, where $\epsilon(v)$ is the eccentricity of vertex $v$. Two special cases exist. If the graph has no vertices, the radius is 0. If the graph is disconnected, the diameter is Double.POSITIVE_INFINITY.

For more fine-grained control over this method, or if you need additional distance metrics such as the graph diameter, consider using GraphMeasurer instead.

Type Parameters:
V - graph vertex type
E - graph edge type
Parameters:
graph - input graph
Returns:
the diameter of the graph.
• #### getGirth

public static <V,E> int getGirth(Graph<V,E> graph)
Compute the girth of the graph. The girth of a graph is the length (number of edges) of the smallest cycle in the graph. Acyclic graphs are considered to have infinite girth. For directed graphs, the length of the shortest directed cycle is returned (see Bang-Jensen, J., Gutin, G., Digraphs: Theory, Algorithms and Applications, Springer Monographs in Mathematics, ch 1, ch 8.4.). Simple undirected graphs have a girth of at least 3 (triangle cycle). Directed graphs and Multigraphs have a girth of at least 2 (parallel edges/arcs), and in Pseudo graphs have a girth of at least 1 (self-loop).

This implementation is loosely based on these notes. In essence, this method invokes a Breadth-First search from every vertex in the graph. A single Breadth-First search takes $O(n+m)$ time, where $n$ is the number of vertices in the graph, and $m$ the number of edges. Consequently, the runtime complexity of this method is $O(n(n+m))=O(mn)$.

An algorithm with the same worst case runtime complexity, but a potentially better average runtime complexity of $O(n^2)$ is described in: Itai, A. Rodeh, M. Finding a minimum circuit in a graph. SIAM J. Comput. Vol 7, No 4, 1987.

Type Parameters:
V - graph vertex type
E - graph edge type
Parameters:
graph - input graph
Returns:
girth of the graph, or Integer.MAX_VALUE if the graph is acyclic.