Package org.jgrapht.alg.shortestpath
Class GraphMeasurer<V,E>
- java.lang.Object
-
- org.jgrapht.alg.shortestpath.GraphMeasurer<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
public class GraphMeasurer<V,E> extends java.lang.Object
Algorithm class which computes a number of distance related metrics. A summary of various distance metrics can be found here.- Author:
- Joris Kinable, Alexandru Valeanu
-
-
Constructor Summary
Constructors Constructor Description GraphMeasurer(Graph<V,E> graph)
Constructs a new instance of GraphMeasurer.GraphMeasurer(Graph<V,E> graph, ShortestPathAlgorithm<V,E> shortestPathAlgorithm)
Constructs a new instance of GraphMeasurer.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description double
getDiameter()
Compute the diameter of the graph.java.util.Set<V>
getGraphCenter()
Compute the graph center.java.util.Set<V>
getGraphPeriphery()
Compute the graph periphery.java.util.Set<V>
getGraphPseudoPeriphery()
Compute the graph pseudo-periphery.double
getRadius()
Compute the radius of the graph.java.util.Map<V,java.lang.Double>
getVertexEccentricityMap()
Compute the eccentricity of each vertex in the graph.
-
-
-
Constructor Detail
-
GraphMeasurer
public GraphMeasurer(Graph<V,E> graph)
Constructs a new instance of GraphMeasurer.FloydWarshallShortestPaths
is used as the default shortest path algorithm.- Parameters:
graph
- input graph
-
GraphMeasurer
public GraphMeasurer(Graph<V,E> graph, ShortestPathAlgorithm<V,E> shortestPathAlgorithm)
Constructs a new instance of GraphMeasurer.- Parameters:
graph
- input graphshortestPathAlgorithm
- shortest path algorithm used to compute shortest paths between all pairs of vertices. Recommended algorithms are:JohnsonShortestPaths
(Runtime complexity: $O(|V||E| + |V|^2 log|V|)$) orFloydWarshallShortestPaths
(Runtime complexity: $O(|V|^3)$.
-
-
Method Detail
-
getDiameter
public double getDiameter()
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
.- Returns:
- the diameter of the graph.
-
getRadius
public double getRadius()
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
.- Returns:
- the diameter of the graph.
-
getVertexEccentricityMap
public java.util.Map<V,java.lang.Double> getVertexEccentricityMap()
Compute the eccentricity of each vertex in the graph. The eccentricity of a vertex $u$ is defined as $\max_{v}d(u,v)$, where $d(u,v)$ is the shortest path between vertices $u$ and $v$. If the graph is disconnected, the eccentricity of each vertex isDouble.POSITIVE_INFINITY
. The runtime complexity of this method is $O(n^2+L)$, where $L$ is the runtime complexity of the shortest path algorithm provided during construction of this class.- Returns:
- a map containing the eccentricity of each vertex.
-
getGraphCenter
public java.util.Set<V> getGraphCenter()
Compute the graph center. The center of a graph is the set of vertices of graph eccentricity equal to the graph radius.- Returns:
- the graph center
-
getGraphPeriphery
public java.util.Set<V> getGraphPeriphery()
Compute the graph periphery. The periphery of a graph is the set of vertices of graph eccentricity equal to the graph diameter.- Returns:
- the graph periphery
-
getGraphPseudoPeriphery
public java.util.Set<V> getGraphPseudoPeriphery()
Compute the graph pseudo-periphery. The pseudo-periphery of a graph is the set of all pseudo-peripheral vertices. A pseudo-peripheral vertex $v$ has the property that for any vertex $u$, if $v$ is as far away from $u$ as possible, then $u$ is as far away from $v$ as possible. Formally, a vertex $u$ is pseudo-peripheral, if for each vertex $v$ with $d(u,v)=\epsilon(u)$ holds $\epsilon(u)=\epsilon(v)$, where $\epsilon(u)$ is the eccentricity of vertex $u$.- Returns:
- the graph pseudo-periphery
-
-