codecov-io
commented
3 years ago Codecov Report
Merging #10 (b5ab1f1) into master (b5db289) will increase coverage by
0.14%. The diff coverage is100.00%.
@@ Coverage Diff @@
## master #10 +/- ##
==========================================
+ Coverage 91.81% 91.95% +0.14%
==========================================
Files 3 3
Lines 342 348 +6
==========================================
+ Hits 314 320 +6
Misses 28 28 | Impacted Files | Coverage Δ | |
|---|---|---|
| grandiso/__init__.py | 80.48% <ø> (ø) |
|
| grandiso/test_grandiso.py | 100.00% <100.00%> (ø) |
Continue to review full report at Codecov.
Legend - Click here to learn more
Δ = absolute <relative> (impact),ø = not affected,? = missing dataPowered by Codecov. Last update b5db289...b5ab1f1. Read the comment docs.
Some of the best characters-per-amount-of-improvement ratio I've ever written :)
In the worst-case of this algorithm (before), the worst-case is encountered when downstream nodes can't be filtered based upon connectivity to the partial candidate-mapping.
For example, in the star graph on 100 nodes, it takes us O(200) iterations to realize that we can't form any triangles: First to pick random nodes, and then to draw the first edge and realize there's nowhere for us to go.
This improvement checks the minimum degree of the receiving end of the edge, and short-circuits any search that is doomed to fail due to not-enough-places-to-go. In short, given a candidate mapping for any node, degree_motif ≥ degree_host.
The contrived worst-case star example is a new test in the GrandIso test-suite. Star(30K) takes nearly 30 seconds to run in the old model. In the new model, it is near-instantaneous.