qlever icon indicating copy to clipboard operation
qlever copied to clipboard

Improve transitive path computation with GraphBLAS

Open JoBuRo opened this issue 1 year ago • 2 comments

This PR changes the implementation of the TransitivePath class. Previously it used DFS to compute the transitive hull. The new implementation uses sparse, boolean matrices instead. The matrix object and functionalities come from the SuiteSparse:GraphBLAS library [website | github] . This library is added as new dependency. The new class GrbMatrix wraps the library for this application.

JoBuRo avatar Jan 30 '24 15:01 JoBuRo

Codecov Report

Attention: Patch coverage is 67.80000% with 161 lines in your changes are missing coverage. Please review.

Project coverage is 86.94%. Comparing base (bcc05cc) to head (714744a).

:exclamation: Current head 714744a differs from pull request most recent head f6e2429. Consider uploading reports for the commit f6e2429 to get more accurate results

Files Patch % Lines
src/engine/TransitivePath.cpp 51.02% 111 Missing and 9 partials :warning:
src/engine/GrbMatrix.cpp 79.08% 21 Missing and 20 partials :warning:
Additional details and impacted files
@@            Coverage Diff             @@
##           master    #1252      +/-   ##
==========================================
- Coverage   88.10%   86.94%   -1.16%     
==========================================
  Files         310      310              
  Lines       28436    28410      -26     
  Branches     3148     3168      +20     
==========================================
- Hits        25053    24701     -352     
- Misses       2231     2552     +321     
- Partials     1152     1157       +5     

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

codecov[bot] avatar Feb 07 '24 17:02 codecov[bot]

Quality Gate Failed Quality Gate failed

Failed conditions
9.1% Duplication on New Code (required ≤ 3%)

See analysis details on SonarCloud

sonarqubecloud[bot] avatar Mar 14 '24 16:03 sonarqubecloud[bot]

We have now merged the better implementation that uses a binary search, so we can then close this PR.

joka921 avatar Apr 18 '24 13:04 joka921