Closed pnevyk closed 1 year ago
It would be even better if the error contained the full cycle (vertices/edges that make the cycle). However, this requirement should not penalize the happy path (no cycle) in efficiency. A good compromise would be to call a separate routine that collects the cycle if one is detected. Nevertheless, this still probably should be a setting, because the user might not care and in that case a performance degradation even in error case is not acceptable.
Another alternative is to have a public routine for finding the full cycle which can be called by the user in the case it is desired. The input of the algorithm could be directly the error from toposort algorithm. Something like this:
pub struct Cycle<G: GraphBase>(pub G::EdgeIndex);
// Toposort error
pub enum Error<G: GraphBase> {
Cycle(Cycle<G>),
}
// Cycle collection algorithm
pub fn run(self, cycle: Cycle<G>) -> ...
The reason for having a dedicated Cycle
struct for representing the cycle error is that a cycle could be detected by various algorithms (not just toposort).
The information about the edge and vertices in the cycle is a very useful information in applications as well as during debugging. To have the API as simple as possible, it is sufficient to just include the edge index, from which the rest can be retrieved from the graph.