Chapter VIII Feedback Arc Set

Eades–Lin–Smyth in Rust

A linear-time heuristic that handles real-world build graphs and achieves a tight provable approximation.

Adjacency lists with successor and predecessor sides. Rust's borrow checker forces you to think about ownership of the graph up front — which is fine, since the algorithm only reads.

struct Graph {
    succ: Vec<Vec<usize>>,
    pred: Vec<Vec<usize>>,
}
impl Graph {
    fn outdeg(&self, v: usize) -> isize { self.succ[v].len() as isize }
    fn indeg (&self, v: usize) -> isize { self.pred[v].len() as isize }
}

The algorithm builds two sequences — left and right — by repeatedly grabbing sources (no incoming) onto the right edge of the left sequence, sinks (no outgoing) onto the left edge of the right sequence, and otherwise the vertex maximizing outdeg − indeg.

fn eades(g: &Graph) -> Vec<usize> {
    let n = g.succ.len();
    let mut alive = vec![true; n];
    let (mut s1, mut s2): (Vec<usize>, Vec<usize>) = (vec![], vec![]);
    let count = |g: &Graph, alive: &Vec<bool>, pred: bool| -> Vec<isize> {
        (0..n).map(|v| if !alive[v] { -1 } else {
            (if pred { &g.pred[v] } else { &g.succ[v] })
                .iter().filter(|&&u| alive[u]).count() as isize
        }).collect()
    };
    while alive.iter().any(|&a| a) {
        let ind = count(g, &alive, true);
        let outd = count(g, &alive, false);
        // sinks first
        if let Some(s) = (0..n).find(|&v| alive[v] && outd[v] == 0) {
            s2.insert(0, s); alive[s] = false; continue;
        }
        if let Some(s) = (0..n).find(|&v| alive[v] && ind[v] == 0) {
            s1.push(s); alive[s] = false; continue;
        }
        let v = (0..n).filter(|&v| alive[v])
                      .max_by_key(|&v| outd[v] - ind[v]).unwrap();
        s1.push(v); alive[v] = false;
    }
    s1.extend(s2); s1
}

Given the order, the FAS is exactly the edges that go from a later vertex to an earlier one. That's a single pass through the edge list.

fn fas(g: &Graph, order: &[usize]) -> Vec<(usize, usize)> {
    let pos: Vec<usize> = {
        let mut p = vec![0; order.len()];
        for (i, &v) in order.iter().enumerate() { p[v] = i; }
        p
    };
    let mut back = vec![];
    for u in 0..g.succ.len() {
        for &v in &g.succ[u] {
            if pos[u] > pos[v] { back.push((u, v)); }
        }
    }
    back
}

Run it on a small graph with a single back-edge. Eades–Lin–Smyth produces an ordering with at most |E|/2 − |V|/6 back edges, which on real-world graphs is usually within a factor of 2 of optimal.

fn main() {
    let g = Graph {
        succ: vec![vec![1], vec![2], vec![0,3], vec![]],
        pred: vec![vec![2], vec![0], vec![1],   vec![2]],
    };
    let ord = eades(&g);
    println!("order = {:?}, FAS = {:?}", ord, fas(&g, &ord));
}

Grammar — Rust

Rust enforces single ownership of every value at compile time. For a graph algorithm that only reads the input, that boils down to passing &Graph everywhere — once you do, the rest is plain code.

struct T { f: A, g: B }: a record type with named fields. Tuple structs and unit structs also exist.
impl T { fn m(&self) }: method block — fn m is a method on T. &self is an immutable borrow of the receiver.
Vec<T>: a heap-allocated, growable array. The standard owned-collection type.
&: a borrow — an immutable reference. Pass-by-reference without giving up ownership.
let mut x = ...;: a mutable binding. Without `mut`, the binding is immutable — compile-time enforced.
if let Some(s) = expr: pattern-match a single shape. Run the body only if expr matches Some.
usize: a pointer-sized unsigned integer — the standard array index type.
|x: T| -> R { ... }: a closure (lambda). The pipes wrap the parameter list.
?: the try operator. On Err/None it returns early; otherwise it unwraps the Ok/Some.

An adjacency list as struct of two vectors — successors and predecessors. The borrow checker forces you to decide up front whether the algorithm needs to mutate; ours only reads, so &Graph everywhere.

struct Graph {
    succ: Vec<Vec<usize>>,
    pred: Vec<Vec<usize>>,
}
impl Graph {
    fn outdeg(&self, v: usize) -> usize { self.succ[v].len() }
    fn indeg (&self, v: usize) -> usize { self.pred[v].len() }
}

The Rust Playground — try Rust in your browser →