First of all: thanks a lot for the feedback!
My prior approach was fundamentally flawed, simply because I thought about the whole memory-architecture wrong, so I sat down and did some more reading the book.
Here is what I came up with:
pub struct DirectedGraph<E>
where
E: Edge,
{
/// The owned edges.
edges: Vec<E>,
/// The indices of elements in `edges` where `e.left()` is equal to the key.
left: HashMap<E::Node, Vec<usize>>,
/// The indices of elements in `edges` where `e.right()` is equal to the key.
right: HashMap<E::Node, Vec<usize>>,
}
As @quinedot suggested using an index is probably the best way, because of the whole owning/borrowing system, I would have to have one copy of a potentially big Edge
struct per HashMap
, which is bonkers.
For the keys I decided to go with @steffahn 's suggestion to actually own them instead of borrowing, that made everything 1000% easier and cleaned up a lot of code. For iterators: I moved them to a different trait and implemented them separately.
Without further ado; here is the reworked code with some doc:
use std::{
collections::{HashMap, HashSet},
hash::Hash,
};
/// # Edge
/// An `Edge<Node>` also line connects a pair of nodes `left()` and `right()`.
/// How the connections is interpreted depends on the `Graph<Node, Edge>` the edges belong to.
///
/// ## Types
/// * `Node: Copy + Eq + Hash`
///
/// ## Functions
/// * `left(&self) -> Self::Node`: The left node of an `Edge<Node>`, is the origin of the edge, if the `Graph<Node, Edge>` is directed.
///
/// * `right(&self) -> Self::Node`: The right node of an `Edge<Node>`, is the target of the edge, if the `Graph<Node, Edge>` is directed.
///
pub trait Edge {
type Node: Copy + Eq + Hash;
/// ### Summary
/// The left node of an `Edge<Node>`, is the origin of the edge, if the `Graph<Node, Edge>` is directed.
fn left(&self) -> Self::Node;
/// ### Summary
/// The right node of an 'Edge', is the target of the edge, if the `Graph<Node, Edge>` is directed.
fn right(&self) -> Self::Node;
}
/// # Graph
///
/// A `Graph<Node, Edge>`
/// * ... is a structure in which pairs of object are related [more...](https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)).
/// * ... implementing this trait is not necessarily oriented or directed.
/// * ... can be represented as a set of `Self::Edge`s. Each edge owns a `left()` and `right()` node. Each node is connected to edges.
///
/// ## Types
/// * `Node: Copy + Eq + Hash`: The type of each node of the `Graph<Node, Edge>`.
/// * `Edge: Edge<Node = Self::Node>`: The type of each edge of the `Graph<Node, Edge>`.
///
/// ## Functions
/// * `insert(&mut self, edge: Self::Edge) -> bool`: Inserts an `Self::Edge` into the `Graph<Node, Edge>`
///
/// * `contains_edge(&self, edge: &Self::Edge) -> bool`: Indicates whether the `Graph<Node, Edge>` contains a node equal to the `Self::Node` provided.
///
/// * `adjacent(&self, x: &Self::Node, y: &Self::Node) -> Option<&Self::Edge>`: Returns the edge between two nodes if `x` and `y` are adjacent.
/// Adjacency is direction-agnostic, an edge from `x` to `y` and `y` to `x` are equivalent.
pub trait Graph {
/// ### Summary
/// The type of each node of the `Graph<Node, Edge>`.
///
/// ### Remarks
/// `Nodes` are often used as keys for `HashMap`s, and as such copied quite often. A `Node` should be as slim as possible.
type Node: Copy + Eq + Hash;
/// ### Summary
/// The type of each edge of the `Graph<Node, Edge>`.
///
/// ### Remarks
/// `self.left` and `self.right` should be as slim as possible, as the references are used for comparisons. Preferably field accessors.
type Edge: Edge<Node = Self::Node>;
/// ### Summary
/// Inserts an `Self::Edge` into the `Graph<Node, Edge>`
/// * If the graph does not contain an edge connecting `edge.left()` with `edge.right()`; inserts the `Edge<Node>`, and returns `true`,
/// * otherwise; returns `false`.
///
/// Depending on if the `Graph<Node, Edge>` is oriented or [directed](https://en.wikipedia.org/wiki/Directed_graph) or not, the behavior of the function may differ.
///
/// ### Usage
/// ```rust
/// for e in get_edges() {
/// graph.insert(e);
///}
///
/// assert_eq!(graph.nodes_len(), NODES_LEN);
/// assert_eq!(graph.edges_len(), EDGES_LEN);
/// ```
fn insert(&mut self, edge: Self::Edge) -> bool;
/// ### Summary
/// Indicates whether a `Self::Edge` exists in the `Graph<Node, Edge>`.
/// * If there is an edge connection `edge.left()` with `edge.right()`; returns `true`,
/// * otherwise; returns `false`.
///
/// Depending on if the `Graph<Node, Edge>` is oriented or [directed](https://en.wikipedia.org/wiki/Directed_graph) or not, the behavior of the function may differ.
///
/// ### Usage
/// ```rust
/// let mut graph = DirectedGraph::<IntEdge>::new();
/// build_graph(&mut graph);
///
/// for e in get_edges() {
/// assert!(graph.contains_edge(&e));
/// }
///
/// assert!(!graph.contains_edge(&IntEdge { l: 24, r: 0 }));
/// assert!(!graph.contains_edge(&IntEdge { l: 0, r: 24 }));
/// ```
fn contains_edge(&self, edge: &Self::Edge) -> bool;
/// ### Summary
/// Indicates whether the `Graph<Node, Edge>` contains a node equal to the `Self::Node` provided.
/// * If there is a node `eq`ual to `node`; returns `true`,
/// * otherwise; returns `false`.
///
/// ### Usage
/// ```rust
/// let mut graph = DirectedGraph::<IntEdge>::new();
/// build_graph(&mut graph); // build the graph from get_edges() with nodes from get_nodes()
///
/// for n in get_nodes() {
/// assert!(graph.contains_node(&n));
/// }
///
/// assert!(!graph.contains_node(&24));
/// ```
fn contains_node(&self, node: &Self::Node) -> bool;
/// ### Summary
/// Returns the edge between two nodes if `x` and `y` are adjacent.
/// Adjacency is direction-agnostic, an edge from `x` to `y` and `y` to `x` are equivalent.
///
/// If the `Graph<Node, Edge>` is direction-agnostic:
/// * If there is an edge between `x` and `y`; returns `Some` edge,
/// * otherwise; returns `None`.
///
/// If the `Graph<Node, Edge>` is [directed](https://en.wikipedia.org/wiki/Directed_graph):
/// * If there are multiple edges; returns `Some` edge in the edge in the preferred direction: `x` is `left` and `y` is `right`,
/// * if there is one edge between the nodes; returns `Some` edge that connects `x` and `y` in either direction,
/// * otherwise; returns `None`.
///
/// ### Usage
/// ```rust
/// let mut graph = DirectedGraph::<IntEdge>::new();
/// build_graph(&mut graph); // build the graph from get_edges() with nodes from get_nodes()
///
/// for e in get_edges() {
/// assert!(graph.adjacent(&e.l, &e.r).is_some());
/// assert!(graph.adjacent(&e.r, &e.l).is_some());
/// }
///
/// // 0 -> (1 -> ) 2 -> 3 => 0 !> 3 => graph.adjacent(&0,&3).is_none()
/// assert!(graph.adjacent(&0, &3).is_none());
///
/// assert!(graph.adjacent(&24, &0).is_none());
/// ```
fn adjacent(&self, x: &Self::Node, y: &Self::Node) -> Option<&Self::Edge>;
}
/// # NodesIterable
/// `NodesIterable<'a, Node, NodesIter>` is usually implemented by a `Graph<Node, Edge>` and enables extended access the nodes owned by the graph.
///
/// ## Types
/// * `Node: 'a + Copy + Eq + Hash': The type of each node of the `Graph<Node, Edge>`.
/// * `Iter: Iterator<Item = &'a Self::Node>`: The type of the iterator returned by `iter_nodes`.
///
/// ## Functions
/// * `iter_nodes(&'a self) -> Self::NodesIter`: Returns an iterator over all **distinct** nodes.
/// * `nodes_len(&self) -> usize`: The absolute number of **distinct** nodes.
/// * `nodes_to_set(&'a self) -> HashSet<Self::Node>`: Collects all nodes accessible through `iter_nodes` into a `HashSet`.
/// * `nodes_to_map<T>(&'a self, mapper: fn(&Self::Node) -> T) -> HashMap<Self::Node, T>`: Collects all nodes accessible through `iter_nodes` as keys into a `HashMap` and assigns a value to each key using the `mapper` function.
pub trait NodesIterable<'a> {
/// ### Summary
/// The type of each node of the `Graph<Node, Edge>`.
///
/// ### Remarks
/// `Nodes` are often used as keys for `HashMap`s, and as such copied quite often. A `Node` should be as slim as possible.
type Node: 'a + Copy + Eq + Hash;
/// ### Summary
/// The type of the iterator returned by `iter_nodes`.
type Iter: Iterator<Item = &'a Self::Node>;
/// ### Summary
/// Returns an iterator over all **distinct** nodes.
fn iter_nodes(&'a self) -> Self::Iter;
/// ### Summary
/// The absolute number of **distinct** nodes.
fn nodes_len(&self) -> usize;
/// ### Summary
/// Collects all nodes accessible through `iter_nodes` into a `HashSet`.
fn nodes_to_set(&'a self) -> HashSet<Self::Node> {
let mut set = HashSet::<Self::Node>::with_capacity(self.nodes_len());
for n in self.iter_nodes() {
set.insert(n.to_owned());
}
set
}
/// ### Summary
/// Collects all nodes accessible through `iter_nodes` as keys into a `HashMap` and assigns a value to each key using the `mapper` function.
fn nodes_to_map<T>(&'a self, mapper: fn(&Self::Node) -> T) -> HashMap<Self::Node, T> {
let mut map = HashMap::<Self::Node, T>::with_capacity(self.nodes_len());
for n in self.iter_nodes() {
map.insert(n.to_owned(), mapper(n));
}
map
}
}
/// # EdgesIncident
/// `EdgesIncident<'a, Node, Edge, Iter>` is usually implemented by a directed `Graph<Node, Edge>`, and enables iterating over edges incident to a node.
///
/// ## Types
/// * `Node: Copy + Eq + Hash`: The type of each node of the `Graph<Node, Edge>`.
/// * `Edge: 'a + Edge<Node = Self::Node>`: The type of each edge of the `Graph<Node, Edge>`.
/// * `Iter: Iterator<Item = &'a Self::Edge>`: The type of the iterator returned by `incident`, `incident_left`, and `incident_right`.
///
pub trait EdgesIncident<'a> {
/// ### Summary
/// The type of each node of the `Graph<Node, Edge>`.
///
/// ### Remarks
/// `Nodes` are often used as keys for `HashMap`s, and as such copied quite often. A `Node` should be as slim as possible.
type Node: Copy + Eq + Hash;
/// ### Summary
/// The type of each edge of the `Graph<Node, Edge>`.
///
/// ### Remarks
/// `self.left` and `self.right` should be as slim as possible, as the references are used for comparisons. Preferably field accessors.
type Edge: 'a + Edge<Node = Self::Node>;
/// ### Summary
/// The type of the iterator returned by `incident`, `incident_left`, and `incident_right`.
type Iter: Iterator<Item = &'a Self::Edge>;
/// ### Summary
/// Returns an iterator iterating over all nodes `incident_to` the node.
/// * If `Incidence::Left`; iterates over all nodes that are directly adjacent and accessible by the node, connected using edges with the node as origin (`left`),
/// * If `Incidence::Right`; iterates over all nodes that are directly adjacent and can access the node, connected using edges with the node as target (`right`).
/// * If the node does not exist in the `Graph<Node, Edge>` or there are no edges `adjacent` to the node; returns an empty iterator.
fn incident(&'a self, incident_to: Incidence<&Self::Node>) -> Self::Iter;
/// ### Summary
/// Calls `self.incident(Incidence::Left(incident_to))`.
///
/// See `incident`.
fn incident_left(&'a self, incident_to: &Self::Node) -> Self::Iter {
self.incident(Incidence::Left(incident_to))
}
/// ### Summary
/// Calls `self.incident(Incidence::Right(incident_to))`.
///
/// See `incident`.
fn incident_right(&'a self, incident_to: &Self::Node) -> Self::Iter {
self.incident(Incidence::Right(incident_to))
}
}
pub struct DirectedGraph<E>
where
E: Edge,
{
/// The owned edges.
edges: Vec<E>,
/// The indices of elements in `edges` where `e.left()` is equal to the key.
left: HashMap<E::Node, Vec<usize>>,
/// The indices of elements in `edges` where `e.right()` is equal to the key.
right: HashMap<E::Node, Vec<usize>>,
}
impl<E> DirectedGraph<E>
where
E: Edge,
{
/// ### Summary
/// Initializes a new `DirectedGraph<E>` without allocating.
pub fn new() -> DirectedGraph<E> {
DirectedGraph {
edges: Vec::new(),
left: HashMap::new(),
right: HashMap::new(),
}
}
/// ### Summary
/// Initializes a new `DirectedGraph<E>` allocating the data-structures for `capacity` edges.
pub fn with_capacity(capacity: usize) -> DirectedGraph<E> {
DirectedGraph {
edges: Vec::with_capacity(capacity),
left: HashMap::with_capacity(capacity / 3),
right: HashMap::with_capacity(capacity / 3),
}
}
/// ### Summary
/// > Reserves capacity for at least additional more elements to be inserted in the given Vec<T>. The collection may reserve more space to avoid frequent reallocations. After calling reserve, capacity will be greater than or equal to self.len() + additional. Does nothing if capacity is already sufficient.
/// >
/// ^ Does that for edges vector.
pub fn reserve(&mut self, additional: usize) {
self.edges.reserve(additional);
}
pub fn iter_edges(&self) -> std::slice::Iter<E> {
self.edges.iter()
}
pub fn edges_len(&self) -> usize {
self.edges.len()
}
fn get_edge(&self, left: &E::Node, right: &E::Node) -> Option<usize> {
if let Some(edges) = self.left.get(left) {
for e in edges {
if self.edges[*e].right().eq(right) {
return Some(*e);
}
}
}
None
}
fn add_edge(&mut self, left: E::Node, right: E::Node, edge: usize) {
if let Some(edges) = self.left.get_mut(&left) {
edges.push(edge);
} else {
self.left.insert(left, vec![edge]);
}
if let Some(edges) = self.right.get_mut(&right) {
edges.push(edge);
} else {
self.right.insert(right, vec![edge]);
}
}
}
impl<E> Default for DirectedGraph<E>
where
E: Edge,
{
fn default() -> Self {
Self::new()
}
}
impl<E> Graph for DirectedGraph<E>
where
E: Edge,
{
type Node = E::Node;
type Edge = E;
fn insert(&mut self, edge: Self::Edge) -> bool {
let left = edge.left();
let right = edge.right();
if self.get_edge(&left, &right).is_some() {
return false;
}
let e = self.edges.len();
self.edges.push(edge);
self.add_edge(left, right, e);
true
}
#[inline]
fn contains_edge(&self, edge: &Self::Edge) -> bool {
self.get_edge(&edge.left(), &edge.right()).is_some()
}
#[inline]
fn contains_node(&self, node: &Self::Node) -> bool {
self.left.contains_key(node) || self.right.contains_key(node)
}
#[inline]
fn adjacent(&self, left: &Self::Node, right: &Self::Node) -> Option<&Self::Edge> {
if let Some(edge) = self.get_edge(left, right) {
Some(&self.edges[edge])
} else if let Some(edge) = self.get_edge(right, left) {
Some(&self.edges[edge])
} else {
None
}
}
}
impl<'a, E> EdgesIncident<'a> for DirectedGraph<E>
where
E: 'a + Edge,
{
type Node = E::Node;
type Edge = E;
type Iter = IncidentIter<'a, E>;
fn incident(&'a self, incident_to: Incidence<&Self::Node>) -> IncidentIter<'a, E> {
IncidentIter::new(self, incident_to)
}
}
pub enum Incidence<V> {
Left(V),
Right(V),
}
impl<'a, E> NodesIterable<'a> for DirectedGraph<E>
where
E: 'a + Edge,
{
type Node = E::Node;
type Iter = std::collections::hash_map::Keys<'a, Self::Node, Vec<usize>>;
fn iter_nodes(&'a self) -> Self::Iter {
self.left.keys()
}
fn nodes_len(&self) -> usize {
self.left.len()
}
}
impl<V> Incidence<V>
where
V: PartialEq,
{
#[inline(always)]
pub fn node(&self) -> &V {
match self {
Incidence::Left(v) => v,
Incidence::Right(v) => v,
}
}
#[inline(always)]
pub fn is_adjacent<E: Edge<Node = V>>(&self, edge: &E) -> bool {
match self {
Incidence::Left(v) => edge.left().eq(v),
Incidence::Right(v) => edge.right().eq(v),
}
}
}
pub struct IncidentIter<'a, E>
where
E: 'a + Edge,
{
graph: &'a DirectedGraph<E>,
incident_edges: Option<std::slice::Iter<'a, usize>>,
}
impl<'a, E> IncidentIter<'a, E>
where
E: 'a + Edge,
{
pub fn new(
graph: &'a DirectedGraph<E>,
incident_to: Incidence<&E::Node>,
) -> IncidentIter<'a, E> {
let edges = match incident_to {
Incidence::Left(v) => graph.left.get(v),
Incidence::Right(v) => graph.right.get(v),
};
IncidentIter {
graph,
incident_edges: edges.map(|v| v.iter()),
}
}
pub fn exists(&self) -> bool {
self.incident_edges.is_some()
}
}
impl<'a, E> Iterator for IncidentIter<'a, E>
where
E: 'a + Edge,
{
type Item = &'a E;
fn next(&mut self) -> Option<Self::Item> {
if let Some(iter) = &mut self.incident_edges {
if let Some(edge_idx) = iter.next() {
return Some(&self.graph.edges[edge_idx.to_owned()]);
}
}
None
}
}
pub struct DepthFirstIter<'a, E>
where
E: 'a + Edge,
{
graph: &'a DirectedGraph<E>,
gray: Vec<E::Node>,
black: HashSet<E::Node>,
}
impl<'a, E> DepthFirstIter<'a, E>
where
E: 'a + Edge,
{
pub fn new(graph: &'a DirectedGraph<E>, root: E::Node) -> DepthFirstIter<'a, E> {
let mut gray = Vec::with_capacity(graph.left.len() / 3);
gray.push(root);
DepthFirstIter {
graph,
gray,
black: HashSet::with_capacity(graph.left.len()),
}
}
}
impl<'a, E> Iterator for DepthFirstIter<'a, E>
where
E: 'a + Edge,
{
type Item = E::Node;
fn next(&mut self) -> Option<Self::Item> {
while let Some(node) = self.gray.pop() {
if self.black.insert(node) {
self.gray.push(node);
}
let mut has_no_adj = true;
for edge in self.graph.incident(Incidence::Left(&node)) {
let incident = edge.right();
if self.black.insert(incident) {
self.gray.push(incident);
has_no_adj = false;
}
}
if has_no_adj {
// We are at the end of the trace of the dfs.
return Some(node);
}
}
None
}
}
And as far as I can tell everything even works. Yay!
I also got started on some unit tests...
#[cfg(test)]
mod tests {
use ancile::framework::graph::{DirectedGraph, Edge, Graph, NodesIterable};
use ancile::framework::util::*;
#[derive(PartialEq, Eq)]
struct IntEdge {
pub l: isize,
pub r: isize,
}
impl Edge for IntEdge {
type Node = isize;
fn left(&self) -> Self::Node {
self.l
}
fn right(&self) -> Self::Node {
self.r
}
}
/// ```
/// 1 ------> 2 -------|
/// ^ | | |
/// | | v |
/// | | 3 ---- |
/// 0 ---- ^ | |
/// ^ |----- |
/// | |
/// |-------------------
/// ```
fn get_edges() -> Vec<IntEdge> {
vec![
IntEdge { l: 0, r: 1 },
IntEdge { l: 0, r: 2 },
IntEdge { l: 1, r: 2 },
IntEdge { l: 2, r: 0 },
IntEdge { l: 2, r: 3 },
IntEdge { l: 3, r: 3 },
]
}
const EDGES_LEN: usize = 6;
fn get_nodes() -> Vec<isize> {
vec![0, 1, 2, 3]
}
const NODES_LEN: usize = 4;
fn build_graph(graph: &mut DirectedGraph<IntEdge>) {
for e in get_edges() {
graph.insert(e);
}
assert_eq!(graph.nodes_len(), NODES_LEN);
assert_eq!(graph.edges_len(), EDGES_LEN);
}
#[test]
pub fn text_create() {
let mut new_graph = DirectedGraph::<IntEdge>::new();
build_graph(&mut new_graph);
let mut capacity_graph = DirectedGraph::<IntEdge>::with_capacity(512);
build_graph(&mut capacity_graph);
}
#[test]
pub fn test_contains_node() {
let mut graph = DirectedGraph::<IntEdge>::new();
build_graph(&mut graph); // build the graph from get_edges() with nodes from get_nodes()
for e in get_edges() {
assert!(graph.contains_edge(&e));
}
assert!(!graph.contains_edge(&IntEdge { l: 24, r: 0 }));
assert!(!graph.contains_edge(&IntEdge { l: 0, r: 24 }));
for n in get_nodes() {
assert!(graph.contains_node(&n));
}
assert!(!graph.contains_node(&24));
}
#[test]
pub fn test_adjacent() {
let mut graph = DirectedGraph::<IntEdge>::new();
build_graph(&mut graph); // build the graph from get_edges() with nodes from get_nodes()
for e in get_edges() {
assert!(graph.adjacent(&e.l, &e.r).is_some());
assert!(graph.adjacent(&e.r, &e.l).is_some());
}
// 0 -> (1 -> ) 2 -> 3 => 0 !> 3 => graph.adjacent(&0,&3).is_none()
assert!(graph.adjacent(&0, &3).is_none());
assert!(graph.adjacent(&24, &0).is_none());
assert!(graph.adjacent(&0, &24).is_none());
}
#[test]
pub fn test_iter_nodes() {
let mut graph = DirectedGraph::<IntEdge>::new();
build_graph(&mut graph); // build the graph from get_edges() with nodes from get_nodes()
assert_eq!(graph.iter_nodes().count(), NODES_LEN);
let mut nodes = get_nodes();
for n in graph.iter_nodes() {
assert!(nodes.take(n).is_some());
}
assert!(nodes.is_empty())
}
#[test]
pub fn test_iter_edges() {
let mut graph = DirectedGraph::<IntEdge>::new();
build_graph(&mut graph); // build the graph from get_edges() with nodes from get_nodes()
assert_eq!(graph.iter_edges().count(), EDGES_LEN);
let mut edges = get_edges();
for e in graph.iter_edges() {
assert!(edges.take(e).is_some());
}
assert!(edges.is_empty());
}
}
... but they are far from a good test-coverage / -dataset.
Thanks again for the help. Cheers!