Struct IncrementalScc 

pub struct IncrementalScc { /* private fields */ }

Incremental SCC tracker over a mutable directed graph.

Implementations

impl IncrementalScc

pub fn new(graph: DynamicGraph) -> GraphalgResult<Self>

Build the tracker, computing the initial SCC partition with Tarjan.

pub fn num_nodes(&self) -> usize

Number of vertices.

pub fn num_components(&self) -> usize

Number of strongly-connected components.

pub fn component_of(&self, v: usize) -> GraphalgResult<usize>

Dense component id of vertex v.

pub fn same_component(&self, u: usize, v: usize) -> GraphalgResult<bool>

Whether u and v are in the same SCC (mutually reachable).

pub fn components(&self) -> Vec<Vec<usize>>

The component partition as sorted vertex lists, each list sorted and the outer list ordered by smallest member.

pub fn graph(&self) -> &DynamicGraph

Borrow the underlying graph.

pub fn apply_insert(&mut self, u: usize, v: usize) -> GraphalgResult<()>

Insert directed edge u → v and update the partition incrementally.

pub fn apply_remove(&mut self, u: usize, v: usize) -> GraphalgResult<()>

Remove directed edge u → v and update the partition incrementally.

Removing an edge never changes any vertex’s current component label, so the affected-component test inside handle_remove can safely read comp_of after the graph mutation.

pub fn apply_batch( &mut self, updates: &[(usize, usize, bool)], ) -> GraphalgResult<()>

Apply a batch of (u, v, is_insert) updates, maintaining the partition after each one.

Trait Implementations

impl Clone for IncrementalScc

fn clone(&self) -> IncrementalScc

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for IncrementalScc

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

Formats the value using the given formatter.