Struct AdjacencyEdgeDict

pub struct AdjacencyEdgeDict<const ONE_WAY: bool> { /* private fields */ }

Sparse, edge first, adjacency list

Space Complexity

• $O(|V|+|E|)$ for undirected graph
• $O(|V|+2|E|)$ for directed graph

Node Time Complexity

This structure has very good performance for nodes

• Insert: $O\left(1\right)$
• Query: $O\left(1\right)$
• Removal: $O\left(1\right)$
• Count: $O\left(1\right)$
• Neighbors: $O\left(1\right)$

Edge Time Complexity

This structure has linear complexity across the edges

• Insert edge: $O\left(1\right)$
• Query edge: $O\left(|V|\right)$
• Removal edge: $O\left(|V|\right)$
• Count edges: $O\left(|V|\right)$

Trait Implementations

impl<const ONE_WAY: bool> Debug for AdjacencyEdgeDict<ONE_WAY>

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

Formats the value using the given formatter.