Struct SpanningTree 

pub struct SpanningTree {
    pub nodes: Vec<NodeInfo>,
    pub order: Vec<usize>,
}

A spanning tree representation of a graph. Parts of the graph may not be in the tree.

Fields

nodes: Vec<NodeInfo>

Information about the nodes in the spanning tree.

order: Vec<usize>

The order in which the nodes were visited in the DFS.

Implementations

impl SpanningTree

pub fn is_connected(&self) -> bool

pub fn chain_decomposition(&mut self)

Assign chain ids to the nodes and back-edges in the spanning tree.

pub fn count_bridges(&self) -> usize

Count non-external bridge nodes. Make sure to call Self::chain_decomposition first.

pub fn bridges(&self) -> impl Iterator<Item = usize>

Get non-external bridge nodes. Make sure to call Self::chain_decomposition first.

pub fn has_zero_flow_bridges(&self) -> bool

Detect if the graph has zero-flow bridges. This only works when the root node is an external node (if there are any).

Trait Implementations

impl Clone for SpanningTree

fn clone(&self) -> SpanningTree

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for SpanningTree

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

Formats the value using the given formatter.