public class ParallelBreadthFirstVisit extends Object
To use this class you first create an instance, and then invoke visit(long)
. If you want perform
more visits preserving the marker
state you can invoke visit(long)
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 “big array“ marker
field to discover details about the visit.
Depending on the parent
value provided at construction time, 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 connectedcomponent index if the graph is symmetric.
Observe that in the former case (if parent
is true
), 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(long)
, queue
and cutPoints
, too, provide useful information. In
particular, the nodes in queue
from the dth to the (d +1)th cutpoint
are exactly the nodes at distance d from the source.
This class needs three longs per node. If there are several available cores, breadthfirst 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.
Modifier and Type  Field and Description 

LongBigArrayBigList 
cutPoints
At the end of a visit, the cutpoints of
queue . 
ImmutableGraph 
graph
The graph under examination.

AtomicLongArray[] 
marker

boolean 
parent
Whether
marker contains parent nodes or round numbers. 
LongBigArrayBigList 
queue
The queue of visited nodes.

long 
round

Constructor and Description 

ParallelBreadthFirstVisit(ImmutableGraph graph,
int requestedThreads,
boolean parent,
ProgressLogger pl)
Creates a new class for keeping track of the state of parallel breadthfirst visits.

Modifier and Type  Method and Description 

void 
clear()

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

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

long 
visit(long start)
Performs a breadthfirst visit of the given graph starting from the given node.

long 
visit(long start,
long expectedSize)
Performs a breadthfirst visit of the given graph starting from the given node.

void 
visitAll()
Visits all nodes.

public final ImmutableGraph graph
public final LongBigArrayBigList queue
public final LongBigArrayBigList cutPoints
queue
. The dth cutpoint is the first node in the queue at distance d. The
last cutpoint is the queue size.public final boolean parent
marker
contains parent nodes or round numbers.public final AtomicLongArray[] marker
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. It has the same form of a big array, but it is handled manually.public long round
public ParallelBreadthFirstVisit(ImmutableGraph graph, int requestedThreads, boolean parent, ProgressLogger pl)
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
.public void clear()
public long visit(long start)
This method will increment round
.
start
 the starting node.visit(long,long)
public long visit(long start, long expectedSize)
This method will increment round
if at least one node is visited.
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.public void visitAll()
clear()
initially.
This method is more efficient than invoking visit(long, long)
on all nodes as threads are created just once.
public long nodeAtMaxDistance()
public long maxDistance()