public class GraphStatistics
extends java.lang.Object
Constructor and Description |
---|
GraphStatistics() |
Modifier and Type | Method and Description |
---|---|
static java.util.Map |
averageDistances(ArchetypeGraph g)
For each vertex
v in g ,
calculates the average shortest path length from v
to all other vertices in g , ignoring edge weights. |
static java.util.Map |
averageDistances(ArchetypeGraph graph,
Distance d)
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. |
static java.util.Map |
clusteringCoefficients(ArchetypeGraph graph)
Returns a
Map of vertices to their clustering coefficients. |
static Histogram |
createHistogram(cern.colt.list.DoubleArrayList values,
double min,
int numBins,
double binWidth)
Creates a histogram from a sequence of doubles
|
static double |
diameter(ArchetypeGraph g)
Returns the diameter of
g , ignoring edge weights. |
static double |
diameter(ArchetypeGraph g,
Distance d)
Returns the diameter of
g using the metric
specified by d . |
static double |
diameter(ArchetypeGraph g,
Distance d,
boolean use_max)
Returns the diameter of
g using the metric
specified by d . |
public static java.util.Map clusteringCoefficients(ArchetypeGraph graph)
Map
of vertices to their clustering coefficients.
The clustering coefficient cc(v) of a vertex v is defined as follows:
degree(v) == 0
: 0
degree(v) == 1
: 1
degree(v) == n, n > 1
: given S, the set of neighbors
of v
: cc(v) = (the sum over all w in S of the number of
other elements of w that are neighbors of w) / ((|S| * (|S| - 1) / 2).
Less formally, the fraction of v
's neighbors that are also
neighbors of each other.
Note: This algorithm treats its argument as an undirected graph; edge direction is ignored.
graph
- public static java.util.Map averageDistances(ArchetypeGraph graph, Distance d)
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
).
To calculate the average distances, ignoring edge weights if any:
Map distances = GraphStatistics.averageDistances(g, new UnweightedShortestPath(g));To calculate the average distances respecting edge weights:
DijkstraShortestPath dsp = new DijkstraShortestPath(g, nev); Map distances = GraphStatistics.averageDistances(g, dsp);where
nev
is an instance of NumberEdgeValue
that
is used to fetch the weight for each edge.UnweightedShortestPath
,
DijkstraDistance
public static java.util.Map averageDistances(ArchetypeGraph g)
v
in g
,
calculates the average shortest path length from v
to all other vertices in g
, ignoring edge weights.diameter(ArchetypeGraph, Distance)
public static double diameter(ArchetypeGraph g, Distance d, boolean use_max)
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
.public static double diameter(ArchetypeGraph g, Distance d)
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.public static double diameter(ArchetypeGraph g)
g
, ignoring edge weights.public static Histogram createHistogram(cern.colt.list.DoubleArrayList values, double min, int numBins, double binWidth)
values
- the sequence of doublesmin
- the minimum value to bin off ofnumBins
- the number of binsbinWidth
- the width of the bin