Struct ReplacementEdgeIndex 

pub struct ReplacementEdgeIndex { /* private fields */ }

Level-based replacement edge index for O(log n) lookup

Organizes non-tree edges by level, enabling efficient replacement edge discovery when tree edges are deleted.

Complexity

• Lookup: O(log n) amortized
• Insert: O(log n)
• Delete: O(log n)

Implementations

impl ReplacementEdgeIndex

pub fn new(n: usize) -> Self

Create a new replacement edge index

pub fn add_tree_edge(&mut self, u: VertexId, v: VertexId)

Add a tree edge

pub fn remove_tree_edge(&mut self, u: VertexId, v: VertexId) -> bool

Remove a tree edge (returns if it was present)

pub fn add_non_tree_edge(&mut self, u: VertexId, v: VertexId)

Add a non-tree edge at level 0

pub fn remove_non_tree_edge(&mut self, u: VertexId, v: VertexId)

Remove a non-tree edge

pub fn find_replacement( &mut self, u: VertexId, v: VertexId, tree_adjacency: &HashMap<VertexId, HashSet<VertexId>>, ) -> Option<EdgeKey>

Find a replacement edge for deleted tree edge (u, v)

Returns Some((x, y)) if a replacement exists, None if components disconnect.

Complexity

O(log n) amortized through level-based search

pub fn find_replacement_fast( &self, smaller_component: &HashSet<VertexId>, ) -> Option<EdgeKey>

Fast replacement lookup when components are already known

Complexity

O(log n) - binary search through levels

pub fn stats(&self) -> ReplacementIndexStats

Get statistics about the index

Trait Implementations

impl Clone for ReplacementEdgeIndex

fn clone(&self) -> ReplacementEdgeIndex

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for ReplacementEdgeIndex

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

Formats the value using the given formatter.