Class ParallelBreadthFirstVisit
- java.lang.Object
-
- it.unimi.dsi.webgraph.algo.ParallelBreadthFirstVisit
-
public class ParallelBreadthFirstVisit extends java.lang.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 themarker
state you can invokevisit(int)
again. By callingclear()
, instead, you can resetmarker
(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 theparent
value provided at construction time, the arraymarker
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
istrue
), the arraymarker
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
andcutPoints
, too, provide useful information. In particular, the nodes inqueue
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 it.unimi.dsi.fastutil.ints.IntArrayList
cutPoints
At the end of a visit, the cutpoints ofqueue
.ImmutableGraph
graph
The graph under examination.java.util.concurrent.atomic.AtomicIntegerArray
marker
boolean
parent
Whethermarker
contains parent nodes or round numbers.it.unimi.dsi.fastutil.ints.IntArrayList
queue
The queue of visited nodes.int
round
-
Constructor Summary
Constructors Constructor Description ParallelBreadthFirstVisit(ImmutableGraph graph, int requestedThreads, boolean parent, it.unimi.dsi.logging.ProgressLogger pl)
Creates a new class for keeping track of the state of parallel breadth-first visits.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description void
clear()
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.
-
-
-
Field Detail
-
graph
public final ImmutableGraph graph
The graph under examination.
-
queue
public final it.unimi.dsi.fastutil.ints.IntArrayList queue
The queue of visited nodes.
-
cutPoints
public final it.unimi.dsi.fastutil.ints.IntArrayList cutPoints
At the end of a visit, the cutpoints ofqueue
. 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
Whethermarker
contains parent nodes or round numbers.
-
marker
public final java.util.concurrent.atomic.AtomicIntegerArray marker
-
round
public int round
-
-
Constructor Detail
-
ParallelBreadthFirstVisit
public ParallelBreadthFirstVisit(ImmutableGraph graph, int requestedThreads, boolean parent, it.unimi.dsi.logging.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 forRuntime.availableProcessors()
).parent
- if true,marker
will contain parent nodes; otherwise, it will contain round numbers.pl
- a progress logger, ornull
.
-
-
Method Detail
-
clear
public void clear()
-
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. Callsclear()
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.
-
-