Struct BitGraph

pub struct BitGraph { /* private fields */ }

A BitGraph is an undirected graph data structure Its capacity is limited to mem::size_of::<usize>.pow(4)

Implementations

impl BitGraph

pub fn with_capacity(capacity: u32) -> BitGraph

Creates a new BitGraph preallocated with up to capacity vertices It is not possible later add vertices >= capacity

pub fn complete(capacity: u32) -> BitGraph

Creates a new BitGraph with capacity vertices, with all vertices connected to each other. It is not possible later add vertices >= capacity

pub fn add_edge(&mut self, u: u32, v: u32)

Adds a new undirected edge from u to v If the edge already exists, the graph is not updated It is not possible to add edges with endpoints >= capacity

pub fn add_edge_unchecked(&mut self, u: u32, v: u32)

Same as add_edge except that no boundary checks are performed. Can corrupt the underlying data

pub fn remove_edge(&mut self, u: u32, v: u32)

Removes the edge from u to v after performing boundary checks. If the edge is not present the graph is not updated

pub fn remove_edge_unchecked(&mut self, u: u32, v: u32)

Same as remove_edge except that no boundary checks are performed Can corrupt the underlying data

pub fn contract_edge(&mut self, target: u32, source: u32)

Contracts the edge (target, source) by adding all neighbors of source to target and removing source

pub fn contract_edge_unchecked(&mut self, target: u32, source: u32)

Same as contract_edge without any boundary checks This is very unsafe, and can corrupt the entire graph if the function is called with invalid arguments

pub fn neighbors(&self, v: u32) -> BitIter<&BitSet>

Returns an iterator over the neighborhood of vertex v

pub fn order(&self) -> u32

Number of vertices in the graph

pub fn degree(&self, v: u32) -> u32

Number of neighbors of v

pub fn dfs(&self, v: u32) -> DfsIterator<'_>

Returns a DfsIterator starting at vertex v

Trait Implementations

impl Clone for BitGraph

fn clone(&self) -> BitGraph

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for BitGraph

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

Formats the value using the given formatter.