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 non-trivial 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 fine-grained 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 fine-grained 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 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.
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 nullIllegalArgumentException - if graph is not undirectedCopyright © 2019. All rights reserved.