|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectit.unimi.dsi.webgraph.algo.ParallelBreadthFirstVisit
public class ParallelBreadthFirstVisit
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.
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.
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.
Note, however, 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 | |
---|---|
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 | |
---|---|
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 | |
---|---|
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 Detail |
---|
public final ImmutableGraph graph
public final IntArrayList queue
public final IntArrayList cutPoints
queue
. The d-th 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 AtomicIntegerArray 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.
public int round
marker
if parent
is false).
Constructor Detail |
---|
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
.Method Detail |
---|
public void clear()
marker
entries and round
to -1.
public int visit(int start)
This method will increment round
.
start
- the starting node.
visit(int,int)
public int visit(int start, int 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(int, int)
on all nodes as threads are created just once.
public int nodeAtMaxDistance()
public int maxDistance()
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |