Package it.unimi.dsi.webgraph.algo

Class ParallelBreadthFirstVisit

java.lang.Object
it.unimi.dsi.webgraph.algo.ParallelBreadthFirstVisit
public class ParallelBreadthFirstVisit
extends Object
Performs breadth-firsts visits of a graph exploiting multicore parallelism.

To use this class you first create an instance, and then invoke visit(int). If you want perform more visits preserving the marker state you can invoke visit(int) again. By calling clear(), instead, you can reset marker (i.e., forget about visited nodes).

Alternatively, visitAll() will start a visit from all the nodes of the graph in a more efficient way.

After the visit, you can peek at the field marker to discover details about the visit. Depending on the parent value provided at construction time, the array marker will be filled with parent information (e.g., with the index of the parent node in the visit tree) or with a round number increased at each nonempty visit, which act as a connected-component index if the graph is symmetric.

Observe that in the former case (if parent is true), the array marker will contain the value -1 for the nodes that have not been reached by the visit, the parent of the node in the BFS tree if the node was not the root, or the node itself for the root.

In the case of visit(int, int), queue and cutPoints, too, provide useful information. In particular, the nodes in queue from the d-th to the (d +1)-th cutpoint are exactly the nodes at distance d from the source.

Performance issues

This class needs three integers per node. If there are several available cores, breadth-first visits will be decomposed into relatively small tasks (small blocks of nodes in the queue at the same distance from the starting node) and each task will be assigned to the first available core. Since all tasks are completely independent, this ensures a very high degree of parallelism. However, on very sparse graphs the cost of keeping the threads synchronised can be extremely high, and even end up increasing the visit time.

Note that if the degree distribution is extremely skewed some cores might get stuck in the enumeration of the successors of some nodes with a very high degree.

  • Field Summary

    Fields
    Modifier and Type Field Description
    IntArrayList cutPoints
    At the end of a visit, the cutpoints of queue.
    ImmutableGraph graph
    The graph under examination.
    AtomicIntegerArray marker
    The marker array; contains -1 for nodes that have not still been enqueued, the parent of the visit tree if parent is true, or an index increased at each visit if parent is false, which in the symmetric case is the index of the connected component of the node.
    boolean parent
    Whether marker contains parent nodes or round numbers.
    IntArrayList queue
    The queue of visited nodes.
    int round
    A number increased at each nonempty visit (used to mark marker if parent is false).

  • Constructor Summary

    Constructors
    Constructor Description
    ParallelBreadthFirstVisit​(ImmutableGraph graph, int requestedThreads, boolean parent, ProgressLogger pl)
    Creates a new class for keeping track of the state of parallel breadth-first visits.

  • Method Summary

    Modifier and Type Method Description
    void clear()
    Clears the internal state of the visit, setting all marker entries and round to -1.
    int maxDistance()
    Returns the maximum distance computed during the last visit (e.g., the eccentricity of the source).
    int nodeAtMaxDistance()
    Returns a node at maximum distance during the last visit (e.g., a node realising the positive eccentricity of the starting node).
    int visit​(int start)
    Performs a breadth-first visit of the given graph starting from the given node.
    int visit​(int start, int expectedSize)
    Performs a breadth-first visit of the given graph starting from the given node.
    void visitAll()
    Visits all nodes.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Field Details

    • graph

      public final ImmutableGraph graph
      The graph under examination.

    • queue

      public final IntArrayList queue
      The queue of visited nodes.

    • cutPoints

      public final IntArrayList cutPoints
      At the end of a visit, the cutpoints of queue. The d-th cutpoint is the first node in the queue at distance d. The last cutpoint is the queue size.

    • parent

      public final boolean parent
      Whether marker contains parent nodes or round numbers.

    • marker

      public final AtomicIntegerArray marker
      The marker array; contains -1 for nodes that have not still been enqueued, the parent of the visit tree if parent is true, or an index increased at each visit if parent is false, which in the symmetric case is the index of the connected component of the node.

    • round

      public int round
      A number increased at each nonempty visit (used to mark marker if parent is false).

  • Constructor Details

    • ParallelBreadthFirstVisit

      public ParallelBreadthFirstVisit​(ImmutableGraph graph, int requestedThreads, boolean parent, ProgressLogger pl)
      Creates a new class for keeping track of the state of parallel breadth-first visits.
      Parameters:
      graph - a graph.
      requestedThreads - the requested number of threads (0 for Runtime.availableProcessors()).
      parent - if true, marker will contain parent nodes; otherwise, it will contain round numbers.
      pl - a progress logger, or null.

  • Method Details

    • clear

      public void clear()
      Clears the internal state of the visit, setting all marker entries and round to -1.

    • visit

      public int visit​(int start)
      Performs a breadth-first visit of the given graph starting from the given node.

      This method will increment round.

      Parameters:
      start - the starting node.
      Returns:
      the number of visited nodes.
      See Also:
      visit(int,int)

    • visit

      public int visit​(int start, int expectedSize)
      Performs a breadth-first visit of the given graph starting from the given node.

      This method will increment round if at least one node is visited.

      Parameters:
      start - the starting node.
      expectedSize - the expected size (number of nodes) of the visit (for logging), or -1 to use the number of nodes of the graph.
      Returns:
      the number of visited nodes.

    • visitAll

      public void visitAll()
      Visits all nodes. Calls clear() initially.

      This method is more efficient than invoking visit(int, int) on all nodes as threads are created just once.

    • nodeAtMaxDistance

      public int nodeAtMaxDistance()
      Returns a node at maximum distance during the last visit (e.g., a node realising the positive eccentricity of the starting node).
      Returns:
      the maximum distance computed during the last visit.

    • maxDistance

      public int maxDistance()
      Returns the maximum distance computed during the last visit (e.g., the eccentricity of the source).
      Returns:
      the maximum distance computed during the last visit.