Class NeighbourhoodFunction

    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method Description
      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, it.unimi.dsi.logging.ProgressLogger pl)
      Computes and returns the neighbourhood function of the specified graph by multiple breadth-first visits.
      static double[] compute​(ImmutableGraph g, it.unimi.dsi.logging.ProgressLogger pl)
      Computes and returns the neighbourhood function of the specified graph by multiple breadth-first visits.
      static long[] computeExact​(ImmutableGraph g, int threads, it.unimi.dsi.logging.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​(java.lang.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

      • NeighbourhoodFunction

        public NeighbourhoodFunction()
    • Method Detail

      • compute

        public static double[] compute​(ImmutableGraph g)
        Computes and returns the neighbourhood function of the specified graph by multiple breadth-first visits.

        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.

        Parameters:
        g - a graph.
        Returns:
        the neighbourhood function of the specified graph.
      • compute

        public static double[] compute​(ImmutableGraph g,
                                       it.unimi.dsi.logging.ProgressLogger pl)
        Computes and returns the neighbourhood function of the specified graph by multiple breadth-first visits.

        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.

        Parameters:
        g - a graph.
        pl - a progress logger, or null.
        Returns:
        the neighbourhood function of the specified graph.
      • compute

        public static double[] compute​(ImmutableGraph g,
                                       int threads,
                                       it.unimi.dsi.logging.ProgressLogger pl)
        Computes and returns the neighbourhood function of the specified graph by multiple breadth-first visits.

        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.

        Parameters:
        g - a graph.
        threads - the requested number of threads (0 for Runtime.availableProcessors()). Note that if the graph is small a large number of thread will slow down the computation because of synchronization costs.
        pl - a progress logger, or null.
        Returns:
        the neighbourhood function of the specified graph.
      • computeExact

        public static long[] computeExact​(ImmutableGraph g,
                                          int threads,
                                          it.unimi.dsi.logging.ProgressLogger pl)
        Computes and returns the neighbourhood function of the specified graph by multiple breadth-first visits.

        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).

        Parameters:
        g - a graph.
        threads - the requested number of threads (0 for Runtime.availableProcessors()). Note that if the graph is small a large number of thread will slow down the computation because of synchronization costs.
        pl - a progress logger, or null.
        Returns:
        the neighbourhood function of the specified graph as an array of longs.
      • distanceCumulativeDistributionFunction

        public static double[] distanceCumulativeDistributionFunction​(double[] neighbourhoodFunction)
        Returns the distance cumulative distribution function.
        Parameters:
        neighbourhoodFunction - a neighbourhood function or distance cumulative distribution function.
        Returns:
        the distance cumulative distribution function.
      • distanceProbabilityMassFunction

        public static double[] distanceProbabilityMassFunction​(double[] neighbourhoodFunction)
        Returns the probability mass function of the distance distribution.
        Parameters:
        neighbourhoodFunction - a neighbourhood function or distance cumulative distribution function.
        Returns:
        the probability mass function of the distance distribution.
      • effectiveDiameter

        public static double effectiveDiameter​(double alpha,
                                               double[] neighbourhoodFunction)
        Returns the effective diameter at a specified fraction.
        Parameters:
        alpha - the desired fraction of reachable pairs of nodes (usually, 0.9).
        neighbourhoodFunction - a neighbourhood function or distance cumulative distribution function.
        Returns:
        the effective diameter at fraction.
      • effectiveDiameter

        public static double effectiveDiameter​(double[] neighbourhoodFunction)
        Returns the effective diameter at 0.9.
        Parameters:
        neighbourhoodFunction - a neighbourhood function (or distance cumulative distribution function).
        Returns:
        the effective diameter at 0.9.
      • medianDistance

        public static double medianDistance​(double[] neighbourhoodFunction)
        Returns the median of distances between all pairs of nodes.
        Parameters:
        neighbourhoodFunction - a neighbourhood function.
        Returns:
        the median distance, which might be Double.POSITIVE_INFINITY if less than half of the pairs of nodes are reachable.
      • medianDistance

        public static double medianDistance​(int n,
                                            double[] neighbourhoodFunction)
        Returns the median of distances between all pairs of nodes.

        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.

        Parameters:
        n - the number of nodes in the graph.
        neighbourhoodFunction - a neighbourhood function (or distance cumulative distribution function).
        Returns:
        the median distance, which might be Double.POSITIVE_INFINITY if less than half of the pairs of nodes are reachable.
      • spid

        public static double spid​(double[] neighbourhoodFunction)
        Returns the spid (shortest-paths index of dispersion).
        Parameters:
        neighbourhoodFunction - a neighbourhood function (or distance cumulative distribution function).
        Returns:
        the spid.
      • averageDistance

        public static double averageDistance​(double[] neighbourhoodFunction)
        Returns the average of the distances between reachable pairs of nodes.
        Parameters:
        neighbourhoodFunction - a neighbourhood function (or distance cumulative distribution function).
        Returns:
        the average of the distances between reachable pairs of nodes.
      • harmonicDiameter

        public static double harmonicDiameter​(double[] neighbourhoodFunction)
        Returns the harmonic diameter, that is, the harmonic mean of all distances.
        Parameters:
        neighbourhoodFunction - a neighbourhood function.
        Returns:
        the harmonic diameter.
      • harmonicDiameter

        public static double harmonicDiameter​(int n,
                                              double[] neighbourhoodFunction)
        Returns the harmonic diameter, that is, the harmonic mean of all distances.

        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.

        Parameters:
        n - the number of nodes in the graph.
        neighbourhoodFunction - a neighbourhood function (or distance cumulative distribution function).
        Returns:
        the harmonic diameter.
      • main

        public static void main​(java.lang.String[] arg)
                         throws java.io.IOException,
                                com.martiansoftware.jsap.JSAPException
        Throws:
        java.io.IOException
        com.martiansoftware.jsap.JSAPException