Struct PredecessorTree

#[non_exhaustive]
pub struct PredecessorTree {
    pub pred: Vec<Option<usize>>,
}

A predecessor tree.

A PredecessorTree contains each vertex’s predecessor on the shortest path from the source vertex.

Examples

This PredecessorTree is generated by BfsPred::predecessors.

The path from vertex 0 is red. The dashed arcs mark the PredecessorTree.

use {
    graaf::{
        AddArc,
        AdjacencyList,
        BfsPred,
        Empty,
        PredecessorTree,
    },
    std::iter::once,
};

let mut digraph = AdjacencyList::empty(6);

digraph.add_arc(0, 1);
digraph.add_arc(1, 2);
digraph.add_arc(1, 4);
digraph.add_arc(2, 5);

assert!(BfsPred::new(&digraph, once(0))
    .predecessors()
    .into_iter()
    .eq([None, Some(0), Some(1), None, Some(1), Some(2)]));

Fields (Non-exhaustive)

Non-exhaustive structs could have additional fields added in future. Therefore, non-exhaustive structs cannot be constructed in external crates using the traditional Struct { .. } syntax; cannot be matched against without a wildcard ..; and struct update syntax will not work.

pred: Vec<Option<usize>>

The predecessors of each vertex.

Implementations

impl PredecessorTree

pub fn new(order: usize) -> Self

Construct a PredecessorTree with a given order.

Arguments

• order: The number of vertices in the PredecessorTree.

Panics

Panics if order is zero.

Examples

use graaf::PredecessorTree;

assert!(PredecessorTree::new(4)
    .into_iter()
    .eq([None, None, None, None]));

pub fn search(&self, s: usize, t: usize) -> Option<Vec<usize>>

Search a PredecessorTree for a path from a source vertex to a target vertex.

Arguments

• s: The source vertex.
• t: The target vertex.

Returns

If a path from s to t is found, the function returns it. Otherwise, returns None.

Examples

use graaf::PredecessorTree;

let pred = PredecessorTree::from(vec![Some(1), Some(2), Some(3), None]);

assert!(pred.search(0, 3).into_iter().eq(Some(vec![0, 1, 2, 3])));

pub fn search_by<F>(&self, s: usize, is_target: F) -> Option<Vec<usize>>

where F: Fn(&usize, &Option<usize>) -> bool,

Search a PredecessorTree for a path from a source vertex to a vertex that satisfies a predicate.

Arguments

• s: The source vertex.
• is_target: A predicate determining if a vertex is the target.

Returns

If it finds a target, it returns the path from the source to the target. Otherwise, it returns None.

Panics

Panics if s isn’t in the path.

Examples

use graaf::PredecessorTree;

let pred = PredecessorTree::from(vec![Some(1), Some(2), Some(3), None]);

assert!(pred
    .search_by(0, |&v, _| v > 1)
    .into_iter()
    .eq(Some(vec![0, 1, 2])));

let pred =
    PredecessorTree::from(vec![Some(1), Some(2), Some(3), None, Some(0)]);

assert!(pred
    .search_by(0, |_, v| v.is_none())
    .into_iter()
    .eq(Some(vec![0, 1, 2, 3])));

Trait Implementations

impl Clone for PredecessorTree

fn clone(&self) -> PredecessorTree

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for PredecessorTree

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl From<Vec<Option<usize>>> for PredecessorTree

fn from(pred: Vec<Option<usize>>) -> Self

Converts to this type from the input type.

impl Hash for PredecessorTree

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl Index<usize> for PredecessorTree

type Output = Option<usize>

The returned type after indexing.

fn index(&self, index: usize) -> &Self::Output

Performs the indexing (container[index]) operation.

impl IndexMut<usize> for PredecessorTree

fn index_mut(&mut self, index: usize) -> &mut Self::Output

Performs the mutable indexing (container[index]) operation.

impl IntoIterator for PredecessorTree

type IntoIter = IntoIter<<PredecessorTree as IntoIterator>::Item>

Which kind of iterator are we turning this into?

type Item = Option<usize>

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl Ord for PredecessorTree

fn cmp(&self, other: &PredecessorTree) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

where Self: Sized,

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

where Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

where Self: Sized,

Restrict a value to a certain interval.

impl PartialEq for PredecessorTree

fn eq(&self, other: &PredecessorTree) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl PartialOrd for PredecessorTree

fn partial_cmp(&self, other: &PredecessorTree) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, other: &Rhs) -> bool

Tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &Rhs) -> bool

Tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, other: &Rhs) -> bool

Tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &Rhs) -> bool

Tests greater than or equal to (for self and other) and is used by the >= operator.

impl Eq for PredecessorTree

impl StructuralPartialEq for PredecessorTree