Struct PolylogConnectivity 

pub struct PolylogConnectivity { /* private fields */ }

Polylogarithmic worst-case dynamic connectivity

Maintains connectivity with O(log³ n) expected worst-case update time.

Example

use ruvector_mincut::connectivity::polylog::PolylogConnectivity;

let mut conn = PolylogConnectivity::new();
conn.insert_edge(0, 1);
conn.insert_edge(1, 2);

assert!(conn.connected(0, 2));

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

Implementations

impl PolylogConnectivity

pub fn new() -> Self

Create new empty connectivity structure

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

Insert an edge

Time complexity: O(log³ n) expected worst-case

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

Delete an edge

Time complexity: O(log³ n) expected worst-case

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

Check if two vertices are connected

Time complexity: O(log n) worst-case

pub fn is_connected(&self) -> bool

Check if the entire graph is connected

pub fn component_count(&self) -> usize

Get number of connected components

pub fn vertex_count(&self) -> usize

Get number of vertices

pub fn edge_count(&self) -> usize

Get number of edges

pub fn stats(&self) -> &PolylogStats

Get statistics

Trait Implementations

impl Debug for PolylogConnectivity

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

Formats the value using the given formatter.

impl Default for PolylogConnectivity

fn default() -> Self

Returns the “default value” for a type.