search

higra / Higra

Hierarchical Graph Analysis
Other
97 stars 20 forks source link

Lca fast based on RMQ with block decomposition #237

Closed PerretB closed 3 years ago

PerretB commented 3 years ago

Refactor fast LCA computation based on range minimum query and add a new algorithm based on block decomposition with an expected speedup comprised between 1.2 and 1.8 (tested on graphs with 100,000 to 10,000,000 edges)

Thanks to @lnajman for the POC and initial benchmark

codecov[bot] commented 3 years ago

Codecov Report

Merging #237 (e1f02d7) into master (e26c197) will increase coverage by 0.02%. The diff coverage is 100.00%.

@@            Coverage Diff             @@
##           master     #237      +/-   ##
==========================================
+ Coverage   98.81%   98.83%   +0.02%     
==========================================
  Files          44       45       +1     
  Lines        4634     4739     +105     
==========================================
+ Hits         4579     4684     +105     
  Misses         55       55