I was finding loom.alg/degeneracy-ordering was running a bit slowly on a dense graph, so have had a go at speeding it up. This version calculates the updated degrees and updates the node-degree map in a single pass. I also removed an unused loop parameter and added a comment since the code is a bit more concise now.
On my weeny laptop the version in this PR completes in 50 milliseconds whereas the original version takes at least 15 minutes (I gave up waiting) on OpenJDK 8. lein test-all still passes.
Edit: It turns out my graph had a node with an edge to itself, which was causing an infinite loop in the original implementation. After removing this edge the original version completes in 80 ms, so only a minor improvement in normal cases. Both versions return the same result.
I was finding
loom.alg/degeneracy-orderingwas running a bit slowly on a dense graph, so have had a go at speeding it up. This version calculates the updated degrees and updates the node-degree map in a single pass. I also removed an unused loop parameter and added a comment since the code is a bit more concise now.This is the graph I was struggling with: https://gist.github.com/cbowdon/7711151498464be7a25e965497edb1c2
On my weeny laptop the version in this PR completes in 50 milliseconds whereas the original version takes at least 15 minutes (I gave up waiting) on OpenJDK 8.
lein test-allstill passes.Edit: It turns out my graph had a node with an edge to itself, which was causing an infinite loop in the original implementation. After removing this edge the original version completes in 80 ms, so only a minor improvement in normal cases. Both versions return the same result.