Metrics¶
Certain graph metrics such as the diameter of a graph can be computed using the following functions.

jgrapht.metrics.
count_triangles
(graph)[source]¶ Count the number of triangles in a graph.
This is an \(\mathcal{O}(m^{3/2})\) algorithm for counting the number of triangles in an undirected graph.
 Parameters
graph – the input graph. Must be undirected
 Returns
the number of triangles in the graph
 Raises
ValueError – if the graph is not undirected

jgrapht.metrics.
diameter
(graph)[source]¶ Compute the diameter of a 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: (a) if the graph has no vertices, the diameter is 0, and (b) if the graph is disconnected, the diameter is positive infinity.
 Parameters
graph – the input graph
 Returns
the graph diameter

jgrapht.metrics.
girth
(graph)[source]¶ Compute the girth of a graph.
The girth is the length of the shortest graph cycle (if any) in a graph. Acyclic graphs are considered to have infinite girth. For directed graphs, the length of the shortest directed cycle is returned.
This method invokes a breadthfirst search from every vertex in the graph. Thus, its runtime complexity is \(\mathcal{O}(n(m+n)) = \mathcal{O}(m n)\).
 Parameters
graph – the input graph
 Returns
the graph girth

jgrapht.metrics.
measure
(graph)[source]¶ Measure the graph. This method executes an allpairs shortest paths using FloydWarshal.
This method computes:
the graph diameter
the graph radius
the set of vertices which form the center of the graph
the set of vertices which form the periphery of the graph
the set of vertices which form the pseudoperiphery of the graph
the vertex eccentricity map
 Parameters
graph – the input graph
 Returns
a 6tuple containing the results.

jgrapht.metrics.
radius
(graph)[source]¶ Compute the radius of a graph.
The radius of a graph is the minimum vertex eccentricity.
Note
If the graph has no vertices, the radius is zero. In case the graph is disconnected, the radius is positive infinity.
 Parameters
graph – the input graph
 Returns
the graph diameter