API Reference

airfoil() -> (A::SparseMatrixCSC, coords::Matrix)

Load the SuiteSparse airfoil example from the airfoil1 artifact.

build_adjacency(edges::Matrix{Int}, num_nodes::Int)

Construct the adjacency matrix of a graph from an edge list.

Arguments

• edges::Matrix: Matrix where each row represents an edge [u, v].
• num_nodes::Int: Total number of nodes in the graph.

Returns

• A symmetric sparse adjacency matrix (SparseMatrixCSC{Int, Int}).

Example

julia> edges = [1 2; 2 3; 3 1]
julia> A = build_adjacency(edges, 3)

build_adjacency(type::String)

Generate a predefined adjacency matrix and corresponding node coordinates.

Arguments

• type::String: Type of graph to generate.
  • "network": A predefined network structure.
  • "triangles": A small triangular mesh structure.

Returns

• A::SparseMatrixCSC: The sparse adjacency matrix of the graph.
• coords::Matrix: Node coordinates for visualization.

Example

julia> A, coords = build_adjacency("network")

compute_partition_balance(p::AbstractVector) -> Float64

Computes the balance metric of a given graph partitioning.

Parameters

• p::AbstractVector: A vector where p[i] represents the partition index assigned to vertex i.

Returns

• Float64: The balance metric, defined as the ratio of the largest partition size to the ideal partition size. A value close to 1.0 indicates a well-balanced partitioning, while higher values suggest imbalance.

Example

julia> p = [1, 1, 2, 2, 2, 3, 3, 3, 3]  # Example partitioning
julia> balance = compute_partition_balance(p)
julia> println(balance)  # Output close to 1 for balanced partitions

count_edge_cut(A::AbstractMatrix, p::AbstractVector)

Count the number of edges that cross partitions in the graph A.

Arguments

• A::AbstractMatrix: Adjacency matrix of the graph.
• p::AbstractVector: Partition vector where p[v] represents the partition of vertex v.

Returns

• The number of edges that connect nodes in different partitions.

Example

julia> count_edge_cut(A, p)
15

draw_graph(A::SparseMatrixCSC, coords::Matrix, p::Vector{Int}; file_name::Union{String, Nothing}=nothing)

Draw and optionally save a visualization of the partitioned graph A.

Arguments

• A: Adjacency matrix of the graph.
• coords: Node coordinates for plotting.
• p: Partition labels for each node.
• file_name (optional): If provided, saves the figure to the specified file.

Output

• Returns the generated figure.
• Saves the figure if file_name is specified.

draw_graph(A::SparseMatrixCSC, coords::Matrix; file_name::Union{String, Nothing}=nothing)

Draw and optionally save a visualization of the graph A without partitioning.

Arguments

• A: Adjacency matrix of the graph.
• coords: Node coordinates for plotting.
• file_name (optional): If provided, saves the figure to the specified file.

Output

• Returns the generated figure.
• Saves the figure if file_name is specified.

france() -> (A::SparseMatrixCSC, coords::Matrix)

Load the France graph from the france_graph artifact.

nested_dissection(A::SparseMatrixCSC, method::Function; coords=nothing, minsep=5, verbose=false)

Computes a nested dissection ordering of the sparse matrix A using a given separator method.

Arguments

• A::SparseMatrixCSC: The sparse matrix.
• method::Function: Function to compute graph separators.
• coords::Union{Matrix, Nothing}: Optional node coordinates for geometric methods (default is nothing).
• minsep::Int: Minimum component size to stop recursion (default is 10).
• verbose::Bool: Whether to display visualizations and pause for input during recursion (default is false).

Returns

• pA::Vector{Int}: The computed permutation vector.

normalized_cut(A::AbstractMatrix, p::AbstractVector{<:Integer}) -> Float64

Compute Ncut(p) = ∑j cut(pj, ¯pj) / vol(pj), where vol(pj) = ∑{v∈p_j} degree(v).

Assumes an undirected, unweighted adjacency (nonzeros -> edges).

part_adaptive_sfc(A::SparseMatrixCSC, coords::Matrix, k::Int=2)

Partition a graph using an adaptive space-filling curve traversal.

This function builds a kd-tree from node coordinates, traverses the tree following an adaptive space-filling curve, and assigns partition labels based on traversal order. It returns a partition vector that assigns each node to one of k partitions.

This algorithm is based on "A General Space-filling Curve Algorithm for Partitioning 2D Meshes" (Aparna et al., 2015, DOI: 10.1109/HPCC-CSS-ICESS.2015.192) and "Space-filling Curves for Partitioning Adaptively Refined Meshes" (Sasidharan, Aparna, and Snir).

Arguments

• A::SparseMatrixCSC: Adjacency matrix of the graph.
• coords::Matrix: An n × 2 matrix of node coordinates.
• k::Int=2: Number of partitions.

Returns

• A vector part of length n assigning each node to a partition labeled 1 to k.

Example

julia> part = part_adaptive_sfc(A, coords, 4)
[1, 1, 2, 2, 3, 4, 4, ...]

part_coordinate(A::SparseMatrixCSC, coords::Matrix)

Compute a bi-partition of the graph A using the coordinate method based on coords.

Arguments

• A::SparseMatrixCSC: Adjacency matrix of the graph.
• coords::Matrix: Node coordinates used for partitioning.

Returns

• A vector of partition labels for each node.

Example

julia> part_coordinate(A, coords)
 1
 ⋮
 2

part_geospectral(A::SparseMatrixCSC; ev::Int=2)

Performs spectral partitioning by projecting the graph onto its low-frequency Laplacian eigenvectors, followed by geometric random sphere partitioning in the resulting embedding space.

Arguments

• A::SparseMatrixCSC: The adjacency matrix of an undirected graph.
• ev::Int=2: The number of Laplacian eigenvectors to use for embedding (default is 2).

Returns

• p::Vector{Int}: A partition of the vertex set, typically as cluster labels.

Notes

• Emits a warning if the graph is large, as eigen decomposition may become computationally expensive.
• This combines spectral embedding with geometric partitioning for improved structural fidelity.

part_inertial(A::SparseMatrixCSC, coords::Matrix)

Compute a bi-partition of the graph A using the inertial method based on coords.

Arguments

• A::SparseMatrixCSC: Adjacency matrix of the graph.
• coords::Matrix: Node coordinates used for partitioning.

Returns

• A vector of partition labels for each node.

Example

julia> part_inertial(A, coords)
 1
 ⋮
 2

part_metis(A::SparseMatrixCSC, k::Int, alg::Symbol)

Partition the graph A into k parts using METIS with the specified algorithm.

Arguments

• A: Adjacency matrix of the graph.
• k: Number of partitions.
• alg: Partitioning algorithm (:KWAY or :RECURSIVE).

Output

• Returns a vector of partition labels for each node.

Examples

julia> part_metis(A, 2, :RECURSIVE)
 1
 ⋮
 2

part_randsphere(A, coords; ntrials)

Geometric _partitioning using random spheres and lines.

Arguments:

• A::SparseMatrixCSC: adjacency matrix
• coords::Matrix{Float64}: n × d node positions
• ntries::Int (optional): number of directions to try (default: 30)

Returns:

• part1, part2: vectors of node indices

part_sfc(A::SparseMatrixCSC, coords::Matrix, k::Int=2, curve::Symbol=:gilbert)

Partition the graph A into k parts using a space-filling curve on coords.

The coordinates are projected to a grid and ordered according to the selected space-filling curve (:gilbert or :morton). The resulting 1D ordering is then split into k contiguous segments.

Arguments

• A::SparseMatrixCSC: Adjacency matrix of the graph.
• coords::Matrix: Node coordinates used for projection to grid.
• k::Int: Number of partitions (default = 2).
• curve::Symbol: Curve type, one of :gilbert or :morton.

Returns

• A vector of partition labels (1 to k) for each node.

Example

julia> part_sfc(A, coords, 4, :morton)
 1
 ⋮
 4

part_spectral(A::SparseMatrixCSC; fiedler::Bool=false)

Compute a bi-partition of the graph A using the spectral method.

Arguments

• A::SparseMatrixCSC: Adjacency matrix of the graph.
• fiedler::Bool=false: If true, returns the Fiedler vector instead of partition labels.

Returns

• A vector of partition labels (1 or 2).
• If fiedler=true, returns the Fiedler vector.

Example

julia> part_spectral(A)
 1
 ⋮
 2

ratio_cut(A::AbstractMatrix, p::AbstractVector{<:Integer}) -> Float64

Compute the Ratio Cut: Rcut(p) = sumj cut(pj, ¯pj) / |pj|

• A: (0/1) adjacency (dense or sparse). Nonzeros are treated as edges.
• p: partition labels (length == number of vertices). Labels can be any integers.

Counts each inter-cluster edge once for each endpoint's cluster (as per definition).

recursive_bisection(method::Function, k::Int, A::AbstractSparseMatrix, 
                    coords::Union{Matrix, Nothing}=nothing, minpoints::Int=8)

Partition the graph A into k parts using recursive bisection with the specified partitioning method.

Arguments

• method::Function: Partitioning method to apply at each bisection step (e.g., part_spectral, part_inertial).
• k::Int: Number of partitions (must be a power of 2 or will be rounded up).
• A::AbstractSparseMatrix: Adjacency matrix of the graph.
• coords::Union{Matrix, Nothing}=nothing: Node coordinates for spatial partitioning (optional).
• minpoints::Int=8: Minimum number of nodes required for further partitioning.

Returns

• A vector of partition labels for each node.

Example

julia> recursive_bisection(part_spectral, 4, A, coords)
 1
 ⋮
 4

swiss() -> (A::SparseMatrixCSC, coords::Matrix)

Load the Swiss road graph from the swiss_graph artifact.