|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectit.unimi.dsi.webgraph.algo.NeighbourhoodFunction
public class NeighbourhoodFunction
Computes the neighbourhood function of a graph by multiple parallel breadth-first visits.
Note that performing all breadth-first visits requires time O(nm), so this class is usable only on very small graphs.
Additionally, this class provides several useful static methods such as distanceCumulativeDistributionFunction(double[])
,
distanceProbabilityMassFunction(double[])
, averageDistance(double[])
, medianDistance(int, double[])
and spid(double[])
that act on neighbourhood functions.
This class uses an instance of ParallelBreadthFirstVisit
to ensure a high degree of parallelism (see its
documentation for memory requirements).
Constructor Summary | |
---|---|
NeighbourhoodFunction()
|
Method Summary | |
---|---|
static double |
averageDistance(double[] neighbourhoodFunction)
Returns the average of the distances between reachable pairs of nodes. |
static double[] |
compute(ImmutableGraph g)
Computes and returns the neighbourhood function of the specified graph by multiple breadth-first visits. |
static double[] |
compute(ImmutableGraph g,
int threads,
ProgressLogger pl)
Computes and returns the neighbourhood function of the specified graph by multiple breadth-first visits. |
static double[] |
compute(ImmutableGraph g,
ProgressLogger pl)
Computes and returns the neighbourhood function of the specified graph by multiple breadth-first visits. |
static long[] |
computeExact(ImmutableGraph g,
int threads,
ProgressLogger pl)
Computes and returns the neighbourhood function of the specified graph by multiple breadth-first visits. |
static double[] |
distanceCumulativeDistributionFunction(double[] neighbourhoodFunction)
Returns the distance cumulative distribution function. |
static double[] |
distanceProbabilityMassFunction(double[] neighbourhoodFunction)
Returns the probability mass function of the distance distribution. |
static double |
effectiveDiameter(double[] neighbourhoodFunction)
Returns the effective diameter at 0.9. |
static double |
effectiveDiameter(double alpha,
double[] neighbourhoodFunction)
Returns the effective diameter at a specified fraction. |
static double |
harmonicDiameter(double[] neighbourhoodFunction)
Returns the harmonic diameter, that is, the harmonic mean of all distances. |
static double |
harmonicDiameter(int n,
double[] neighbourhoodFunction)
Returns the harmonic diameter, that is, the harmonic mean of all distances. |
static void |
main(String[] arg)
|
static double |
medianDistance(double[] neighbourhoodFunction)
Returns the median of distances between all pairs of nodes. |
static double |
medianDistance(int n,
double[] neighbourhoodFunction)
Returns the median of distances between all pairs of nodes. |
static double |
spid(double[] neighbourhoodFunction)
Returns the spid (shortest-paths index of dispersion). |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Constructor Detail |
---|
public NeighbourhoodFunction()
Method Detail |
---|
public static double[] compute(ImmutableGraph g)
This method returns an array of doubles. When some values of the function are near 263, it
might lose some least-significant digits. If you need exact values,
use computeExact(ImmutableGraph, int, ProgressLogger)
instead.
g
- a graph.
public static double[] compute(ImmutableGraph g, ProgressLogger pl)
This method returns an array of doubles. When some values of the function are near 263, it
might lose some least-significant digits. If you need exact values,
use computeExact(ImmutableGraph, int, ProgressLogger)
instead.
g
- a graph.pl
- a progress logger, or null
.
public static double[] compute(ImmutableGraph g, int threads, ProgressLogger pl)
This method returns an array of doubles. When some values of the function are near 263, it
might lose some least-significant digits. If you need exact values,
use computeExact(ImmutableGraph, int, ProgressLogger)
instead.
g
- a graph.threads
- the requested number of threads (0 for Runtime.availableProcessors()
).pl
- a progress logger, or null
.
public static long[] computeExact(ImmutableGraph g, int threads, ProgressLogger pl)
This method returns an array of longs. When some values of the function are near 263, it
provides an exact value, as opposed to compute(ImmutableGraph, int, ProgressLogger)
.
g
- a graph.threads
- the requested number of threads (0 for Runtime.availableProcessors()
).pl
- a progress logger, or null
.
public static double[] distanceCumulativeDistributionFunction(double[] neighbourhoodFunction)
neighbourhoodFunction
- a neighbourhood function or distance cumulative distribution function.
public static double[] distanceProbabilityMassFunction(double[] neighbourhoodFunction)
neighbourhoodFunction
- a neighbourhood function or distance cumulative distribution function.
public static double effectiveDiameter(double alpha, double[] neighbourhoodFunction)
alpha
- the desired fraction of reachable pairs of nodes (usually, 0.9).neighbourhoodFunction
- a neighbourhood function or distance cumulative distribution function.
fraction
.public static double effectiveDiameter(double[] neighbourhoodFunction)
neighbourhoodFunction
- a neighbourhood function (or distance cumulative distribution function).
public static double medianDistance(double[] neighbourhoodFunction)
neighbourhoodFunction
- a neighbourhood function.
Double.POSITIVE_INFINITY
if less than half
of the pairs of nodes are reachable.public static double medianDistance(int n, double[] neighbourhoodFunction)
Note that if you have an actual neighbourhood function, you can safely pass its first value as first argument; however, having the number of nodes as a separate input makes it possible passing this method a distance cumulative distribution function, too.
n
- the number of nodes in the graph.neighbourhoodFunction
- a neighbourhood function (or distance cumulative distribution function).
Double.POSITIVE_INFINITY
if less than half
of the pairs of nodes are reachable.public static double spid(double[] neighbourhoodFunction)
neighbourhoodFunction
- a neighbourhood function (or distance cumulative distribution function).
public static double averageDistance(double[] neighbourhoodFunction)
neighbourhoodFunction
- a neighbourhood function (or distance cumulative distribution function).
public static double harmonicDiameter(double[] neighbourhoodFunction)
neighbourhoodFunction
- a neighbourhood function.
public static double harmonicDiameter(int n, double[] neighbourhoodFunction)
Note that if you have an actual neighbourhood function, you can safely pass its first value as first argument; however, having the number of nodes as a separate input makes it possible passing this method a distance cumulative distribution function, too.
n
- the number of nodes in the graph.neighbourhoodFunction
- a neighbourhood function (or distance cumulative distribution function).
public static void main(String[] arg) throws IOException, JSAPException
IOException
JSAPException
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |