pnevyk / gryf

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

Toposort algorithms should support skipping cycles #26

Open pnevyk opened 1 year ago

pnevyk commented 1 year ago

The algorithms for topological sort implement Iterator<Item = Result<VertexIndex, Error>>, that is, they lazily produce a sequence of vertices in topological order or report a (cycle) error when encountered.

It should be possible to just skip cycle errors and continue and get the rest of the vertices. The result sequence should be a valid topological order as if the encountered cycles were not in the original graph. In code, this should work and give expected output:

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

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

There may perhaps be an option to specify if recovering from cycles while still producing a valid topological order is required or not (as that may influence some implementation details, where false could be more efficient), e.g.

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

It's not obvious to me what would be the default value for this option. Anyway, for the false case, the behavior for all algorithms consistently should be to always return None after the first cycle error is reported.