pnevyk / gryf

Graph data structure library aspiring to be convenient, versatile, correct and performant.
MIT License
69 stars 1 forks source link

Kahn algorithm does not recover from encountering a cycle #28

Closed pnevyk closed 1 year ago

pnevyk commented 1 year ago

If continuing the iteration even when a cycle error is encountered, Kahn algorithm keeps reporting the cycle error forever. This makes the following code an infinite loop:

let toposort = TopoSort::on(&graph).kahn().run();

let sorted = toposort
    // Ignore cycle errors.
    .filter_map(|result| result.ok())
    .collect::<Vec<_>>();

The desired behavior is described in #26, but until then the fix can just be to set a flag and return None when this flag is set.