Adjacency List Graph Representation

Deprecated because it's way easier to use Vec<Vec<(usize, T)>>. The performance gain isn't worth giving up usability.

Credits to kiwiyou

#[derive(Debug)]
struct Graph<T> {
    n: usize,
    first: Vec<u32>,
    edge: Vec<(u32, u32, T)>, // (to, prev, data)
}

impl<T> Graph<T> {
    fn new(n: usize, e: usize) -> Self {
        Self {
            n,
            first: vec![u32::MAX; n],
            edge: Vec::with_capacity(e),
        }
    }

    fn add_edge(&mut self, from: usize, to: usize, data: T) {
        let prev = std::mem::replace(&mut self.first[from], self.edge.len() as u32);
        self.edge.push((to as u32, prev, data));
    }

    fn neighbor(&self, of: usize) -> Neighbor<T> {
        Neighbor {
            graph: self,
            next_edge: self.first[of],
        }
    }
}

struct Neighbor<'g, T> {
    graph: &'g Graph<T>,
    next_edge: u32,
}

impl<'g, T> Iterator for Neighbor<'g, T> {
    type Item = (usize, &'g T);

    fn next(&mut self) -> Option<Self::Item> {
        let (to, next_edge, data) = self.graph.edge.get(self.next_edge as usize)?;
        self.next_edge = *next_edge;
        Some((*to as usize, data))
    }
}

Last modified on 231008.