Library Reference

Everything you call is in two modules: PATHPACK.CPU (the solver and the semirings) and PATHPACK.GPU (the GPU solver, available once CUDA is loaded). Import what you use:

using PATHPACK
using PATHPACK.CPU: MinPlus, MaxMin, mstar, mlu
using PATHPACK.GPU: apsp_gpu       # after `using CUDA`

You want	Call
every pair, on the CPU	mstar(s, A)
some rows or columns, or many queries	mlu(s, A), then rmul!(B, F) (rows) or lmul!(F, B) (columns)
every pair, on one GPU or several	apsp_gpu(A; semiring, devices)
a few sources, on the GPU	apsp_gpu(A, sources)
new weights on the same graph, on the GPU	apsp_plan(A), then apsp_gpu(plan, A2)

Computing Stars

PATHPACK.CPU.mstar Function

mstar(s::AbstractSemiring, A; alg = AMF(), nt = Threads.nthreads())

Compute the star A* = I ⊕ A ⊕ A² ⊕ ⋯ of the matrix A over the semiring s, as a dense matrix. A[i, j] is the weight of the arc i → j; A*[i, j] is the ⊕-sum over all paths from i to j of the ⊗-products of their arcs' weights. With MinPlus that is the shortest-path distance between every pair of vertices.

D = mstar(MinPlus(), A)    # shortest paths
W = mstar(MaxMin(), A)     # widest paths

The result has n² entries; to compute only some rows or columns, factorize with mlu.

source

PATHPACK.CPU.mlu Function

mlu(s::AbstractSemiring, A; alg = AMF(), nt = Threads.nthreads())

Factorize the star of the matrix A over the semiring s, A* = U* L*, for queries. A sparse A is ordered to reduce fill (alg: any elimination algorithm of CliqueTrees.jl, or a permutation) and factorized with the multifrontal method; a dense A is factorized directly. Then lmul!(F, B) gives A* B (columns of the star), rmul!(B, F) gives B A* (rows), and Matrix(F) the whole star. nt is the number of threads.

F = mlu(MinPlus(), A)
B = fill(Inf, 1, size(A, 1)); B[1] = 0.0
rmul!(B, F)    # the distances from vertex 1

source

PATHPACK.CPU.pstar Function

pstar(s::AbstractSemiring, A::SparseMatrixCSC; alg, nt)

The partial star of a sparse matrix: the entries of A* on the sparsity pattern of the factors, as a sparse matrix in the original vertex order.

source

lmul!(F, B) overwrites B with A* B, the least solution of X = A X ⊕ B; rmul!(B, F) overwrites B with B A*. Both take a matrix of right-hand sides at once and the keyword nt, and Matrix(F) is the whole star.

Semirings

PATHPACK.CPU.MinPlus Type

MinPlus()

The tropical semiring ([-∞, ∞], min, +). With it, mstar(MinPlus(), A)[i, j] is the length of a shortest path from i to j; Inf means that j cannot be reached from i. Weights may be negative if no cycle is.

source

PATHPACK.CPU.MaxPlus Type

MaxPlus()

The semiring ([-∞, ∞], max, +). With it, mstar(MaxPlus(), A)[i, j] is the length of a longest path from i to j: on graphs without positive cycles, for example the critical paths of a schedule.

source

PATHPACK.CPU.MaxMin Type

MaxMin()

The widest-path semiring ([-∞, ∞], max, min). With capacities as weights, mstar(MaxMin(), A)[i, j] is the largest capacity of a single path from i to j.

source

PATHPACK.CPU.MinMax Type

MinMax()

The bottleneck semiring ([-∞, ∞], min, max). With it, mstar(MinMax(), A)[i, j] is the smallest possible largest arc weight on a path from i to j: the mildest worst step.

source

PATHPACK.CPU.MaxProd Type

MaxProd()

The Viterbi semiring ([0, ∞], max, ×). With probabilities in [0, 1] as weights, mstar(MaxProd(), A)[i, j] is the probability of the most reliable path from i to j.

source

PATHPACK.CPU.MinProd Type

MinProd()

The semiring ([0, ∞], min, ×). With it, mstar(MinProd(), A)[i, j] is the smallest product of arc weights along a path from i to j.

source

PATHPACK.CPU.PlusProd Type

PlusProd()

The semiring of nonnegative real numbers ([0, ∞], +, ×). With it, mstar(PlusProd(), B) is the sum over all walks, (I - B)⁻¹, for a nonnegative B whose spectral radius is below 1: diffusion, personalized PageRank, walk counts. Negative entries are outside this semiring.

source

PATHPACK.CPU.OrAnd Type

OrAnd()

The Boolean lattice (2ⁿ, ∪, ∩) on sets of bits stored in integers. With labels as weights, mstar(OrAnd(), A)[i, j] is the set of labels that some path carries from i to j; with one bit, it is reachability. Use an integer type such as Int32.

source

PATHPACK.CPU.AndOr Type

AndOr()

The Boolean lattice (2ⁿ, ∩, ∪) on sets of bits stored in integers: the dual of OrAnd.

source

Semiring Algebra

The scalar layer under the solver, for defining a semiring of your own or calling the kernels directly. A semiring is a subtype of AbstractSemiring; the solver reaches it only through these functions.

PATHPACK.CPU.AbstractSemiring Type

AbstractSemiring

The supertype of the semirings that mstar, mlu and pstar take. The solver reaches a semiring only through the scalar functions szero, sone, splus, sprod, smuladd, sstar and slte; the definitions in src/CPU/semiring/ show what a semiring provides.

source

PATHPACK.CPU.szero Function

szero(s::AbstractSemiring, T, op = Val(:N))

The zero of s as a value of type T: the identity of ⊕ and the weight of "no path" (Inf for MinPlus).

source

PATHPACK.CPU.sone Function

sone(s::AbstractSemiring, T, op = Val(:N))

The one of s as a value of type T: the identity of ⊗ and the weight of the empty path (0 for MinPlus).

source

PATHPACK.CPU.splus Function

splus(s::AbstractSemiring, a, b, op = Val(:N))

a ⊕ b: the better of two paths (min(a, b) for MinPlus).

source

PATHPACK.CPU.sprod Function

sprod(s::AbstractSemiring, a, b, tA = Val(:N), tB = Val(:N))

a ⊗ b: two paths one after the other (a + b for MinPlus).

source

PATHPACK.CPU.smuladd Function

smuladd(s::AbstractSemiring, a, b, c, tA = Val(:N), tB = Val(:N))

(a ⊗ b) ⊕ c, the update at the heart of the factorization.

source

PATHPACK.CPU.sstar Function

sstar(s::AbstractSemiring, a)

The star a* = 1 ⊕ a ⊕ a² ⊕ ⋯ of one element: for MinPlus, 0 if a ≥ 0 and -Inf for a negative cycle.

source

PATHPACK.CPU.slte Function

slte(s::AbstractSemiring, a, b)

Whether a ≤ b in the natural order of s, the order in which a ⊕ b = b. For MinPlus that is a >= b.

source

PATHPACK.CPU.sgte Function

sgte(s::AbstractSemiring, a, b)

Whether a ≥ b in the natural order of s: slte(s, b, a).

source

PATHPACK.CPU.sdot Function

sdot(s::AbstractSemiring, tA, tB, x, y)

The semiring dot product ⊕ᵢ x[i] ⊗ y[i], vectorized for machine number types.

source

PATHPACK.CPU.saxpy! Function

saxpy!(s::AbstractSemiring, tA, tB, side, a, x, y)

Overwrite y with (a ⊗ x) ⊕ y elementwise (side = Val(:L)) or (x ⊗ a) ⊕ y (side = Val(:R)), and return it.

source

PATHPACK.CPU.sger! Function

sger!(s::AbstractSemiring, tA, tB, side, x, y, M; nt = Threads.nthreads())

The rank-one update M[r, c] = (x[r] ⊗ y[c]) ⊕ M[r, c] (side = Val(:R)) or (y[c] ⊗ x[r]) ⊕ M[r, c] (side = Val(:L)), on nt threads; returns M.

source

Semirings built from others, and families:

PATHPACK.CPU.DualQuantale Type

DualQuantale{S}()

S with its order reversed: ⊕ becomes the opposite operation of S's order (max for min), and ⊗ stays. MaxPlus is DualQuantale{MinPlus} and MaxProd is DualQuantale{MinProd}.

source

PATHPACK.CPU.NegativeQuantale Type

NegativeQuantale{S}()

S restricted to the elements below its one in its order, such as [0, ∞] in ([-∞, ∞], min, +). The Lawvere quantales MinPlusLaw, MaxPlusLaw, MinProdLaw and MaxProdLaw are these.

source

PATHPACK.CPU.Lattice Type

Lattice{S}()

The lattice of S's order: ⊕ is S's ⊕ and ⊗ is the opposite operation. MinMax is Lattice{MinPlus}, ([-∞, ∞], min, max).

source

PATHPACK.CPU.MinPlusLaw Type

MinPlusLaw()

The Lawvere quantale ([0, ∞], min, +): MinPlus on non-negative weights.

source

PATHPACK.CPU.MaxPlusLaw Type

MaxPlusLaw()

The dual Lawvere quantale ([-∞, 0], max, +): MaxPlus on non-positive weights.

source

PATHPACK.CPU.MinProdLaw Type

MinProdLaw()

The multiplicative Lawvere quantale ([1, ∞], min, ×): MinProd on weights of at least 1.

source

PATHPACK.CPU.MaxProdLaw Type

MaxProdLaw()

The dual multiplicative Lawvere quantale ([0, 1], max, ×): MaxProd on probabilities.

source

PATHPACK.CPU.LawvereQuantale Type

LawvereQuantale

The union of MinPlusLaw, MaxPlusLaw, MinProdLaw and MaxProdLaw.

source

PATHPACK.CPU.TropicalSemiring Type

TropicalSemiring

The union of MinPlus, MaxPlus, MinProd and MaxProd.

source

GPUs

PATHPACK.GPU.apsp_gpu Function

apsp_gpu(A; semiring = MinPlus(), devices = [CUDA.device()], output = :device)
apsp_gpu(A, sources; semiring = MinPlus(), output = :device)

The closure A* of the square sparse matrix A over semiring, on the GPU, in the vertex labels of A. Needs CUDA.jl (using CUDA).

source

PATHPACK.GPU.apsp_gpu! Function

apsp_gpu!(H, A; semiring = MinPlus(), alg)
apsp_gpu!(H, plan, A)
apsp_gpu!(D, A; semiring = MinPlus(), alg)

The closure of A into the host matrix H, or into the device matrix D (a CuMatrix the caller allocated). Needs CUDA.jl.

source

PATHPACK.GPU.apsp_plan Function

apsp_plan(A; semiring = MinPlus())

A plan for repeated closures of matrices with the pattern of A (new weights, same graph). Needs CUDA.jl.

source

PATHPACK.GPU.sssp_gpu! Function

Single-source solves on the GPU, one source per row of the output. Needs CUDA.jl.

source

GPU Tuning and Internals

You do not need these to use the solver. They expose its configuration, device profiles and phase timings.

PATHPACK.GPU.config Function

The GPU solver's settings in this scope. Needs CUDA.jl.

source

PATHPACK.GPU.with_config Function

Run f with some settings of the GPU solver changed. Needs CUDA.jl.

source

PATHPACK.GPU.device_profile Function

The measured profile of a GPU. Needs CUDA.jl.

source

PATHPACK.GPU.with_phases Function

r, t = with_phases(f)

f() and the time of each phase of the GPU solver's calls in it (symbolic, numeric CPU / GPU part, transfer, inverse U_, solve L_, relabel, ...). Needs CUDA.jl.

source

PATHPACK.GPU.measure! Function

Measure the profile of a GPU. Needs CUDA.jl.

source

PATHPACK.GPU.extension Function

extension()

The module of the GPU backend (PATHPACKCUDAExt), or nothing before CUDA.jl is loaded.

source

PATHPACK.GPU.mlu_gpu Function

The hybrid CPU + GPU factorization of a sparse matrix. Needs CUDA.jl.

source

PATHPACK.GPU.rmul_gpu! Function

B ← B A* on the GPU, B with one right-hand side per row. Needs CUDA.jl.

source

PATHPACK.GPU.closure_gpu Function

The closure of a factor on the GPU, as a new device matrix. Needs CUDA.jl.

source

PATHPACK.GPU.closure_gpu! Function

The closure of a factor on the GPU, into a device matrix. Needs CUDA.jl.

source

PATHPACK.GPU.closure_multigpu! Function

The closure on several GPUs, one block of rows per device. Needs CUDA.jl.

source

PATHPACK.GPU.factorize! Function

The numeric factorization of a factor plan (new weights, same structure). Needs CUDA.jl.

source

PATHPACK.GPU.precompute_ops! Function

The dense operators of the large fronts of a GPU factor. Needs CUDA.jl.

source

PATHPACK.GPU.sgemx_gpu! Function

C ← C ⊕ A ⊗ B on the GPU. Needs CUDA.jl.

source

PATHPACK.GPU.sgetrf_gpu! Function

LU factorization of the closure on the GPU (dense, or hybrid sparse). Needs CUDA.jl.

source