commit ee87fa29507b25030d5f7998a17b94e83d67af71
author Luca Mondada <72734770+lmondada@users.noreply.github.com> Sun Dec 08 19:37:02 2024 +0000
committer GitHub <noreply@github.com> Sun Dec 08 19:37:02 2024 +0000
tree 9624d4e49aa2df49a6d310350dc39d36ff79f08c
parent 67b14158e1f3ebb24e629355386c61e17836079b

Dynamic Toposort Support (#675)

Hi there,

I would like to add support for directed acyclic graphs (DAGs) in
petgraph. I propose adding a wrapper type `Acyclic<G>` that behaves like
the underlying graph `G`, but checks for acyclicity whenever an edge
addition is attempted. This functionality is provided through an
implementation of the `Build` trait, as well as the `try_add_edge`
method.

The idea is similar to the standalone crate
[daggy](https://github.com/mitchmindtree/daggy) except that i) this PR
implements a more efficient algorithm for this purpose and ii) I am
unsure whether daggy is still maintained.

## Algorithm
I looked at the literature to find the recommended way for doing dynamic
acyclicity checks (i.e. not run toposort everytime an edge is added). I
have settled (for now) on the PK algorithm from [1]. This seems to
strike a nice balance between simplicity and performance.

The idea is fairly straightforward: keep a Vec of toposorted nodes of
the graph. When an edge is added that does not respect the current
ordering, find all nodes in the order between the offending edge
endpoints and reorder them appropriately.

[1] "A Dynamic Topological Sort Algorithm for Directed Acyclic Graphs"
by D. Pierce and P. Kelly, JEA, 2004.

## Status of this PR
This is still work in progress, and you might be able to help me here
(especially points 1-2).
- [x] I have attempted to implement the `Into{NodeIdentifiers, Edges,
etc}` for all reference types, giving me a bound of the type
```rust
impl<'a, G: GraphBase> IntoNodeReferences for &'a Acyclic<G>
where
    &'a G: IntoNodeReferences { ... }
```
However, this creates an infinite recursion in the compiler, with the
error:
```
error[E0275]: overflow evaluating the requirement `&visit::filter::NodeFiltered<_, _>: visit::IntoNodeIdentifiers`
```
I wonder if you have had this issue before when implementing other
types. Do you have any suggestions on how I should solve this? Unlike
`Reversed` and `NodeFiltered` (and others), the generic type `<G>` must
be the graph itself and not a reference, as it must be mutable.

- [x] Benchmarking shows that the implemention is currently slow,
dominated by memory allocations for the DFS traversals. Given that only
a small region of the graph is expected to be traversed at each run, it
is wasteful to reallocate a map the size of the graph at each call. The
current code structure makes this a bit hard to change. One solution I
can see is adding a `WithVisitMap(G)` wrapper type that can be used to
specify a custom `VisitMap` type for `G`.
- [x]  Add quickcheck tests.