Another lifetime related question about iterators

Graph

I am learning rust, and as such there needs to be a first project to get to know the lang. For me, I decided to write a graph implementation, since its pretty simple.

See the code below:

use std::{
    collections::HashMap,
    hash::Hash,
    marker::PhantomData,
    ops::Index,
};

use flagset::flags;

pub(crate) trait Arr<Idx>: Index<Idx> {
    fn position(&self, element: &Self::Output) -> Option<Idx>;
}

impl<T> Arr<usize> for Vec<T>
where
    T: PartialEq,
{
    fn position(&self, element: &T) -> Option<usize> {
        for i in 0..self.len() {
            if element.eq(&self[i]) {
                return Some(i);
            }
        }
        None
    }
}

flags!(
    pub enum Color: u8 {
        /// Not visited
        White,
        /// Visited not finished
        Gray,
        /// Visited and finished
        Black,
    }
);

pub trait Colored {
    fn color(&self) -> Color;
    fn color_set(&mut self, color: Color);
}

pub trait Edge<'a>: PartialEq + Clone + Copy {
    type Idx: PartialEq;
    fn from(&self) -> &'a Self::Idx;
    fn to(&self) -> &'a Self::Idx;
}

pub trait Graph<'a, N, E>
where
    N: 'a + Eq + Hash,
    E: 'a + Edge<'a, Idx = N>,
{
    fn is_empty(&self) -> bool;

    fn insert(&mut self, e: E) -> bool;

    fn remove(&mut self, e: E) -> bool;

    fn contains(&self, e: E) -> bool;

    fn iter_adj(
        &self,
        edges: Switch<&'a N>,
    ) -> Option<AdjNodeIter<'a, N, E, std::slice::Iter<'a, E>>>;
}

pub struct AssocGraph<'a, N, E>
where
    N: 'a + Eq + Hash,
    E: 'a + Edge<'a, Idx = N>,
{
    from_edge: HashMap<&'a N, &'a Vec<E>>,
    to_edge: HashMap<&'a N, &'a Vec<E>>,
}

impl<'a, N, E> AssocGraph<'a, N, E>
where
    N: 'a + Eq + Hash,
    E: 'a + Edge<'a, Idx = N>,
{
    pub fn len(&self) -> usize {
        self.from_edge.len()
    }

    fn insert_from(&mut self, e: E) -> bool {
        let n = e.from();
        if let Some(edges) = self.from_edge.get_mut(n) {
            if !edges.contains(&e) {
                edges.push(e);
                true
            } else {
                false
            }
        } else {
            self.from_edge.insert(n, &vec![e]).is_some()
        }
    }

    fn insert_to(&mut self, e: E) -> bool {
        let n = e.to();
        if let Some(edges) = self.to_edge.get_mut(n) {
            if !edges.contains(&e) {
                edges.push(e);
                true
            } else {
                false
            }
        } else {
            self.to_edge.insert(n, &vec![e]).is_some()
        }
    }

    fn remove_from(&mut self, e: E) -> bool {
        let n = e.from();
        if let Some(edges) = self.from_edge.get_mut(n) {
            if let Some(pos) = edges.position(&e) {
                edges.swap_remove(pos);
                true
            } else {
                false
            }
        } else {
            false
        }
    }

    fn remove_to(&mut self, e: E) -> bool {
        let n = e.to();
        if let Some(edges) = self.to_edge.get_mut(n) {
            if let Some(pos) = edges.position(&e) {
                edges.swap_remove(pos);
                true
            } else {
                false
            }
        } else {
            false
        }
    }
}

impl<'a, N, E> Graph<'a, N, E> for AssocGraph<'a, N, E>
where
    N: 'a + Eq + Hash,
    E: 'a + Edge<'a, Idx = N>,
{
    #[inline(always)]
    fn is_empty(&self) -> bool {
        self.len() == 0
    }

    fn insert(&mut self, e: E) -> bool {
        let from = self.insert_from(e);
        let to = self.insert_to(e);
        assert_eq!(from, to, "Corrupted state, edge in matching node not found.");
        from
    }

    fn remove(&mut self, e: E) -> bool {
        let from = self.remove_from(e);
        let to = self.remove_to(e);
        assert_eq!(from, to, "Corrupted state, edge in matching node not found.");
        from
    }

    fn contains(&self, e: E) -> bool {
        let from = if let Some(edges) = self.from_edge.get(e.from()) {
            edges.contains(&e)
        } else {
            false
        };
        let to = if let Some(edges) = self.from_edge.get(e.from()) {
            edges.contains(&e)
        } else {
            false
        };
        assert_eq!(from, to, "Corrupted state, edge in matching node not found.");
        from
    }

    fn iter_adj(
        &self,
        edges: Switch<&'a N>,
    ) -> Option<AdjNodeIter<'a, N, E, std::slice::Iter<'a, E>>> {
        match edges {
            Switch::From(n) => {
                if let Some(e) = self.from_edge.get(n) {
                    Some(AdjNodeIter::new(Switch::From(n), e.iter()))
                } else {
                    None
                }
            }
            Switch::To(n) => {
                if let Some(e) = self.to_edge.get(n) {
                    Some(AdjNodeIter::new(Switch::To(n), e.iter()))
                } else {
                    None
                }
            }
        }
    }
}

#[derive(PartialEq, Eq, Debug)]
pub enum Switch<T> {
    From(T),
    To(T),
}

impl<T> Switch<T> {
    pub fn is_from(&self) -> bool {
        match self {
            Switch::From(_) => true,
            Switch::To(_) => false,
        }
    }

    pub fn is_to(&self) -> bool {
        !self.is_from()
    }

    pub fn value(&self) -> &T {
        match self {
            Switch::From(n) => n,
            Switch::To(n) => n,
        }
    }

    pub fn map<U>(&self, map: &fn(&T) -> U) -> Switch<U> {
        match self {
            Switch::From(n) => Switch::From(map(n)),
            Switch::To(n) => Switch::To(map(n)),
        }
    }
}

pub struct AdjNodeIter<'a, N, E, I>
where
    N: 'a + Eq + Hash,
    E: 'a + Edge<'a, Idx = N>,
    I: 'a + Iterator<Item = &'a E>,
{
    // The node whose adjacent nodes to iterate
    node: Switch<&'a N>,
    // The nodes connecting to the node.
    iter: I,
}

impl<'a, N, E, I> AdjNodeIter<'a, N, E, I>
where
    N: 'a + Eq + Hash,
    E: 'a + Edge<'a, Idx = N>,
    I: 'a + Iterator<Item = &'a E>,
{
    pub fn new(node: Switch<&'a N>, iter: I) -> Self { Self { node, iter } }

    /// Nodes accessible by one step from the node.
    fn next_from(&mut self) -> Option<&'a N> {
        let node = self.node.value();
        while let Some(e) = self.iter.next() {
            if node.eq(&e.from()) {
                return Some(e.to());
            }
        }
        None
    }

    /// Nodes that can access the node with one step.
    fn next_to(&mut self) -> Option<&'a N> {
        let node = self.node.value();
        while let Some(e) = self.iter.next() {
            if node.eq(&e.to()) {
                return Some(e.from());
            }
        }
        None
    }
}

impl<'a, N, E, I> Iterator for AdjNodeIter<'a, N, E, I>
where
    N: 'a + Eq + Hash,
    E: 'a + Edge<'a, Idx = N>,
    I: 'a + Iterator<Item = &'a E>,
{
    type Item = &'a N;

    #[inline(always)]
    fn next(&mut self) -> Option<Self::Item> {
        match self.node {
            Switch::From(_) => self.next_from(),
            Switch::To(_) => self.next_to(),
        }
    }
}

pub struct DepthFirstIter<'a, G, N, E>
where
    N: 'a + Colored + Eq + Hash,
    E: 'a + Edge<'a, Idx = N>,
    G: 'a + Graph<'a, N, E>,
{
    dummy: PhantomData<E>,
    node: &'a mut N,
    graph: &'a mut G,
}

impl<'a, G, N, E> DepthFirstIter<'a, G, N, E>
where
    N: 'a + Colored + Eq + Hash,
    E: 'a + Edge<'a, Idx = N>,
    G: 'a + Graph<'a, N, E>,
{
    pub fn new(root: &'a mut N, graph: &'a mut G) -> Self {
        Self { dummy: PhantomData, node: root, graph }
    }
}

impl<'a, G, N, E> Iterator for DepthFirstIter<'a, G, N, E>
where
    N: 'a + Colored + Eq + Hash,
    E: 'a + Edge<'a, Idx = N>,
    G: 'a + Graph<'a, N, E>,
{
    type Item = &'a N;

    fn next(& mut self) -> std::option::Option<Self::Item> {
        // We never stop on a colored node unless there are no uncolored nodes left -> we are done.
        if self.node.color() != Color::White {
            return None
        }
        let iter = match self.graph.iter_adj(Switch::From(self.node)) {
            Some(iter) => iter,
            None => return None,
        };

        self.node.color_set(Color::Gray);
        
        while let Some(node) = iter.next() {
            // DFS
        }
        todo!()
    }
}

Cannot infer an appropriate lifetime due to conflicting requirements

First, the lifetime cannot outlive the anonymous lifetime defined on the method body at 312:13...
...so that reference does not outlive borrowed content
but, the lifetime must be valid for the lifetime 'a as defined on the impl at 304:6...
...so that the expression is assignable

This absolutely makes sense, so I modified Graph.iter_adj so that the lifetime of self has to be 'a aswell:

fn iter_adj(
        &'a self,
        edges: Switch<&'a N>,
    ) -> Option<AdjNodeIter<'a, N, E, std::slice::Iter<'a, E>>>;

But sadly this didn't d the trick either, because now the error is as follows:

expected &'a G
found &G
first, the lifetime cannot outlive the anonymous lifetime defined on the method body at 312:13...
...so that reference does not outlive borrowed content
but, the lifetime must be valid for the lifetime 'a as defined on the impl at 304:6...
...so that the types are compatible

But the lifetime 'a of DepthFirstiter is the same as 'a for Graph, so rustc is telling me that a reference with the lifetime 'a is not a reference with the lifetime 'a all thought 'a is equal to 'a? I am totally stupefied by that one. Is my assumption that the implicit lifetime of DepthFirstiter must be contained in the lifetime 'a because we borrow references of lifetime 'a wrong?

Can anyone please explain to me exactly where I dug my grave here, and how I can possibly fix this mess? Thanks in advance, cheers!

I think your code contains way too many lifetimes. It isn’t clear at all what data-structure is going to own all that borrowed data.

It’s best to think of references, i.e. &T, in Rust only as transient/short-lived references, so many of your traits and structs are IMO problematic to begin with. Something that you might notice if you’d ever actually try to implement them. (In particular, I see nothing implementing Edge.)

Also the methods of AssocGraph don’t work at all. You’re trying to modify a &Vec<E>, i.e. a vector behind an immutable reference. (The error message only appears once you comment out that Iterator implementation.)


Consider avoiding many &s here; in particular traits with lifetime parameters are probably not what you want to work with. On the structs, too, lifetimes should be avoided, except perhaps for the iterators (about complications with iterators, see below).

Some concrete ideas

  • use N with a N: Copy bound instead of &'a N. Then you can use types such as u32 for N when implementing the trait Edge (which, as noted, you should do with some example/test struct for edges, in order to demonstrate that that’s even possible in a reasonable manner).
  • Consequently, use from_edge/to_edge: HashMap<N, Vec<E>>, where the HashMap owns both the key (as noted above, using N instead of &'a N) and the value (as noted above, modifying the Vec would be impossible behind an immutable reference, and it’s not supposed to be a short-lived borrowed either, anyway). You could also require Hash for the edge type E and use a HashSet<E> instead of Vec<E> for efficiency, since you seem to be using the vectors as sets anyways.
  • I haven’t addressed the iterators here yet, feel free to post here once you’ve started the refactoring and try to make iter_adj work properly. Note that returning iterators in traits is a nontrivial task in Rust. Since you want the iterator to be constructed from &self (and it does make sense to borrow the graph here), you’ll have to work with lifetimes here, so please feel free to come back and show what your code looks like when you’re having trouble getting this right
4 Likes

I’m only now noticing that your nodes N are apparently supposed to contain some mutable color property. If that’s really desired, then the N: Copy route will – of course – not work so easily. You’d have to be creating a shared type with mutable inner state, not something trivial in Rust to begin with, though if it’s really necessary, it can be done. But trying to figure out how to do that is maybe not the most rewarding experience for a beginner. Thus in this case, you might want to prefer keeping the color outside of the node. One particular concern with the current design:

  • N is used as a key in a HashMap, so modifying the nodes in-place would modify the hash-value of the node, too (which then break the entire hash-map). At least if you don’t pay attention that this won’t happen: You’d need to write custom Eq and Hash implementations that ignore the color.

I would suggest you

  • Don’t include color inside of the node. Instead, either:
    • put color information in the Graph as another map HashMap<N, Color> or so (I’m assuming the N: Copy approach again, now). Then the depth-first search iterator will have to &mut self modify the graph (which I guess is already the intention of how things are currently set up). Or:
    • put color information only in the depth-first-search iterator (e.g. as a HashMap<N, Color> there). This means that you’ll need to create a new hash-map for each search, but then multiple DFS traversals could theoretically happen in parallel and you could create a DFS iterator with a &self reference of the Graph.

Another point: you seem to be just using a simple Color enum, yet you’re importing a crate to support flag-sets. As long as you don’t actually use any FlagSets, you don’t need the flagset crate at all. (I assume a node in a graph is never supposed to have multiple colors or no color.) You can remove the flags! macro-call around the enum.

1 Like

Just a side note that implementing a traditionally pointer-based project as an introduction to Rust often backfires, due to Rust's ownership/borrowing/lifetime semantics. Doing this with references and traits with lifetimes, et cetera, will be a trial by fire for a beginner.

It may be advisable to start with an index-based graph approach (or different project generally) until you get your feet wet.

3 Likes

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!

1 Like

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.