# 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!