Crate adjacency_list

Expand description

§Title

Structs§

AdjacencyEdgeDict

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 (1)$
Query: $O (1)$
Removal: $O (1)$
Count: $O (1)$
Neighbors: $O (1)$

Edge Time Complexity

This structure has linear complexity across the edges

Insert edge: $O (1)$
Query edge: $O (| V |)$
Removal edge: $O (| V |)$
Count edges: $O (| V |)$

AdjacencyNodeList

Sparse, node first, adjacency list

Space Complexity

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

Node Time Complexity

This structure has very good performance for nodes

Insert: $O (1)$
Query: $O (1)$
Removal: $O (1)$
Count: $O (1)$
Neighbors: $O (1)$

Edge Time Complexity

This structure has linear complexity across the edges

Insert edge: $O (1)$
Query edge: $O (| V |)$
Removal edge: $O (| V |)$
Count edges: $O (| V |)$

EdgeFirstAllBridges

EdgeFirstAllEdges

EdgeFirstAllNodes

EdgeFirstFindBridges

EdgeFirstFindNeighbors

Type Aliases§

DiGraphAED: Sparse adjacency list, edge-first directed graph
DiGraphAEL: Dense adjacency list, edge-first directed graph
DiGraphAND: Sparse adjacency list, node-first directed graph
DiGraphANL: Dense adjacency list, node-first directed graph
UnGraphAED: Sparse adjacency list, edge-first undirected graph
UnGraphAEL: Dense adjacency list, edge-first undirected graph
UnGraphAND: Sparse adjacency list, node-first undirected graph
UnGraphANL: Dense adjacency list, node-first undirected graph