Algorithm: Greedy feedback arc set #386
Conversation
The sequence source graph is now always 64-bit however, negating the memory size advantages of 32-bit input graph index.
There was a problem hiding this comment.
Hi, thanks for this. Can you rebase, so that it runs the tests with the new CI?
The paper uses a vector of doubly linked lists to find node candidates, so it avoids the linear search in your implementation.
It would be nice to implement that, but if you prefer we can merge this PR as-is and optimize it afterwards.
On that vein, we could use a small benchmark to test future changes.
Rebase was conflicting so I've merged master; I hope that's okay.
Yeah, I would like to try this, good spot. I didn't read the paper thoroughly at the time. I still don't understand how the bin sort makes it "trivial" to find the next candidate node when constructing the node sequence 😅. But I'll have a play and hopefully figure it out. |
|
They store a cursor into the corresponding linked list for each node so they can delete the nodes in constant time. I think not even the experimental cursor API for std's linked lists supports doing that, you'll have to roll your own. |
Replaced the stable graph clone with a bespoke model which sorts nodes into linked list buckets by their delta degree. This improves time complexity. Removced stable_graph feature dependency.
|
The new changeset is a lot more to review than the original, sorry 😁. This is mostly due to the linked list implementation. I've added benchmarks and tested them against the original - the improvement is mostly good. It's a bit slower than before when there aren't many edges, but the time complexity is clearly better for many edges. Tournament |E| = O(|V|²)
Fan Graph |E| = O(|V|)
|
|
I've tried trimming the bucket lists (hopefully this is similar to what you tried): tobz1000@266f979 The benchmark changes are within a margin of error to me it seems - but I've observed that it occasionally trims 5 or so empty lists off at once with the test graphs. I suppose for some topologies these trims might be even larger, and it might cause a non-negligible performance improvement. Up to you if you want to merge that change as well. Thank you for reviewing this and giving some great input :) |
|
It doesn't seem to add a cost and may be useful for some graphs as you said, so lets add it to this branch and I'll merge the PR. |
* Initial implementation & single test * Add test for feedback arc set upper bound on "tournament" graph * Add constraint for directed graphs only, refactor some types, update docs * Allows 64-bit or 32-bit input graph index size The sequence source graph is now always 64-bit however, negating the memory size advantages of 32-bit input graph index. * Update doc, add example * Hide behind "stable_graph" feature * Minor PR suggestions * Add benches * "degree delta" buckets refactor Replaced the stable graph clone with a bespoke model which sorts nodes into linked list buckets by their delta degree. This improves time complexity. Removced stable_graph feature dependency. * Add back feature gate for doctest * adjust some benchmark data sizes * Use Vec::resize_with * trim bucket lists after removing bidirectional node
* Initial implementation & single test * Add test for feedback arc set upper bound on "tournament" graph * Add constraint for directed graphs only, refactor some types, update docs * Allows 64-bit or 32-bit input graph index size The sequence source graph is now always 64-bit however, negating the memory size advantages of 32-bit input graph index. * Update doc, add example * Hide behind "stable_graph" feature * Minor PR suggestions * Add benches * "degree delta" buckets refactor Replaced the stable graph clone with a bespoke model which sorts nodes into linked list buckets by their delta degree. This improves time complexity. Removced stable_graph feature dependency. * Add back feature gate for doctest * adjust some benchmark data sizes * Use Vec::resize_with * trim bucket lists after removing bidirectional node
Obtains a feedback arc set of a graph which is both decently small and has good time complexity.
This procedure involves the creation of a 64-bit-indexed graph mirroring the input graph, which may somewhat negate the memory advantages of 32-bit for huge graphs (I couldn't find a better way to support but 32-bit- and 64-bit-indexed graphs).
Credit for finding the algorithm used here goes to @steffahn in this discussion.