pub struct ExpanderDecomposition { /* private fields */ }Expand description
Hierarchical expander decomposition
Maintains a multi-level decomposition where:
- Each level contains φ-expander components
- Lower levels have finer-grained components
- Higher levels have coarser-grained components
Implementations§
Source§impl ExpanderDecomposition
impl ExpanderDecomposition
Sourcepub fn build(graph: Arc<DynamicGraph>, phi: Conductance) -> Result<Self>
pub fn build(graph: Arc<DynamicGraph>, phi: Conductance) -> Result<Self>
Build expander decomposition with conductance threshold φ
Constructs a hierarchical decomposition where each component has conductance at least φ (or is maximal)
§Arguments
graph- The graph to decomposephi- Conductance threshold (typically 1/polylog(n))
§Returns
A hierarchical expander decomposition
Sourcepub fn component_at_level(
&self,
v: VertexId,
level: usize,
) -> Option<&ExpanderComponent>
pub fn component_at_level( &self, v: VertexId, level: usize, ) -> Option<&ExpanderComponent>
Get component containing vertex at given level
Sourcepub fn insert_edge(&mut self, u: VertexId, v: VertexId) -> Result<()>
pub fn insert_edge(&mut self, u: VertexId, v: VertexId) -> Result<()>
Update after edge insertion
Identifies affected components and rebuilds them if necessary
Sourcepub fn delete_edge(&mut self, u: VertexId, _v: VertexId) -> Result<()>
pub fn delete_edge(&mut self, u: VertexId, _v: VertexId) -> Result<()>
Update after edge deletion
Identifies affected components and rebuilds them if necessary
Sourcepub fn num_levels(&self) -> usize
pub fn num_levels(&self) -> usize
Get number of levels in the decomposition
Auto Trait Implementations§
impl Freeze for ExpanderDecomposition
impl !RefUnwindSafe for ExpanderDecomposition
impl Send for ExpanderDecomposition
impl Sync for ExpanderDecomposition
impl Unpin for ExpanderDecomposition
impl !UnwindSafe for ExpanderDecomposition
Blanket Implementations§
Source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere
T: ?Sized,
Source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
Mutably borrows from an owned value. Read more
Source§impl<T> IntoEither for T
impl<T> IntoEither for T
Source§fn into_either(self, into_left: bool) -> Either<Self, Self>
fn into_either(self, into_left: bool) -> Either<Self, Self>
Converts
self into a Left variant of Either<Self, Self>
if into_left is true.
Converts self into a Right variant of Either<Self, Self>
otherwise. Read moreSource§fn into_either_with<F>(self, into_left: F) -> Either<Self, Self>
fn into_either_with<F>(self, into_left: F) -> Either<Self, Self>
Converts
self into a Left variant of Either<Self, Self>
if into_left(&self) returns true.
Converts self into a Right variant of Either<Self, Self>
otherwise. Read more