The Cuthill McKee graph permutation algorithm for Julia.
The algorithm is based on the description of the RCM permutation by Ciprian Zavoianu.
Installation (latest tagged version):
using Pkg
Pkg.add("CuthillMcKee")Installation (from master):
using Pkg
Pkg.add(PackageSpec(url="https://github.com/rleegates/CuthillMcKee.jl.git"))Example:
using SparseArrays, CuthillMcKee, UnicodePlots, LinearAlgebra
N = 500_000
A = sprand(N, N, 1/N)
A = A+A'+30I
b = rand(N)
@time p = symrcm(A)
ip = symrcm(A, true, true)
AP = rcmpermute(A)
@assert norm( (AP*b[p])[ip]-A*b ) < 1e-12
display(spy(A))
display(spy(AP))