Add support for reverse Cuthill-McKee algorithm.

[samuelsonric]

This patch adds a function symrcm implementing the reverse Cuthill-McKee algorithm. It resolves this issue. The algorithm is implemented in a package extension, so there are no additional dependencies.

As far as I know, there are three Julia packages that implement the reverse Cuthill-McKee algorithm; the implementation in CliqueTrees.jl is somewhat superior to the other two. Here are some benchmarks

using BenchmarkTools, MatrixMarket, Random, SuiteSparseMatrixCollection, SparseArrays

ssmc = ssmc_db()
name = "venturiLevel3"
matrix = mmread(joinpath(fetch_ssmc(ssmc[ssmc.name .== name, :], format="MM")[1], "$(name).mtx"))

Random.seed!(100)
p = shuffle(axes(matrix, 2))
permute!(matrix, p, p)

SymRCM.jl

julia> import SymRCM

julia> @benchmark SymRCM.symrcm(matrix)
BenchmarkTools.Trial: 6 samples with 1 evaluation per sample.
 Range (min … max):  819.400 ms …   1.050 s  ┊ GC (min … max):  8.86% … 26.92%
 Time  (median):     989.446 ms              ┊ GC (median):    23.26%
 Time  (mean ± σ):   968.267 ms ± 89.339 ms  ┊ GC (mean ± σ):  21.71% ±  7.07%

  █                          █    █                      ██  █  
  █▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁█▁▁▁▁█▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁██▁▁█ ▁
  819 ms          Histogram: frequency by time          1.05 s <

 Memory estimate: 591.03 MiB, allocs estimate: 8053667.

CuthillMcKee.jl

julia> import CuthillMcKee

julia> @benchmark CuthillMcKee.symrcm(matrix)
BenchmarkTools.Trial: 5 samples with 1 evaluation per sample.
 Range (min … max):  994.522 ms …   1.184 s  ┊ GC (min … max):  9.03% … 24.32%
 Time  (median):        1.015 s              ┊ GC (median):    11.35%
 Time  (mean ± σ):      1.055 s ± 77.422 ms  ┊ GC (mean ± σ):  14.44% ±  6.04%

  █    ██                █                                   █  
  █▁▁▁▁██▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁█▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁█ ▁
  995 ms          Histogram: frequency by time          1.18 s <

 Memory estimate: 563.88 MiB, allocs estimate: 8053698.

CliqueTrees.jl

julia> import CliqueTrees

julia> @benchmark CliqueTrees.permutation(matrix; alg=CliqueTrees.RCMMD())
BenchmarkTools.Trial: 8 samples with 1 evaluation per sample.
 Range (min … max):  649.395 ms … 759.693 ms  ┊ GC (min … max): 0.00% … 13.06%
 Time  (median):     659.804 ms               ┊ GC (median):    0.50%
 Time  (mean ± σ):   670.058 ms ±  36.559 ms  ┊ GC (mean ± σ):  2.20% ±  4.48%

  █  ▁ ▁█▁                                                    ▁  
  █▁▁█▁███▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁█ ▁
  649 ms           Histogram: frequency by time          760 ms <

 Memory estimate: 245.79 MiB, allocs estimate: 18.

[samuelsonric]

If this is of interest, and if you are happy with the API, then I will add tests and so on.

[codecov]

Codecov Report

All modified and coverable lines are covered by tests ✅

Project coverage is 89.78%. Comparing base (c4e85f4) to head (56696ba).
Report is 6 commits behind head on master.

Additional details and impacted files

@@            Coverage Diff             @@
##           master     #470      +/-   ##
==========================================
+ Coverage   89.71%   89.78%   +0.07%     
==========================================
  Files          25       27       +2     
  Lines        3685     3712      +27     
==========================================
+ Hits         3306     3333      +27     
  Misses        379      379              

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

🚀 New features to boost your workflow:

• ❄️ Test Analytics: Detect flaky tests, report on failures, and find test suite problems.

[dlfivefifty]

Maybe a more descriptive name would make sense?

[samuelsonric]

Maybe a more descriptive name would make sense?

Sure! symrcm is what MATLAB uses. Maybe cuthillmckee?

[samuelsonric]

One more thing. There are actually several variants of RCM, each using a different strategy to find a pseudo-peripheral vertex. The version that I added here (CliqueTrees.RCMMD) is the variant used in SymRCM.jl and CuthillMcKee.jl; it chooses a vertex of minimum degree. The variant used in MATLAB (CliqueTrees.RCMGL) is more expensive to run but is supposed to yield somewhat better results.

[dlfivefifty]

Oh if that’s the name in Matlab then we can leave it as it will be easier to discover

[samuelsonric]

Added tests and updated the documentation!

[samuelsonric]

Any issues here? @dlfivefifty