Struct DynamicConnectivity 

pub struct DynamicConnectivity { /* private fields */ }

Dynamic connectivity data structure with Euler Tour Tree backend

Maintains connected components of an undirected graph with support for edge insertions and deletions. Uses Euler Tour Trees for O(log n) operations with union-find fallback for robustness.

Examples

let mut dc = DynamicConnectivity::new();
dc.add_vertex(0);
dc.add_vertex(1);
dc.add_vertex(2);

dc.insert_edge(0, 1);
assert!(dc.connected(0, 1));
assert!(!dc.connected(0, 2));

dc.insert_edge(1, 2);
assert!(dc.is_connected()); // All vertices connected

dc.delete_edge(1, 2);
assert!(!dc.connected(0, 2));

Implementations

impl DynamicConnectivity

pub fn new() -> Self

Creates a new empty dynamic connectivity structure

Examples

let dc = DynamicConnectivity::new();
assert_eq!(dc.component_count(), 0);

pub fn add_vertex(&mut self, v: VertexId)

Adds a vertex to the connectivity structure

If the vertex already exists, this is a no-op. Each new vertex starts in its own component.

Arguments

• v - The vertex ID to add

Examples

let mut dc = DynamicConnectivity::new();
dc.add_vertex(0);
assert_eq!(dc.component_count(), 1);

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

Inserts an edge between two vertices

Automatically adds vertices if they don’t exist. If vertices are already connected, updates internal state but doesn’t change connectivity.

Arguments

• u - First vertex
• v - Second vertex

Time Complexity

O(log n) via Euler Tour Tree link operation

Examples

let mut dc = DynamicConnectivity::new();
dc.insert_edge(0, 1);
assert!(dc.connected(0, 1));

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

Deletes an edge between two vertices

Triggers a full rebuild of the data structure from the remaining edges. The ETT is also rebuilt to maintain O(log n) queries.

Arguments

• u - First vertex
• v - Second vertex

Time Complexity

O(m·α(n)) where m is the number of edges (includes ETT rebuild)

Examples

let mut dc = DynamicConnectivity::new();
dc.insert_edge(0, 1);
dc.delete_edge(0, 1);
assert!(!dc.connected(0, 1));

pub fn is_connected(&self) -> bool

Checks if the entire graph is connected (single component)

Returns

true if all vertices are in a single connected component, false otherwise

Time Complexity

O(1)

Examples

let mut dc = DynamicConnectivity::new();
dc.add_vertex(0);
dc.add_vertex(1);
assert!(!dc.is_connected());

dc.insert_edge(0, 1);
assert!(dc.is_connected());

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

Checks if two vertices are in the same connected component

Arguments

• u - First vertex
• v - Second vertex

Returns

true if vertices are connected, false otherwise. Returns false if either vertex doesn’t exist.

Time Complexity

O(α(n)) amortized via union-find with path compression

Examples

let mut dc = DynamicConnectivity::new();
dc.insert_edge(0, 1);
dc.insert_edge(1, 2);
assert!(dc.connected(0, 2));

pub fn connected_fast(&self, u: VertexId, v: VertexId) -> Option<bool>

Fast connectivity check using Euler Tour Tree (O(log n))

Returns None if ETT is out of sync and result is unreliable. Use connected() for the reliable version.

pub fn component_count(&self) -> usize

Returns the number of connected components

Returns

The current number of connected components

pub fn vertex_count(&self) -> usize

Returns the number of vertices

Returns

The current number of vertices

Trait Implementations

impl Clone for DynamicConnectivity

fn clone(&self) -> DynamicConnectivity

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for DynamicConnectivity

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

Formats the value using the given formatter.

impl Default for DynamicConnectivity

fn default() -> Self

Returns the “default value” for a type.