public abstract class GraphMetrics extends Object
Constructor and Description 

GraphMetrics() 
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> long 
getNumberOfTriangles(Graph<V,E> graph)
An $O(E^{3/2})$ algorithm for counting the number of nontrivial triangles in an undirected
graph.

static <V,E> double 
getRadius(Graph<V,E> graph)
Compute the radius of the graph.

public static <V,E> double getDiameter(Graph<V,E> graph)
Double.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.
V
 graph vertex typeE
 graph edge typegraph
 input graphpublic static <V,E> double getRadius(Graph<V,E> graph)
Double.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.
V
 graph vertex typeE
 graph edge typegraph
 input graphpublic static <V,E> int getGirth(Graph<V,E> graph)
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.
V
 graph vertex typeE
 graph edge typegraph
 input graphInteger.MAX_VALUE
if the graph is acyclic.public static <V,E> long getNumberOfTriangles(Graph<V,E> graph)
For more details of this algorithm see Ullman, Jeffrey: "Mining of Massive Datasets", Cambridge University Press, Chapter 10
V
 the graph vertex typeE
 the graph edge typegraph
 the input graphNullPointerException
 if graph
is null
IllegalArgumentException
 if graph
is not undirectedCopyright © 2019. All rights reserved.