Struct SeqIter

pub struct SeqIter<'a, S, G: RandomAccessGraph, P, const PRED: bool> { /* private fields */ }

Sequential depth-first visits.

This is an iterative implementation that does not need a large stack size.

There are three version of the visit, which are type aliases to the same common implementation: SeqNoPred, SeqPred and SeqPath (the generic implementation should not be instantiated by the user).

• SeqNoPred does not keep track of predecessors, nor of nodes on the stack; it can be used, for example, to compute reachability information.
• SeqPred keeps track of predecessors, but not of nodes on the stack; it can be used, for example, to compute a topological sort.
• SeqPath keeps track of predecessors and nodes on the stack; it can be used, for example, to establish acyclicity).

Each type of visit uses incrementally more space:

• SeqNoPred uses one bit per node to remember known nodes and a stack of iterators, one for each node on the visit path.
• SeqPred uses one bit per node to remember known nodes and a stack of pairs made of an iterator and a predecessor, one for each node on the visit path.
• SeqPath uses two bits per node to remember known nodes and whether the node is on the visit path, and a stack of pairs made of an iterator and a predecessor, one for each node on the visit path.

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

• SeqNoPred generates events of type EventNoPred.
• SeqPred generates events of type EventPred, with the proviso that the Boolean associated with events of type Revisit is always false.
• SeqPath generates events of type EventPred.

With respect to EventNoPred, EventPred provides the predecessor of the current node and a postvisit event.

If the visit was interrupted, the nodes still on the visit path can be retrieved using the stack method (only for SeqPred and SeqPath).

Examples

Let’s test acyclicity:

use webgraph_algo::visits::*;
use webgraph_algo::visits::depth_first::*;
use webgraph::graphs::vec_graph::VecGraph;
use webgraph::traits::SequentialLabeling;
use webgraph::labels::proj::Left;
use std::ops::ControlFlow::*;

let graph = VecGraph::from_arcs([(0, 1), (1, 2), (2, 0), (1, 3)]);
let mut visit = depth_first::SeqPath::new(&graph);

assert!(visit.visit(
    0..graph.num_nodes(),
    |event| {
        match event {
            // Stop the visit as soon as a back edge is found
            EventPred::Revisit { on_stack: true, .. } => Break(StoppedWhenDone),
            _ => Continue(()),
        }
    },
).is_break()); // As the graph is not acyclic

Or, assuming the input is acyclic, let us compute the reverse of a topological sort:

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

let graph = VecGraph::from_arcs([(0, 1), (1, 2), (1, 3), (0, 3)]);
let mut visit = depth_first::SeqPred::new(&graph);
let mut top_sort = Vec::with_capacity(graph.num_nodes());

visit.visit(
    0..graph.num_nodes(),
    |event| {
        if let EventPred::Postvisit { node, .. } = event {
            top_sort.push(node);
        }
        Continue(())
    }
).continue_value_no_break();

Implementations

impl<'a, S: NodeStates, G: RandomAccessGraph, P, const PRED: bool> SeqIter<'a, S, G, P, PRED>

pub fn new(graph: &'a G) -> SeqIter<'a, S, G, P, PRED>

Creates a new sequential visit.

Arguments

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

impl<'a, S, G: RandomAccessGraph> SeqIter<'a, S, G, usize, true>

pub fn stack(&mut self) -> StackIterator<'a, '_, S, G>

Returns an iterator over the nodes still on the visit path, except for the last one.

Node will be returned in reverse order of visit.

This method is useful only in the case of interrupted visits, as in a completed visit the stack will be empty. The last node on the visit path at the moment of the interruption must be treated separately.

Trait Implementations

impl<S: NodeStates, G: RandomAccessGraph> Sequential<EventPred> for SeqIter<'_, S, G, usize, true>

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.