Struct Seq

pub struct Seq<G: RandomAccessGraph> { /* private fields */ }

A sequential breadth-first visit.

This implementation uses an algorithm that is slightly different from the classical textbook algorithm, as we do not store parents or distances of the nodes from the root: Parents and distances are computed on the fly and passed to the callback function by visiting nodes when they are discovered, rather than when they are extracted from the queue.

This approach requires inserting a level separator between nodes at different distances: to obtain this result in a compact way, nodes are represented using NonMaxUsize, so the None variant of Option<NonMaxUsize> can be used as a separator.

Examples

Let’s compute the distances from 0:

use webgraph_algo::visits::*;
use webgraph::graphs::vec_graph::VecGraph;
use webgraph::labels::proj::Left;
use std::ops::ControlFlow::Continue;
use no_break::NoBreak;

let graph = VecGraph::from_arcs([(0, 1), (1, 2), (2, 0), (1, 3)]);
let mut visit = breadth_first::Seq::new(&graph);
let mut d = [0; 4];
visit.visit(
    [0],
    |event| {
         // Set distance from 0
         if let breadth_first::EventPred::Unknown { node, distance, .. } = event {
             d[node] = distance;
         }
         Continue(())
    },
).continue_value_no_break();

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

Here instead we compute the size of the ball of radius two around node 0: to minimize resource usage, we count nodes in the filter function, rather than as the result of an event. In this way, node at distance two are counted but not included in the queue, as it would happen if we were counting during an EventPred::Unknown event.

use std::convert::Infallible;
use webgraph_algo::visits::*;
use webgraph::graphs::vec_graph::VecGraph;
use webgraph::labels::proj::Left;
use std::ops::ControlFlow::Continue;
use no_break::NoBreak;

let graph = VecGraph::from_arcs([(0, 1), (1, 2), (2, 3), (3, 0), (2, 4)]);
let mut visit = breadth_first::Seq::new(&graph);
let mut count = 0;
visit.visit_filtered(
    [0],
    |event| { Continue(()) },
    |breadth_first::FilterArgsPred { distance, .. }| {
        if distance > 2 {
            false
        } else {
            count += 1;
            true
        }
    },
).continue_value_no_break();
assert_eq!(count, 3);

Implementations

impl<G: RandomAccessGraph> Seq<G>

pub fn new(graph: G) -> Self

Creates a new sequential visit.

Arguments

• graph: an immutable reference to the graph to visit.

Trait Implementations

impl<G: RandomAccessGraph> Sequential<EventPred> for Seq<G>

fn visit_filtered_with<R: IntoIterator<Item = usize>, T, E, C: FnMut(&mut T, EventPred) -> ControlFlow<E, ()>, F: FnMut(&mut T, FilterArgsPred) -> bool>( &mut self, roots: R, init: T, callback: C, filter: F, ) -> 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 visit_filtered<R: IntoIterator<Item = usize>, E, C: FnMut(A) -> ControlFlow<E, ()>, F: FnMut(A::FilterArgs) -> bool>( &mut self, roots: R, callback: C, filter: F, ) -> ControlFlow<E, ()>

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

fn visit_with<R: IntoIterator<Item = usize>, T, E, C: FnMut(&mut T, A) -> ControlFlow<E, ()>>( &mut self, roots: R, init: T, callback: C, ) -> ControlFlow<E, ()>

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

fn visit<R: IntoIterator<Item = usize>, E, C: FnMut(A) -> ControlFlow<E, ()>>( &mut self, roots: R, callback: C, ) -> ControlFlow<E, ()>

Visits the graph from the specified nodes.