/*
* Copyright (c) 2003, The JUNG Authors
*
* All rights reserved.
*
* This software is open-source under the BSD license; see either
* "license.txt" or
* https://github.com/jrtom/jung/blob/master/LICENSE for a description.
*/
package edu.uci.ics.jung.algorithms.shortestpath;
import java.util.Collection;
import com.google.common.base.Function;
import edu.uci.ics.jung.algorithms.scoring.ClosenessCentrality;
import edu.uci.ics.jung.algorithms.scoring.util.VertexScoreTransformer;
import edu.uci.ics.jung.graph.Hypergraph;
/**
* Statistics relating to vertex-vertex distances in a graph.
*
* Formerly known as GraphStatistics in JUNG 1.x.
*
* @author Scott White
* @author Joshua O'Madadhain
*/
public class DistanceStatistics
{
/**
* For each vertex v in graph,
* calculates the average shortest path length from v
* to all other vertices in graph using the metric
* specified by d, and returns the results in a
* Map from vertices to Double values.
* If there exists an ordered pair <u,v>
* for which d.getDistance(u,v) returns null,
* then the average distance value for u will be stored
* as Double.POSITIVE_INFINITY).
*
*
Does not include self-distances (path lengths from v
* to v).
*
*
To calculate the average distances, ignoring edge weights if any:
*
* Map distances = DistanceStatistics.averageDistances(g, new UnweightedShortestPath(g));
*
* To calculate the average distances respecting edge weights:
*
* DijkstraShortestPath dsp = new DijkstraShortestPath(g, nev);
* Map distances = DistanceStatistics.averageDistances(g, dsp);
*
* where nev is an instance of Transformer that
* is used to fetch the weight for each edge.
*
* @see edu.uci.ics.jung.algorithms.shortestpath.UnweightedShortestPath
* @see edu.uci.ics.jung.algorithms.shortestpath.DijkstraDistance
*
* @param graph the graph for which distances are to be calculated
* @param d the distance metric to use for the calculation
* @param the vertex type
* @param the edge type
* @return a map from each vertex to the mean distance to each other (reachable) vertex
*/
public static Function averageDistances(Hypergraph graph, Distance d)
{
final ClosenessCentrality cc = new ClosenessCentrality(graph, d);
return new VertexScoreTransformer(cc);
}
/**
* For each vertex v in g,
* calculates the average shortest path length from v
* to all other vertices in g, ignoring edge weights.
* @see #diameter(Hypergraph)
* @see edu.uci.ics.jung.algorithms.scoring.ClosenessCentrality
*
* @param g the graph for which distances are to be calculated
* @param the vertex type
* @param the edge type
* @return a map from each vertex to the mean distance to each other (reachable) vertex
*/
public static Function averageDistances(Hypergraph g)
{
final ClosenessCentrality cc = new ClosenessCentrality(g,
new UnweightedShortestPath(g));
return new VertexScoreTransformer(cc);
}
/**
* Returns the diameter of g using the metric
* specified by d. The diameter is defined to be
* the maximum, over all pairs of vertices u,v,
* of the length of the shortest path from u to
* v. If the graph is disconnected (that is, not
* all pairs of vertices are reachable from one another), the
* value returned will depend on use_max:
* if use_max == true, the value returned
* will be the the maximum shortest path length over all pairs of connected
* vertices; otherwise it will be Double.POSITIVE_INFINITY.
*
* @param g the graph for which distances are to be calculated
* @param d the distance metric to use for the calculation
* @param use_max if {@code true}, return the maximum shortest path length for all graphs;
* otherwise, return {@code Double.POSITIVE_INFINITY} for disconnected graphs
* @param the vertex type
* @param the edge type
* @return the longest distance from any vertex to any other
*/
public static double diameter(Hypergraph g, Distance d, boolean use_max)
{
double diameter = 0;
Collection vertices = g.getVertices();
for(V v : vertices) {
for(V w : vertices) {
if (v.equals(w) == false) // don't include self-distances
{
Number dist = d.getDistance(v, w);
if (dist == null)
{
if (!use_max)
return Double.POSITIVE_INFINITY;
}
else
diameter = Math.max(diameter, dist.doubleValue());
}
}
}
return diameter;
}
/**
* Returns the diameter of g using the metric
* specified by d. The diameter is defined to be
* the maximum, over all pairs of vertices u,v,
* of the length of the shortest path from u to
* v, or Double.POSITIVE_INFINITY
* if any of these distances do not exist.
* @see #diameter(Hypergraph, Distance, boolean)
*
* @param g the graph for which distances are to be calculated
* @param d the distance metric to use for the calculation
* @param the vertex type
* @param the edge type
* @return the longest distance from any vertex to any other
*/
public static double diameter(Hypergraph g, Distance d)
{
return diameter(g, d, false);
}
/**
* Returns the diameter of g, ignoring edge weights.
* @see #diameter(Hypergraph, Distance, boolean)
*
* @param g the graph for which distances are to be calculated
* @param the vertex type
* @param the edge type
* @return the longest distance from any vertex to any other
*/
public static double diameter(Hypergraph g)
{
return diameter(g, new UnweightedShortestPath(g));
}
}
Ads help maintain this website.