Class NodeNeighbourhoodFunction

java.lang.Object
it.unimi.dsi.webgraph.scratch.NodeNeighbourhoodFunction

public class NodeNeighbourhoodFunction extends Object
Computes the neighbourhood function of a node of graph by a parallel breadth-first visit.

Performance issues

This class uses an instance of ParallelBreadthFirstVisit to ensure a high degree of parallelism (see its documentation for memory requirements). Note that if the graph is small a large number of thread will slow down the computation because of synchronization costs.

Author:
Paolo Boldi, Sebastiano Vigna
  • Constructor Summary

    Constructors
    Constructor
    Description
     
  • Method Summary

    Modifier and Type
    Method
    Description
    static double[]
    compute(ImmutableGraph g, int node)
    Computes and returns the neighbourhood function of the specified graph by multiple breadth-first visits.
    static double[]
    compute(ImmutableGraph g, int node, 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, int node, 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, int node, it.unimi.dsi.logging.ProgressLogger pl)
    Computes and returns the neighbourhood function of the specified graph by multiple breadth-first visits.
    static void
    main(String[] arg)
     

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Constructor Details

    • NodeNeighbourhoodFunction

      public NodeNeighbourhoodFunction()
  • Method Details

    • compute

      public static double[] compute(ImmutableGraph g, int node)
      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, int, ProgressLogger) instead.

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

      public static double[] compute(ImmutableGraph g, int node, 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, int, ProgressLogger) instead.

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

      public static double[] compute(ImmutableGraph g, int node, 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, int, ProgressLogger) instead.

      Parameters:
      g - a graph.
      node - the starting node.
      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, int node, 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.
      node - the starting node.
      pl - a progress logger, or null.
      Returns:
      the neighbourhood function of the specified graph as an array of longs.
    • main

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