Metrics

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

jgrapht.metrics.count_triangles(graph)

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)

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)

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 breadth-first 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)

Measure the graph. This method executes an all-pairs shortest paths using Floyd-Warshal.

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 pseudo-periphery of the graph

• the vertex eccentricity map

Parameters

graph – the input graph

Returns

a 6-tuple containing the results.

jgrapht.metrics.radius(graph)

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