Expand description
Operations on graphs
These operations are modeled as traits that can be implemented by types
that represent graphs. The traits are implemented for combinations of
standard types like array, slice, Vec, BTreeMap,
BTreeSet, HashMap, and HashSet when the implementation has a
close-to-optimal complexity.
§Examples
extern crate alloc;
use {
alloc::collections::BTreeSet,
graaf::op::{
AddEdge,
Indegree,
Outdegree,
RemoveEdge,
},
};
let mut graph = vec![BTreeSet::new(); 3];
// 1 ← 0 → 2
graph.add_edge(0, 1);
graph.add_edge(0, 2);
assert_eq!(graph.outdegree(0), 2);
assert_eq!(graph.indegree(1), 1);
assert_eq!(graph.indegree(2), 1);
graph.remove_edge(0, 1);
assert_eq!(graph.outdegree(0), 1);
assert_eq!(graph.indegree(1), 0);
assert_eq!(graph.indegree(2), 1);§Supported types
§Adjacency list
§Unweighted
BTreeMap<usize, BTreeSet<usize>>BTreeMap<usize, Vec<usize>>HashMap<usize, HashSet<usize>>HashMap<usize, Vec<usize>>Vec<BTreeSet<usize>>Vec<HashSet<usize>>Vec<Vec<usize>>[BTreeSet<usize>; V][BTreeSet<usize>][HashSet<usize>; V][HashSet<usize>][Vec<usize>; V][Vec<usize>]
§Weighted
BTreeMap<usize, BTreeMap<usize, W>>BTreeMap<usize, BTreeSet<(usize, W)>>BTreeMap<usize, Vec<(usize, W)>>HashMap<usize, HashMap<usize, W>>HashMap<usize, HashSet<(usize, W)>>HashMap<usize, Vec<(usize, W)>>Vec<BTreeMap<usize, W>>Vec<BTreeSet<(usize, W)>>Vec<HashMap<usize, W>>Vec<HashSet<(usize, W)>>Vec<Vec<(usize, W)>>[BTreeMap<usize, W>; V][BTreeMap<usize, W>][BTreeSet<(usize, W)>; V][BTreeSet<(usize, W)>][HashMap<usize, W>; V][HashMap<usize, W>][HashSet<(usize, W)>; V][HashSet<(usize, W)>][Vec<(usize, W)>; V][Vec<(usize, W)>]
§Edge list
§Unweighted
BTreeSet<(usize, usize)>HashSet<(usize, usize)>Vec<(usize, usize)>[(usize, usize); V][(usize, usize)]
§Weighted
BTreeSet<(usize, usize, W)>HashSet<(usize, usize, W)>Vec<(usize, usize, W)>[(usize, usize, W); V][(usize, usize, W)]
Re-exports§
pub use add_edge::AddEdge;pub use add_weighted_edge::AddWeightedEdge;pub use count_all_edges::CountAllEdges;pub use count_all_vertices::CountAllVertices;pub use edge_weight::EdgeWeight;pub use indegree::Indegree;pub use is_edge::IsEdge;pub use is_simple::IsSimple;pub use iter_all_edges::IterAllEdges;pub use iter_all_weighted_edges::IterAllWeightedEdges;pub use iter_edges::IterEdges;pub use iter_vertices::IterVertices;pub use iter_weighted_edges::IterWeightedEdges;pub use outdegree::Outdegree;pub use remove_edge::RemoveEdge;pub use target::Target;
Modules§
- A trait to add an edge to an unweighted graph
- A trait to add a weighted edge to a graph
- A trait to count all edges in a graph
- A trait to count all vertices in a graph
- A trait to get the weight of a given edge
- A trait to get the indegree of a given vertex
- A trait to check if an edge exists between two vertices
- A trait to determine whether a graph is simple
- A trait to iterate over all unweighted edges in a graph
- A trait to iterate over all weighted edges in a graph
- A trait to iterate over all unweighted edges with a given source vertex
- A trait to iterate over all vertices in a graph
- A trait to iterate over all weighted edges with a given source vertex
- A trait to get the outdegree of a given vertex
- A trait to remove an edge from a graph
- A trait to get the target vertex of an adjacency list edge