Graph Library

A directed weighted graph library in Rust represents vertices by compact integer handles (NodeId(usize)) rather than self-referential pointers, storing node payloads and outgoing adjacency lists inside flat Vec arenas. Integer index handles satisfy the borrow checker without Rc<RefCell<...>> cycles while supporting Breadth-First Search (BFS), Dijkstra's shortest-path algorithm, and Kahn's topological sort with cycle detection.

Adjacency-List Arena Representation

Graph<N, E>
  nodes: Vec<N>               adj: Vec<Vec<Edge<E>>>
  +---+------------+          +---+----------------------------------------+
  | 0 | "auth"     | -------> | 0 | [ Edge { to: 1, weight: 4 },           |
  +---+------------+          |   |   Edge { to: 2, weight: 2 } ]          |
  | 1 | "billing"  | -------> +---+----------------------------------------+
  +---+------------+          | 1 | [ Edge { to: 3, weight: 5 } ]          |
  | 2 | "cache"    | -------> +---+----------------------------------------+
  +---+------------+          | 2 | [ Edge { to: 1, weight: 1 },           |
  | 3 | "database" | -------> |   |   Edge { to: 3, weight: 8 } ]          |
  +---+------------+          +---+----------------------------------------+

Complete Implementation

use std::cmp::Reverse;
use std::collections::{BinaryHeap, VecDeque};

#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct NodeId(pub usize);

#[derive(Debug, Clone)]
pub struct Edge<W> {
    pub to: NodeId,
    pub weight: W,
}

pub struct DiGraph<N, W> {
    nodes: Vec<N>,
    adj: Vec<Vec<Edge<W>>>,
}

impl<N, W: Copy> DiGraph<N, W> {
    pub fn new() -> Self {
        Self {
            nodes: Vec::new(),
            adj: Vec::new(),
        }
    }

    pub fn add_node(&mut self, weight: N) -> NodeId {
        let id = NodeId(self.nodes.len());
        self.nodes.push(weight);
        self.adj.push(Vec::new());
        id
    }

    pub fn add_edge(&mut self, from: NodeId, to: NodeId, weight: W) {
        assert!(from.0 < self.nodes.len() && to.0 < self.nodes.len());
        self.adj[from.0].push(Edge { to, weight });
    }

    pub fn node_count(&self) -> usize {
        self.nodes.len()
    }

    pub fn node_weight(&self, id: NodeId) -> &N {
        &self.nodes[id.0]
    }

    pub fn neighbors(&self, id: NodeId) -> &[Edge<W>] {
        &self.adj[id.0]
    }

    pub fn bfs(&self, start: NodeId) -> Vec<NodeId> {
        let mut visited = vec![false; self.nodes.len()];
        let mut order = Vec::new();
        let mut queue = VecDeque::new();

        visited[start.0] = true;
        queue.push_back(start);

        while let Some(curr) = queue.pop_front() {
            order.push(curr);
            for edge in &self.adj[curr.0] {
                if !visited[edge.to.0] {
                    visited[edge.to.0] = true;
                    queue.push_back(edge.to);
                }
            }
        }
        order
    }

    pub fn topological_sort(&self) -> Result<Vec<NodeId>, &'static str> {
        let n = self.nodes.len();
        let mut in_degree = vec![0usize; n];
        for edges in &self.adj {
            for edge in edges {
                in_degree[edge.to.0] += 1;
            }
        }

        let mut queue: VecDeque<NodeId> = in_degree
            .iter()
            .enumerate()
            .filter_map(|(i, &deg)| (deg == 0).then_some(NodeId(i)))
            .collect();

        let mut order = Vec::with_capacity(n);
        while let Some(u) = queue.pop_front() {
            order.push(u);
            for edge in &self.adj[u.0] {
                in_degree[edge.to.0] -= 1;
                if in_degree[edge.to.0] == 0 {
                    queue.push_back(edge.to);
                }
            }
        }

        if order.len() == n {
            Ok(order)
        } else {
            Err("graph contains a directed cycle")
        }
    }
}

impl<N> DiGraph<N, u64> {
    pub fn dijkstra(&self, start: NodeId) -> (Vec<Option<u64>>, Vec<Option<NodeId>>) {
        let n = self.nodes.len();
        let mut dist: Vec<Option<u64>> = vec![None; n];
        let mut prev: Vec<Option<NodeId>> = vec![None; n];
        let mut pq = BinaryHeap::new();

        dist[start.0] = Some(0);
        pq.push(Reverse((0u64, start)));

        while let Some(Reverse((d, u))) = pq.pop() {
            if let Some(best) = dist[u.0] {
                if d > best {
                    continue;
                }
            }
            for edge in &self.adj[u.0] {
                let next_dist = d + edge.weight;
                let improve = match dist[edge.to.0] {
                    None => true,
                    Some(current) => next_dist < current,
                };
                if improve {
                    dist[edge.to.0] = Some(next_dist);
                    prev[edge.to.0] = Some(u);
                    pq.push(Reverse((next_dist, edge.to)));
                }
            }
        }

        (dist, prev)
    }

    pub fn reconstruct_path(prev: &[Option<NodeId>], target: NodeId) -> Vec<NodeId> {
        let mut path = Vec::new();
        let mut curr = Some(target);
        while let Some(id) = curr {
            path.push(id);
            curr = prev[id.0];
        }
        path.reverse();
        path
    }
}

fn main() {
    let mut g = DiGraph::new();
    let gateway = g.add_node("api-gateway");
    let auth = g.add_node("auth-service");
    let cache = g.add_node("redis-cache");
    let billing = g.add_node("billing-worker");
    let db = g.add_node("postgres-primary");

    g.add_edge(gateway, auth, 4);
    g.add_edge(gateway, cache, 2);
    g.add_edge(cache, auth, 1);
    g.add_edge(auth, billing, 5);
    g.add_edge(cache, billing, 8);
    g.add_edge(billing, db, 3);
    g.add_edge(auth, db, 10);

    let bfs_names: Vec<&str> = g
        .bfs(gateway)
        .into_iter()
        .map(|id| *g.node_weight(id))
        .collect();
    println!("BFS traversal from gateway: {:?}", bfs_names);

    let topo_names: Vec<&str> = g
        .topological_sort()
        .unwrap()
        .into_iter()
        .map(|id| *g.node_weight(id))
        .collect();
    println!("Topological dependency order: {:?}", topo_names);

    let (dist, prev) = g.dijkstra(gateway);
    let path_ids = DiGraph::<&str, u64>::reconstruct_path(&prev, db);
    let path_names: Vec<&str> = path_ids.iter().map(|&id| *g.node_weight(id)).collect();
    println!(
        "Shortest path gateway -> postgres-primary (cost = {} ms): {}",
        dist[db.0].unwrap(),
        path_names.join(" -> ")
    );
}

BFS traversal from gateway: ["api-gateway", "auth-service", "redis-cache", "billing-worker", "postgres-primary"]
Topological dependency order: ["api-gateway", "redis-cache", "auth-service", "billing-worker", "postgres-primary"]
Shortest path gateway -> postgres-primary (cost = 11 ms): api-gateway -> redis-cache -> auth-service -> billing-worker -> postgres-primary