ChipFiring

ChipFiringGraph

A structure to represent the underlying (multi)graph of a chip-firing graph. A graph is assumed to be undirected, connected, and with no self-loops.

Fields

• adj_matrix::Matrix{Int}: The n x n multiplicity matrix, where adj_matrix[i, j] is the number of edges between vertex i and vertex j.
• num_vertices::Int: The number of vertices in the graph.
• num_edges::Int: The total number of edges in the graph.
• adj_list::Vector{Vector{Int}}: An adjacency list where adj_list[i] contains the neighbors of vertex i. This represents the underlying simple graph, meaning each neighbor appears only once, regardless of edge multiplicity.
• edge_list::Vector{Tuple{Int, Int}}: A vector of tuples, where each tuple (i, j) represents an edge. Edges are included with their full multiplicity.
• valency_list::Vector{Int}: A vector where valency_list[i] stores the degree of vertex i, accounting for edge multiplicity.

Constructors

• ChipFiringGraph(multiplicity_matrix::Matrix{Int}): Constructs a ChipFiringGraph from a square, symmetric multiplicity matrix. Throws an error if the matrix is not square, not symmetric, or if the graph is not connected.
• ChipFiringGraph(num_vertices::Int, edge_list::Vector{Tuple{Int, Int}}): Constructs a ChipFiringGraph from a list of edges and the total number of vertices.

Divisor <: AbstractVector{Int}

A struct representing a divisor (i.e., chip configuration) on a graph.

Fields

• chips::Vector{Int}: An n-element vector where chips[i] is the number of chips on vertex i.

Workspace

A mutable container for pre-allocated arrays and temporary data structures used in performance-critical algorithms.

This struct is exposed for users who need to run many computations in a tight loop and want to avoid repeated memory allocations. For one-off calculations, it is often more convenient to use the wrapper functions (e.g., q_reduced(g, d, q)) which handle workspace creation automatically.

Base.show(io::IO, g::ChipFiringGraph)

Defines the text representation of a ChipFiringGraph.

borrow!(G::ChipFiringGraph, D::Divisor, v::Int)

Borrows from a single vertex $v$.

borrow!(G::ChipFiringGraph, D::Divisor, vertices::Vector{Int})

Borrows from each vertex in the provided vector.

clear!(ws::Workspace)

Resets all fields in the Workspace to their empty and default states.

compute_genus(G::ChipFiringGraph) -> Int

Computes the genus $g$ (in the topological sense) of the graph represented by $G$, which is given by

\[g = |E| - |V| + 1\]

Note this definition is from divisor theory and differs from typical definitions of genus on a graph.

compute_gonality(G::ChipFiringGraph; min_d=1, max_d=nothing, verbose=false, r=1) -> Int

Computes the r-th (default: 1) gonality of a graph $G$.

Arguments

• G::ChipFiringGraph: The graph to analyze.

Optional Arguments

• min_d=1: The minimum degree to check.
• max_d=nothing: The maximum degree to check. Defaults to nothing.
• verbose=false: If true, prints progress updates.
• r=1: Calculates $r$-th gonality. Defaults to $1$.

Returns

• Int: The computed gonality of the graph. Returns $-1$ if not found within max_d.

Note: The result of compute_gonalitymay returnr \cdot nin the case whenmax_dis set tor \cdot n - 1`.

dhar!(G::ChipFiringGraph, D::Divisor, q::Int, ws::Workspace) -> Bool

Performs a burn starting from a source vertex $q$ to determine if the divisor $D$ is super-stable with respect to $q$.

Arguments

• G::ChipFiringGraph: The graph structure.
• D::Divisor: Input divisor.
• q::Int: The vertex (1-indexed) from which to start the burn.
• ws::Workspace: The following fields are read from ws: ws.burned, ws.legals, ws.threats

Returns

• is_superstable::Bool: true if the entire graph was burned.

Modifies

• ws.burned: Tracks burned vertices.
• ws.legals: The indices of unburned vertices that form a legal firing.
• ws.threats: Tracks threats to unburned vertices.

dhar(G::ChipFiringGraph, D::Divisor, q::Int) -> Tuple{Bool, Vector{Int}}

Performs a burn starting from a source vertex $q$ to determine if the divisor $D$ is super-stable with respect to $q$.

Arguments

• G::ChipFiringGraph: The graph structure.
• D::Divisor: The chip configuration to test.
• q::Int: The vertex (1-indexed) from which to start the burn.

Returns

• The first element is true if the divisor is super-stable, false otherwise.
• The second element is a vector of unburned vertices. This vector is empty if the divisor is super-stable.

divisor_rank(G::ChipFiringGraph, D::Divisor) -> Int

Returns the rank (in the sense of Baker and Norine) of a divisor $D$. See Divisors and Sandpiles by Corry and Perkinson. This is a convenience wrapper.

Arguments

• G::ChipFiringGraph: The graph to analyze.
• D::Divisor: The divisor whose rank is to be computed.

find_negative_vertices!(out_vec::Vector{Int}, G::ChipFiringGraph, D::Divisor, q::Int)

Finds all vertices with negative chips (excluding the sink $q$) and pushes them into the pre-allocated out_vec. This is a non-allocating operation.

get_num_edges(G::ChipFiringGraph, u::Int, v::Int) -> Int

Returns the number of edges (multiplicity) between two vertices $u$ and $v$.

has_rank_at_least_r!(G::ChipFiringGraph, r::Int, ws::Workspace) -> Bool

Checks if a divisor ws.d1 has rank at least $r$.

Arguments

• G::ChipFiringGraph: The graph structure.
• r::Int: The minimum rank to check for.
• ws::Workspace: Workspace containing the divisor in ws.d1.

has_rank_at_least_r(G::ChipFiringGraph, D::Divisor, r::Int) -> Bool

Checks if a divisor $D$ has rank at least $r$.

Arguments

• G::ChipFiringGraph: The graph to analyze.
• D::Divisor: The divisor to check.
• r::Int: The minimum rank to check for.

is_effective(D::Divisor) -> Bool

Checks if a divisor $D$ is effective, meaning all its chip counts are non-negative.

Arguments

• D::Divisor: The divisor to check.

Returns

• Bool: true if $D(v) \geq 0$ for all vertices $v$, and false otherwise.

is_equivalent(G::ChipFiringGraph, D1::Divisor, D2::Divisor) -> Bool

Tests if two divisors are equivalent under chip-firing.

Arguments

• G::ChipFiringGraph: The graph to analyze.
• D1::Divisor: The first divisor.
• D2::Divisor: The second divisor.

is_winnable!(G::ChipFiringGraph, D::Divisor, ws::Workspace) -> Bool

Checks if a divisor $D$ is linearly equivalent to an effective divisor using a version of Dhar's burning algorithm.

is_winnable(G::ChipFiringGraph, D::Divisor) -> Bool

Checks if a divisor $D$ is linearly equivalent to an effective divisor using a version of Dhar's burning algorithm.

This is a convenience wrapper that allocates a temporary workspace. For performance-critical code where this function is called repeatedly, use the version that accepts a Workspace argument.

laplacian(G::ChipFiringGraph) -> Matrix{Int}

Returns the discrete Laplacian matrix of $G$.

lend!(G::ChipFiringGraph, D::Divisor, v::Int)

Lends (fires) a single vertex $v$.

lend!(G::ChipFiringGraph, D::Divisor, vertices::Vector{Int})

Lends (fires) from each vertex in the provided vector.

neighbors(G::ChipFiringGraph, v::Int) -> Vector{Int}

Returns a vector containing the indices of the neighbors of vertex $v$.

next_composition!(v::Vector{Int}) -> Bool

Mutates a vector v into the next composition of the integer sum(v), generating them in colexicographical order.

Algorithm

1. Find the first non-zero element from the left, v[t]. This is the "pivot".
2. If no such element exists (or it's the last one), we are at the end of the sequence.
3. Move one unit from the pivot to its right neighbor: v[t+1] += 1.
4. Move the remaining value of the pivot (v[t] - 1) to the very first position v[1].
5. Set the pivot's original position v[t] to zero.

Example: [3, 0, 0] -> [2, 1, 0] -> [1, 2, 0] -> [0, 3, 0] -> [2, 0, 1] ...

Returns

• true if a next configuration was generated.
• false if v was already the last configuration (e.g., [0, 0, ..., d]).

parse_graph6(g6_string::String) -> ChipFiringGraph

Parses a graph from a string in the graph6 format and returns a ChipFiringGraph.

This function fully implements the graph6 specification for simple, undirected graphs, including the 1, 4, and 8-byte encodings for the number of vertices.

Arguments

• g6_string::String: The string representing the graph. An optional header >>graph6<< is ignored if present.

Returns

• A ChipFiringGraph object.

Throws

• ArgumentError: If the string is malformed, contains invalid characters, or ends unexpectedly.

WARNING:

The backslash `` is a valid character in the graph6 format, but needs to be escaped in Julia.

q_reduced!(G::ChipFiringGraph, D::Divisor, q::Int, ws::Workspace) -> Divisor

Finds the equivalent $q$-reduced effective divisor to $D$.

Arguments

• G::ChipFiringGraph: The graph structure.
• D::Divisor: The initial chip configuration.
• q::Int: The sink vertex.
• ws::Workspace: The workspace containing pre-allocated arrays.

Returns

• d::Divisor: The resulting divisor

Modifies

• ws.d2: Uses this space to construct the resulting divisor

q_reduced(G::ChipFiringGraph, D::Divisor, q::Int) -> Divisor

Finds the equivalent $q$-reduced effective divisor to $D$.

This is a convenience wrapper that allocates a temporary workspace. For performance-critical code where this function is called repeatedly, use the version that accepts a Workspace argument.

Arguments

• G::ChipFiringGraph: The graph structure.
• D::Divisor: The initial chip configuration.
• q::Int: The sink vertex.

Returns

• d::Divisor: The resulting divisor

subdivide(G::ChipFiringGraph, k::Int) -> ChipFiringGraph

Given a ChipFiringGraph $G$, produces another ChipFiringGraph which is an $k$-uniform subdivision of $G$.

Arguments

• G::ChipFiringGraph: The original graph
• k::Int: Number of uniform subdivisions (e.g., 1 returns original graph, 2 produces $2$-uniform subdivision)

Returns

• A $k$-uniform subdivided ChipFiringGraph