Private API Documentation

const ALGORITHMS :: Dict{Symbol, Union{Dict{Symbol}, Vector}}

A dictionary indexing the data types of all available algorithms by submodule.

For instance, to access all metaheuristic minimization algorithms, use MatrixBandwidth.ALGORITHMS[:Minimization][:Metaheuristic]. Similarly, to access all recognition algorithms, use MatrixBandwidth.ALGORITHMS[:Recognition].

NotImplementedError{Nothing}(f, subtype, abstracttype)
NotImplementedError{Symbol}(f, arg, subtype, abstracttype)

An exception indicating that a function lacks dispatch to handle a specific argument type.

Semantically, this differs from MethodError in that it connotes a developer-side failure to implement a method rather than erroneous user input. Throughout this package, it is often used to warn when an existing function with multiple dispatch on some abstract type is called on a newly created subtype for which no method has been defined.

Fields

• f::Function: the function called.
• arg::Symbol: the name of the argument with the unsupported type, if the function has multiple arguments. If the function has only one argument, this field should be set to nothing.
• subtype::Type: the type of the argument. May be the actual concrete type or some intermediate supertype. (For instance, if the relevant input has concrete type A with hierarchy A <: B <: C and the abstracttype field is C, then both A and B are perfectly valid choices for subtype.)
• abstracttype::Type: the abstract type under which the argument is meant to fall.

Constructors

• NotImplementedError(::Function, ::Type, ::Type): constructs a new NotImplementedError instance for a single-argument function. Throws an error if the second type is not abstract or the first type is not a subtype of the second.
• NotImplementedError(::Function, ::Symbol, ::Type, ::Type): constructs a new NotImplementedError instance for a multi-argument function. Throws an error if the second type is not abstract or the first type is not a subtype of the second.

Supertype Hierarchy

NotImplementedError <: Exception

RectangularMatrixError(A)

An exception indicating that the matrix A is not square.

Matrix bandwidth is only defined for square matrices, so this exception is raised when a bandwidth minimization or recognition algorithm is called with a non-square input.

Fields

• A::AbstractMatrix{<:Number}: the input matrix.
• m::Int: the number of rows of A.
• n::Int: the number of columns of A.

Constructors

• RectangularMatrixError(A::AbstractMatrix{<:Number}): constructs a new RectangularMatrixError instance, automatically inferring m and n by calling size(A).

Supertype Hierarchy

RectangularMatrixError <: Exception

StructuralAsymmetryError(A, algorithm)

An exception indicating that the matrix A is not structurally symmetric.

An n×n matrix $A$ is structurally symmetric if $A[i, j]$ is nonzero if and only if $A[j, i]$ is nonzero for $1 ≤ i, j ≤ n$. Many (albeit not all) matrix bandwidth minimization and recognition algorithms assume structural symmetry, so this exception is raised when one of these algorithms is called with a structurally asymmetric input.

Fields

• A::AbstractMatrix{<:Number}: the input matrix.
• algorithm::AbstractAlgorithm: the algorithm that was called.
• problem::Symbol: the matrix bandwidth problem tackled by the algorithm (e.g., :minimization).

Constructors

• StructuralAsymmetryError(A::AbstractMatrix{<:Number}, algorithm::AbstractAlgorithm): constructs a new StructuralAsymmetryError instance, automatically inferring problem by calling _problem(algorithm).

Supertype Hierarchy

StructuralAsymmetryError <: Exception

Notes

As noted in the error message for StructuralAsymmetryError instances, users may want to consider symmetrization techniques from [RS06] to minimize the bandwidth of structurally asymmetric matrices. (A prominent one is to simply replace $A[i, j]$ with $1$ whenever $A[i, j] = 0$ but $A[j, i] ≠ 0$.) Of course, the reliability of minimization algorithms is diminished after such a transformation, so users should proceed with caution nonetheless.

References

• [RS06]: J. K. Reid and J. A. Scott. Reducing the Total Bandwidth of a Sparse Unsymmetric Matrix. SIAM Journal on Matrix Analysis and Applications 28, 805–21 (2006). https://doi.org/10.1137/050629938.

popfirst!(q::Queue)

Removes an element from the front of the queue q and returns it.

push!(q::Queue, x)

Inserts the value x to the end of the queue q.

connected_components(A) -> Vector{Vector{Int}}

Find the indices of all connected components of the graph whose adjacency matrix is A.

A is assumed to be symmetric, representing an undirected graph.

Arguments

• A::AbstractMatrix{Bool}: the adjacency matrix of the graph. Must be symmetric.

Returns

• ::Vector{Vector{Int}}: a vector of vectors, where each element is a vector of node indices belonging to a connected component.

Examples

julia> using Graphs

julia> g = complement(complete_multipartite_graph([3, 4, 2]))
{9, 10} undirected simple Int64 graph

julia> A = Bool.(adjacency_matrix(g))
9×9 SparseArrays.SparseMatrixCSC{Bool, Int64} with 20 stored entries:
 ⋅  1  1  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅
 1  ⋅  1  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅
 1  1  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅
 ⋅  ⋅  ⋅  ⋅  1  1  1  ⋅  ⋅
 ⋅  ⋅  ⋅  1  ⋅  1  1  ⋅  ⋅
 ⋅  ⋅  ⋅  1  1  ⋅  1  ⋅  ⋅
 ⋅  ⋅  ⋅  1  1  1  ⋅  ⋅  ⋅
 ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  1
 ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  1  ⋅

julia> MatrixBandwidth.connected_components(A)
3-element Vector{Vector{Int64}}:
 [1, 2, 3]
 [4, 5, 6, 7]
 [8, 9]

find_direct_subtype(abstracttype, subtype) -> Type

Identify the highest supertype of subtype that is also a subtype of abstracttype.

Arguments

• abstracttype::Type: an abstract type.
• subtype::Type: a subtype of abstracttype.

Returns

• ::Type: the direct subtype of abstracttype that is a supertype of subtype.

Examples

julia> abstract type Parent end

julia> abstract type Child1 <: Parent end

julia> abstract type Grandchild1 <: Child1 end

julia> struct Grandchild2 <: Child1 end

julia> abstract type Child2 <: Parent end

julia> struct Child3 <: Parent end

julia> MatrixBandwidth.find_direct_subtype(Parent, Child1)
Child1

julia> MatrixBandwidth.find_direct_subtype(Parent, Grandchild1)
Child1

julia> MatrixBandwidth.find_direct_subtype(Parent, Grandchild2)
Child1

julia> MatrixBandwidth.find_direct_subtype(Parent, Child2)
Child2

julia> MatrixBandwidth.find_direct_subtype(Parent, Child3)
Child3

floyd_warshall_shortest_paths(A) -> Matrix{Float64}

Compute a distance matrix from the adjacency matrix A using the Floyd–Warshall algorithm.

Relatively isolated pairs of nodes (those unreachable from each other) are assigned distances of Inf.

A is assumed to be symmetric with an all-false diagonal, representing a simple graph.

Arguments

• A::AbstractMatrix{Bool}: the adjacency matrix of the graph. Must be symmetric with an all-false diagonal.

Returns

• ::Matrix{Float64}: an n×n matrix D, where D[i, j] is the length of the shortest path between nodes i and j, or Inf if no such path exists.

Performance

Given an $n×n$ input matrix, the Floyd–Warshall algorithm runs in $O(n³)$ time, given that each level in the triple-nested loop iterates over $O(n)$ entries.

Examples

Floyd–Warshall finds the shortest distances between all pairs of nodes in a connected graph:

julia> using Graphs

julia> g = ladder_graph(5)
{10, 13} undirected simple Int64 graph

julia> A = Bool.(adjacency_matrix(g))
10×10 SparseArrays.SparseMatrixCSC{Bool, Int64} with 26 stored entries:
 ⋅  1  ⋅  ⋅  ⋅  1  ⋅  ⋅  ⋅  ⋅
 1  ⋅  1  ⋅  ⋅  ⋅  1  ⋅  ⋅  ⋅
 ⋅  1  ⋅  1  ⋅  ⋅  ⋅  1  ⋅  ⋅
 ⋅  ⋅  1  ⋅  1  ⋅  ⋅  ⋅  1  ⋅
 ⋅  ⋅  ⋅  1  ⋅  ⋅  ⋅  ⋅  ⋅  1
 1  ⋅  ⋅  ⋅  ⋅  ⋅  1  ⋅  ⋅  ⋅
 ⋅  1  ⋅  ⋅  ⋅  1  ⋅  1  ⋅  ⋅
 ⋅  ⋅  1  ⋅  ⋅  ⋅  1  ⋅  1  ⋅
 ⋅  ⋅  ⋅  1  ⋅  ⋅  ⋅  1  ⋅  1
 ⋅  ⋅  ⋅  ⋅  1  ⋅  ⋅  ⋅  1  ⋅

julia> Int.(MatrixBandwidth.floyd_warshall_shortest_paths(A))
10×10 Matrix{Int64}:
 0  1  2  3  4  1  2  3  4  5
 1  0  1  2  3  2  1  2  3  4
 2  1  0  1  2  3  2  1  2  3
 3  2  1  0  1  4  3  2  1  2
 4  3  2  1  0  5  4  3  2  1
 1  2  3  4  5  0  1  2  3  4
 2  1  2  3  4  1  0  1  2  3
 3  2  1  2  3  2  1  0  1  2
 4  3  2  1  2  3  2  1  0  1
 5  4  3  2  1  4  3  2  1  0

Floyd–Warshall assigns Inf to pairs of nodes in different connected components:

julia> using Graphs

julia> g = complement(wheel_graph(8))
{8, 14} undirected simple Int64 graph

julia> A = Bool.(adjacency_matrix(g))
8×8 SparseArrays.SparseMatrixCSC{Bool, Int64} with 28 stored entries:
 ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅
 ⋅  ⋅  ⋅  1  1  1  1  ⋅
 ⋅  ⋅  ⋅  ⋅  1  1  1  1
 ⋅  1  ⋅  ⋅  ⋅  1  1  1
 ⋅  1  1  ⋅  ⋅  ⋅  1  1
 ⋅  1  1  1  ⋅  ⋅  ⋅  1
 ⋅  1  1  1  1  ⋅  ⋅  ⋅
 ⋅  ⋅  1  1  1  1  ⋅  ⋅

julia> MatrixBandwidth.floyd_warshall_shortest_paths(A)
8×8 Matrix{Float64}:
  0.0  Inf   Inf   Inf   Inf   Inf   Inf   Inf
 Inf    0.0   2.0   1.0   1.0   1.0   1.0   2.0
 Inf    2.0   0.0   2.0   1.0   1.0   1.0   1.0
 Inf    1.0   2.0   0.0   2.0   1.0   1.0   1.0
 Inf    1.0   1.0   2.0   0.0   2.0   1.0   1.0
 Inf    1.0   1.0   1.0   2.0   0.0   2.0   1.0
 Inf    1.0   1.0   1.0   1.0   2.0   0.0   2.0
 Inf    2.0   1.0   1.0   1.0   1.0   2.0   0.0

is_structurally_symmetric(A) -> Bool

Check whether A[i, j] is nonzero if and only if A[j, i] is nonzero for all i and j.

Arguments

• A::AbstractMatrix{<:Number}: the matrix to check for structural symmetry.

Returns

• ::Bool: whether A is structurally symmetric.

Examples

julia> A = [4 0 9 -2; 0 0 1 0; 3 -1 5 0; 4 0 0 3]
4×4 Matrix{Int64}:
 4   0  9  -2
 0   0  1   0
 3  -1  5   0
 4   0  0   3

julia> MatrixBandwidth.is_structurally_symmetric(A)
true

julia> B = [1.12 2.36 0.00; 5.99 0.0 0.0; 0.0 3.1 -7.49]
3×3 Matrix{Float64}:
 1.12  2.36   0.0
 5.99  0.0    0.0
 0.0   3.1   -7.49

julia> MatrixBandwidth.is_structurally_symmetric(B)
false

Notes

Instead of transposing A and allocating a new matrix, it suffices to iterate over all opposing pairs of off-diagonal entries.

offdiag_nz_support(A) -> AbstractMatrix{Bool}

Convert A to a boolean matrix and set all its diagonal entries to false.

Arguments

• A::AbstractMatrix{<:Number}: the matrix to convert.

Returns

• ::AbstractMatrix{Bool}: the nonzero support of A, with all diagonal entries set to false.

Examples

julia> A = [0 2 0 7; 0 -8 0 3; -1 9 0 0; 0 0 0 5]
4×4 Matrix{Int64}:
  0   2  0  7
  0  -8  0  3
 -1   9  0  0
  0   0  0  5

julia> MatrixBandwidth.offdiag_nz_support(A)
4×4 BitMatrix:
 0  1  0  1
 0  0  0  1
 1  1  0  0
 0  0  0  0

Notes

In the context of matrix bandwidth reduction algorithms (which are only concerned with the nonzero support of the input matrix), this improves performance via cache optimizations, availability of bitwise operations, etc.

random_banded_matrix(n, k; p=0.5, rng=default_rng()) -> Matrix{Float64}

Generate a random n×n structurally symmetric k-banded matrix with band density ≈ p.

By definition of structural symmetry, the $(i, j)$-th entry of the matrix is nonzero if and only if the $(j, i)$-th entry is nonzero as well. All entries from this matrix are from the interval [0, 1]. Entries up to the kᵗʰ superdiagonal and down to the kᵗʰ subdiagonal are nonzero with probability p.

It is also guaranteed that each of these bands (besides the main diagonal) has at least one nonzero entry (even when p is very small), thus ensuring that the matrix has bandwidth precisely k before any reordering. (There may, however, still exist a symmetric permutation inducing a minimum bandwidth less than k, especially for small values of p.)

Arguments

• n::Integer: the order of the matrix to generate. Must be positive.
• k::Integer: the desired matrix bandwidth. Must satisfy 0 ≤ k < n.

Keyword Arguments

• p::Real=0.5: the band density. Must satisfy 0 < p ≤ 1. Defaults to 0.5.
• rng::AbstractRNG=Random.default_rng(): the random number generator to use. Defaults to Random.default_rng().

Returns

• ::Matrix{Float64}: a random n×n matrix with bandwidth exactly k and sparse bands with density p.

Examples

Generate a $6×6$ matrix with bandwidth $1$ and the maximum number of nonzero entries:

julia> using Random

julia> A = MatrixBandwidth.random_banded_matrix(6, 1; p=1, rng=MersenneTwister(1228))
6×6 Matrix{Float64}:
 0.310239  0.346413  0.0       0.0        0.0       0.0
 0.509981  0.917073  0.390771  0.0        0.0       0.0
 0.0       0.760045  0.808396  0.0195686  0.0       0.0
 0.0       0.0       0.222338  0.853164   0.806888  0.0
 0.0       0.0       0.0       0.421603   0.132165  0.805813
 0.0       0.0       0.0       0.0        0.305339  0.0799183

julia> bandwidth(A)
1

Generate a $7×7$ matrix with bandwidth $3$ and band density $0.3$:

julia> using Random

julia> A = MatrixBandwidth.random_banded_matrix(7, 3; p=0.3, rng=MersenneTwister(0402))
7×7 Matrix{Float64}:
 0.0       0.132699  0.0       0.0       0.0  0.0       0.0
 0.869352  0.0       0.324319  0.926496  0.0  0.0       0.0
 0.0       0.891878  0.0       0.658102  0.0  0.0       0.0
 0.0       0.88859   0.399559  0.0       0.0  0.284285  0.703377
 0.0       0.0       0.0       0.0       0.0  0.0       0.0
 0.0       0.0       0.0       0.489594  0.0  0.0       0.393573
 0.0       0.0       0.0       0.412412  0.0  0.47063   0.0

julia> bandwidth(A)
3

Generate an $8×8$ diagonal (bandwidth $0$) matrix with default band density ($0.5$):

julia> using Random

julia> A = MatrixBandwidth.random_banded_matrix(8, 0; rng=MersenneTwister(0102))
8×8 Matrix{Float64}:
 0.0  0.0        0.0       0.0       0.0  0.0      0.0  0.0
 0.0  0.0762399  0.0       0.0       0.0  0.0      0.0  0.0
 0.0  0.0        0.373113  0.0       0.0  0.0      0.0  0.0
 0.0  0.0        0.0       0.726309  0.0  0.0      0.0  0.0
 0.0  0.0        0.0       0.0       0.0  0.0      0.0  0.0
 0.0  0.0        0.0       0.0       0.0  0.41974  0.0  0.0
 0.0  0.0        0.0       0.0       0.0  0.0      0.0  0.0
 0.0  0.0        0.0       0.0       0.0  0.0      0.0  0.293132

julia> bandwidth(A)
0

Notes

Users of the MatrixBandwidth package may find this function useful when generating random test data for whatever frameworks, algorithms, etc. they are implementing.

bi_criteria_node_finder(A) -> Int

Select a pseudo-peripheral node from the graph of A based on both eccentricity and width.

This function acts as a node finder for heuristic matrix bandwidth minimization algorithms such as reverse Cuthill–McKee and Gibbs–Poole–Stockmeyer when applies to connected graphs (or their adjacency matrices). It heuristically identifies the node "farthest" from the others in the graph (i.e., a pseudo-peripheral node) as a good starting point for the search process. The heuristic is based on both eccentricity (the maximum distance from a candidate node to any other node in the graph) and width (the maximum number of nodes in any level of the breadth-first search level structure rooted at a candidate node).

It is assumed that A is the adjacency matrix of some undirected connected graph; otherwise, undefined behavior may arise.

Arguments

• A::AbstractMatrix{Bool}: a symmetric boolean matrix with an all-false diagonal, representing the adjacency matrix of some undirected connected graph.

Returns

• Int: the index of the pseudo-peripheral node selected from the graph.

Notes

This algorithm was initially presented in [HLZ24], which in turn is a refinement of the original, more widely known procedure described in [GL79]. Whereas the [GL79] version used only eccentricity as a heuristic, the [HLZ24] version uses width as a tiebreaker when multiple nodes have the same eccentricity, which tends to yield better results.

References

• [GL79]: A. George and J. W. Liu. An Implementation of a Pseudoperipheral Node Finder. ACM Transactions on Mathematical Software 5, 284–95 (1979). https://doi.org/10.1145/355841.355845.
• [HLZ24]: J. Hou, H. Liu and S. Zhu. RCM++:Reverse Cuthill-McKee ordering with Bi-Criteria Node Finder (2024), arXiv:2409.04171 [cs.DS]. https://arxiv.org/abs/2409.04171

pseudo_peripheral_node_finder(A) -> Int

Select a pseudo-peripheral node from the graph of A based on eccentricity.

This function acts as a node finder for heuristic matrix bandwidth minimization algorithms such as reverse Cuthill–McKee and Gibbs–Poole–Stockmeyer when applies to connected graphs (or their adjacency matrices). It heuristically identifies the node "farthest" from the others in the graph (i.e., a pseudo-peripheral node) as a good starting point for the search process. The heuristic is based solely on eccentricity (the maximum distance from a candidate node to any other node in the graph).

It is assumed that A is the adjacency matrix of some undirected connected graph; otherwise, undefined behavior may arise.

Arguments

• A::AbstractMatrix{Bool}: a symmetric boolean matrix with an all-false diagonal, representing the adjacency matrix of some undirected connected graph.

Returns

• Int: the index of the pseudo-peripheral node selected from the graph.

Notes

This function takes heavy inspiration from the implementation in [Net25], which in turn is based on the algorithm described in [GL79]. Whereas the [Net25] implementation accepts a graph object as input and leverages several pre-existing functions in the networkx library, we repurpose the logic to work directly on adjacency matrices, avoiding reallocation overhead and an unnecessary dependency on the Graphs.jl package.

References

• [GL79]: A. George and J. W. Liu. An Implementation of a Pseudoperipheral Node Finder. ACM Transactions on Mathematical Software 5, 284–95 (1979). https://doi.org/10.1145/355841.355845.
• [Net25]: NetworkX Developers. Source code for networkx.utils.rcm. NetworkX v3.5 documentation (2025). Accessed: 2025-06-11. https://networkx.org/documentation/stable/_modules/networkx/utils/rcm.html.

dcm_ps_optimal_depth(A) -> Int

Compute a (hopefully) near-optimal Del Corso–Manzini perimeter search depth for A.

Taking experimental results from [DM99, pp. 197–99] into account, this function tries to approximate the optimal depth parameter as a function of both matrix size and density. This depth parameter determines how large of a "perimeter" of last-placed indices is precomputed in the Del Corso–Manzini algorithm with perimeter search.

Arguments

• A::AbstractMatrix{Bool}: the (structurally symmetric and square) input matrix whose bandwidth is investigated.

Returns

• ::Int: a (hopefully) near-optimal perimeter search depth for the Del Corso–Manzini algorithm with perimeter search on A.

Notes

See Tables 4, 5, and 6 from the original paper for more details on experimental results regarding the optimal perimeter search depth [DM99, pp. 197–99].

See also DelCorsoManziniWithPS and MatrixBandwidth.Minimization.Exact.DelCorsoManziniWithPS) for our implementation of the relevant bandwidth recognition and bandwidth minimization algorithms, respectively.

References

• [DM99]: G. M. Del Corso and G. Manzini. Finding Exact Solutions to the Bandwidth Minimization Problem. Computing 62, 189–203 (1999). https://doi.org/10.1007/s006070050002.