Graphs are represented in Compressed Sparse Row format. All edges on the graph are stored in a single array such that edges with the same starting vertex are connected like a linked list.

  • link stores (previous edge index, endpoint) tuples.
  • head stores indices of edge list heads (or u32::MAX if none).
fn main() {
struct Graph {
    head: Vec<u32>,
    link: Vec<(u32, u32)>,

impl Graph {
    fn new(v: usize, e: usize) -> Self {
        Self {
            head: vec![u32::MAX; v],
            link: Vec::with_capacity(e),
    fn connect(&mut self, from: usize, to: usize) {
        let prev = self.head[from];
        self.head[from] = as u32;, to as u32));
    fn neighbor(&self, u: usize) -> Neighbor {
        Neighbor(self, self.head[u])

struct Neighbor<'a>(&'a Graph, u32);

impl<'a> Iterator for Neighbor<'a> {
    // (edge index, endpoint)
    type Item = (usize, usize);
    fn next(&mut self) -> Option<Self::Item> {
        let e = self.1;
        let (next, endpoint) = * as usize)?;
        self.1 = next;
        Some((e as usize, endpoint as usize))