 java.lang.Object

 org.jgrapht.GraphMetrics

public abstract class GraphMetrics extends java.lang.Object
Collection of methods which provide numerical graph information. Author:
 Joris Kinable, Alexandru Valeanu


Constructor Summary
Constructors Constructor Description GraphMetrics()

Method Summary
All Methods Static Methods Concrete Methods Modifier and Type Method Description static <V,E>
doublegetDiameter(Graph<V,E> graph)
Compute the diameter of the graph.static <V,E>
intgetGirth(Graph<V,E> graph)
Compute the girth of the graph.static <V,E>
longgetNumberOfTriangles(Graph<V,E> graph)
An $O(E^{3/2})$ algorithm for counting the number of nontrivial triangles in an undirected graph.static <V,E>
doublegetRadius(Graph<V,E> graph)
Compute the radius of the graph.



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 isDouble.POSITIVE_INFINITY
.For more finegrained 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 typeE
 graph edge type Parameters:
graph
 input graph Returns:
 the diameter of the graph.

getRadius
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 isDouble.POSITIVE_INFINITY
.For more finegrained 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 typeE
 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 BangJensen, 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 (selfloop).This implementation is loosely based on these notes. In essence, this method invokes a BreadthFirst search from every vertex in the graph. A single BreadthFirst 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 typeE
 graph edge type Parameters:
graph
 input graph Returns:
 girth of the graph, or
Integer.MAX_VALUE
if the graph is acyclic.

getNumberOfTriangles
public static <V,E> long getNumberOfTriangles(Graph<V,E> graph)
An $O(E^{3/2})$ algorithm for counting the number of nontrivial triangles in an undirected graph. A nontrivial triangle is formed by three distinct vertices all connected to each other.For more details of this algorithm see Ullman, Jeffrey: "Mining of Massive Datasets", Cambridge University Press, Chapter 10
 Type Parameters:
V
 the graph vertex typeE
 the graph edge type Parameters:
graph
 the input graph Returns:
 the number of triangles in the graph
 Throws:
java.lang.NullPointerException
 ifgraph
isnull
java.lang.IllegalArgumentException
 ifgraph
is not undirected

