Struct ParFair

pub struct ParFair<G: RandomAccessGraph, const PRED: bool = false> { /* private fields */ }

Fair parallel breadth-first visits.

“Fairness” refers to the fact that the visit is parallelized by dividing the visit queue in chunks of approximately equal size; threads consume the chunks, and visit the associated nodes. Thus, the visiting cost is distributed evenly among the threads, albeit the work done on the enumeration of successors depends on the sum of the outdegrees nodes in a chunk, which might differ significantly between chunks.

There are two version of the visit, which are type aliases to the same common implementation: ParFairNoPred and ParFairPred.

• ParFairNoPred does not keep track of predecessors; it can be used, for example, to compute distances.
• ParFairPred keeps track of predecessors; it can be used, for example, to compute a visit tree.

Each type of visit uses incrementally more space:

• ParFairNoPred uses one bit per node to remember known nodes and a queue of usize representing nodes;
• ParFairPred uses one bit per node to remember known nodes and a queue of pairs of usize representing nodes and their parents.

If you need predecessors but the cost of the callbacks is not significant you can use a low-memory parallel visit instead.

The visits differ also in the type of events they generate:

• ParFairNoPred generates events of type EventNoPred.
• ParFairPred generates events of type EventPred.

With respect to EventNoPred, EventPred provides the predecessor of the current node.

Examples

Let’s compute the distances from 0. We will be using a SyncSlice from the sync_cell_slice crate to store the parent of each node.

use webgraph_algo::visits::Parallel;
use webgraph_algo::visits::breadth_first::{*, self};
use webgraph_algo::thread_pool;
use webgraph::graphs::vec_graph::VecGraph;
use webgraph::labels::proj::Left;
use std::sync::atomic::AtomicUsize;
use std::sync::atomic::Ordering;
use std::ops::ControlFlow::Continue;
use sync_cell_slice::SyncSlice;
use no_break::NoBreak;

let graph = VecGraph::from_arcs([(0, 1), (1, 2), (2, 0), (1, 3)]);
let mut visit = breadth_first::ParFairNoPred::new(&graph);
let mut d = [0_usize; 4];
let mut d_sync = d.as_sync_slice();
visit.par_visit(
    [0],
    |event| {
        // Set distance from 0
        if let EventNoPred::Unknown { node, distance, ..} = event {
            // There will be exactly one set for each node
            unsafe { d_sync[node].set(distance) };
        }
        Continue(())
    },
   &thread_pool![],
).continue_value_no_break();

assert_eq!(d[0], 0);
assert_eq!(d[1], 1);
assert_eq!(d[2], 2);
assert_eq!(d[3], 2);

Implementations

impl<G: RandomAccessGraph, const P: bool> ParFair<G, P>

pub fn new(graph: G) -> Self

Creates a fair parallel breadth-first visit.

This constructor uses a default granularity of 128 nodes. Use with_granularity to set a different granularity.

Arguments

• graph: the graph to visit.

pub fn with_granularity(graph: G, granularity: Granularity) -> Self

Creates a fair parallel breadth-first visit.

Arguments

• graph: the graph to visit.

• granularity: High granularity reduces overhead, but may lead to decreased performance on graphs with a skewed outdegree distribution. From this parameter, we derive a node granularity.

Trait Implementations

impl<G: RandomAccessGraph + Sync> Parallel<EventNoPred> for ParFair<G, false>

fn par_visit_filtered_with<R: IntoIterator<Item = usize>, T: Clone + Send + Sync, E: Send, C: Fn(&mut T, EventNoPred) -> ControlFlow<E, ()> + Sync, F: Fn(&mut T, FilterArgsNoPred) -> bool + Sync>( &mut self, roots: R, init: T, callback: C, filter: F, thread_pool: &ThreadPool, ) -> ControlFlow<E, ()>

Visits the graph from the specified nodes with an initialization value and a filter function.

fn reset(&mut self)

Resets the visit status, making it possible to reuse it.

fn par_visit_filtered<R: IntoIterator<Item = usize>, E: Send, C: Fn(A) -> ControlFlow<E, ()> + Sync, F: Fn(A::FilterArgs) -> bool + Sync>( &mut self, roots: R, callback: C, filter: F, thread_pool: &ThreadPool, ) -> ControlFlow<E, ()>

Visits the graph from the specified nodes with a filter function.

fn par_visit_with<R: IntoIterator<Item = usize>, T: Clone + Send + Sync, E: Send, C: Fn(&mut T, A) -> ControlFlow<E, ()> + Sync>( &mut self, roots: R, init: T, callback: C, thread_pool: &ThreadPool, ) -> ControlFlow<E, ()>

Visits the graph from the specified nodes with an initialization value.

fn par_visit<R: IntoIterator<Item = usize>, E: Send, C: Fn(A) -> ControlFlow<E, ()> + Sync>( &mut self, roots: R, callback: C, thread_pool: &ThreadPool, ) -> ControlFlow<E, ()>

Visits the graph from the specified nodes.

impl<G: RandomAccessGraph + Sync> Parallel<EventPred> for ParFair<G, true>

fn par_visit_filtered_with<R: IntoIterator<Item = usize>, T: Clone + Send + Sync, E: Send, C: Fn(&mut T, EventPred) -> ControlFlow<E, ()> + Sync, F: Fn(&mut T, <EventPred as Event>::FilterArgs) -> bool + Sync>( &mut self, roots: R, init: T, callback: C, filter: F, thread_pool: &ThreadPool, ) -> ControlFlow<E, ()>

Visits the graph from the specified nodes with an initialization value and a filter function.

fn reset(&mut self)

Resets the visit status, making it possible to reuse it.

fn par_visit_filtered<R: IntoIterator<Item = usize>, E: Send, C: Fn(A) -> ControlFlow<E, ()> + Sync, F: Fn(A::FilterArgs) -> bool + Sync>( &mut self, roots: R, callback: C, filter: F, thread_pool: &ThreadPool, ) -> ControlFlow<E, ()>

Visits the graph from the specified nodes with a filter function.

fn par_visit_with<R: IntoIterator<Item = usize>, T: Clone + Send + Sync, E: Send, C: Fn(&mut T, A) -> ControlFlow<E, ()> + Sync>( &mut self, roots: R, init: T, callback: C, thread_pool: &ThreadPool, ) -> ControlFlow<E, ()>

Visits the graph from the specified nodes with an initialization value.

fn par_visit<R: IntoIterator<Item = usize>, E: Send, C: Fn(A) -> ControlFlow<E, ()> + Sync>( &mut self, roots: R, callback: C, thread_pool: &ThreadPool, ) -> ControlFlow<E, ()>

Visits the graph from the specified nodes.