Struct graph::step::Step

pub struct Step<S = f32, Ix = DefaultIx> {
    pub caller: Option<Rc<Step<S, Ix>>>,
    pub idx: NodeIndex<Ix>,
    pub rel: Option<EdgeIndex<Ix>>,
    pub state: S,
}

A single step in the graph

Steps are the way we compute and represent the graph traversal with the various algorithms.

Steps can store a type S which can be used to hold any information like total weight or any other primitive or structure.

The Step type is a singly linked list, where each step has a reference to its parent. It is a singly linked list because we only need to go backwards to the root node to get the path.

Fields

caller: Option<Rc<Step<S, Ix>>>

The parent State that invoked this instance. If the option is None then it means we arrived to the root state.

idx: NodeIndex<Ix>

The current node index the step is at within the graph.

rel: Option<EdgeIndex<Ix>>

The index of the edge that binds caller -> self

state: S

State of the walking progress

Implementations

impl<S, Ix: IndexType> Step<S, Ix>

pub fn collect_nodes(&self) -> Vec<NodeIndex<Ix>>

Returns the nodes that were traversed to reach this step.

It starts from the target node and goes backwards to the root node. To get the nodes in the correct order, you need to reverse the result with rev().

This is an O(n) operation.

pub fn collect_edges(&self) -> Vec<EdgeIndex<Ix>>

Returns the edges that were traversed to reach this step.

It starts from the target node and goes backwards to the root node. To get the edges in the correct order, you need to reverse the result with rev().

This is an O(n) operation.

pub fn chain_size(&self) -> usize

Returns the size of the chain.

This is an O(n) operation.

pub fn from_slice<I, N, E, Ty: EdgeType, F>( indices: &[NodeIndex<Ix>], graph: &Graph<I, N, E, Ty, Ix>, state: F ) -> Step<S, Ix>where F: Fn(NodeIndex<Ix>, EdgeIndex<Ix>, NodeIndex<Ix>, &S) -> S, S: Default,

Creates a step chain from a slice of node indexes.

The cost of each step is computed with the state function F. The state function receives data regarding the current node and its parent, like current index, state of the parent step, binding edge between the parent step and the current index, etc.

With this data the user should be able to compute any desired state for each step in the chain.

The arguments of the state function are, in order:

• parent index
• edge between parent and current
• current index
• parent state

pub fn iter(&self) -> Iter<'_, S, Ix>

Returns an iterator visiting all the steps in the chain

Trait Implementations

impl<S: Clone, Ix: Clone> Clone for Step<S, Ix>

fn clone(&self) -> Self

Clone the step chain.

The new chain is a deep copy of the original chain.

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

Performs copy-assignment from source.

impl<S: Debug, Ix: Debug> Debug for Step<S, Ix>

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

Formats the value using the given formatter.

impl<S: Default, Ix: Default> Default for Step<S, Ix>

fn default() -> Step<S, Ix>

Returns the “default value” for a type.