graphalgs
graphalgs copied to clipboard
starovoid
Graph algorithms based on the Rust "petgraph" library.
This will be useful for tracking the history of changes.
The current feedback arc set implementation in petgraph is [greedy and non-minimal](https://docs.rs/petgraph/latest/petgraph/algo/feedback_arc_set/fn.greedy_feedback_arc_set.html). There are now [relatively efficient algorithms for minimal feedback arc sets](https://arnold-neumaier.at/ms/minimum_feedback_arc_set.pdf), which would be relevant for some applications....
One of the significant changes is the use of the [SPFA implementation](https://github.com/petgraph/petgraph/pull/686) from `petgraph` instead of similar old one.
1. Avoid `.unwrap()`. Where `.unwrap()` appears as a result of comparing distances, it may be necessary to impose additional restrictions on the types used. 2. Add `MetricCalculator` type with methods...
Currently, `shortest_distances` uses `f32` to represent lengths. It is worth giving the user the opportunity to select the type of result. This task should be coordinated with #7 Perhaps it...
- [ ] Add benchmarks - [ ] Rewrite `find_parents` without recursion. #### Changes below will be implemented in `0.4.0` or later, when the [`Tree`](https://github.com/petgraph/petgraph/issues/711) type is included in `petgraph`...
MIRI finds UB in the safe API of the [`nalgebra`](https://github.com/dimforge/nalgebra) crate. Need to check if there really is an UB error, or it is a MIRI bug. ```rust pub fn...