Struct graaf::algo::breadth_first_tree::BreadthFirstTree

pub struct BreadthFirstTree { /* private fields */ }

A breadth-first tree.

Implementations

impl BreadthFirstTree

pub fn new(order: usize) -> Self

Creates a breadth-first tree.

Arguments

• pred: The predecessor of each vertex on the shortest path from the source.

Panics

Panics if order is zero.

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

Searches a breadth-first tree for a path from a source vertex to a target vertex.

Arguments

• s: The source vertex of the path.
• t: The target vertex of the path.

Returns

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

Examples

use graaf::algo::breadth_first_tree::BreadthFirstTree;

let pred = BreadthFirstTree::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,

Searches a breadth-first tree for a path from a source vertex to a target vertex that satisfies a predicate.

Arguments

• s: The source vertex of the path.
• is_target: A predicate determining whether 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 is not in the path.

Examples

use graaf::algo::breadth_first_tree::BreadthFirstTree;

let pred = BreadthFirstTree::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])));

use graaf::algo::breadth_first_tree::BreadthFirstTree;

let pred = BreadthFirstTree::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 BreadthFirstTree

fn clone(&self) -> BreadthFirstTree

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for BreadthFirstTree

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

Formats the value using the given formatter.

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

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

Converts to this type from the input type.

impl Hash for BreadthFirstTree

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 BreadthFirstTree

type Output = Option<usize>

The returned type after indexing.

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

Performs the indexing (container[index]) operation.

impl IndexMut<usize> for BreadthFirstTree

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

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

impl IntoIterator for BreadthFirstTree

type IntoIter = IntoIter<<BreadthFirstTree 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 BreadthFirstTree

fn cmp(&self, other: &BreadthFirstTree) -> 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 + PartialOrd,

Restrict a value to a certain interval.

impl PartialEq for BreadthFirstTree

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

This method tests for self and other values to be equal, and is used by ==.

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

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

impl PartialOrd for BreadthFirstTree

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

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

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

This method tests less than (for self and other) and is used by the < operator.

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

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

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

This method tests greater than (for self and other) and is used by the > operator.

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

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

impl Eq for BreadthFirstTree

impl StructuralPartialEq for BreadthFirstTree