ChipFiring

ChipFiringGraph

A structure to represent the underlying graph of a chip-firing graph.

This struct provides multiple representations of the graph's structure to suit different computational needs. It is designed for undirected, connected graphs, and the input multiplicity matrix is expected to be symmetric.

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, n.
• 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.
• degree_list::Vector{Int}: A vector where degree_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 chip configuration (or "divisor") 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.

getindex(d::Divisor, i::Int)

Returns the number of chips on vertex i. Allows d[i] syntax.

setindex!(d::Divisor, val, i::Int)

Sets the number of chips on vertex i. Allows d[i] = val syntax.

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

Provides a concise, single-line string representation of a ChipFiringGraph. To obtain a string output, the string() function can do so.

size(d::Divisor)

Returns the size of the divisor (the number of vertices).

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 default initial states.

compute_genus(g::ChipFiringGraph) -> Int

Returns the genus (in the topological sense) of the graph represented by g. Note that this is not the typical definition of graph genus.

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 d to check.
• max_d=nothing: The maximum degree d 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.

The result of computegonality may return r * n in the case when maxd is set to r * n - 1.

dhar!(g::ChipFiringGraph, divisor::Divisor, source::Int, ws::Workspace) -> Bool

Performs a recursive burn starting from a source vertex to determine if a divisor is super-stable with respect to that source.

Following the user's definition, a divisor is super-stable if the entire graph burns. A vertex v "burns" if its number of chips is less than the number of edges connecting it to already-burnt vertices.

Arguments

• g::ChipFiringGraph: The graph structure.
• divisor::Divisor: Input divisor.
• source::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::Vector{Bool}: Tracks burned vertices.
• ws.legals::Vector{Int}: The indices of unburned vertices that form a legal firing.

dhar(g::ChipFiringGraph, divisor::Divisor, source::Int) -> Tuple{Bool, Vector{Int}}

Performs a burn starting from a source vertex to determine if a divisor is super-stable.

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.
• divisor::Divisor: The chip configuration to test.
• source::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

Given a ChipFiringGraph g and Divisor d, returns the rank (in the sense of Baker and Norine) of d on g. See Divisors and Sandpiles by Corry and Perkinson.

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, d::Divisor, r::Int) -> Bool

Given a ChipFiringGraph g and Divisor d, returns a boolean determining whether or not d has rank at least r.

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

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

is_equivalent(g::ChipFiringGraph, d1::Divisor, d2::Divisor) -> Bool

Tests if two divisors are equivalent under chip-firing.

is_winnable(g::ChipFiringGraph, divisor::Divisor, ws::Workspace) -> Bool

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

is_winnable(g::ChipFiringGraph, divisor::Divisor) -> Bool

Checks if a chip configuration 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.

q_reduced(g::ChipFiringGraph, divisor::Divisor; q::Int, ws::Workspace) -> Divisor

Finds the equivalent, q-reduced effective divisor to the one given.

Arguments

• g: The graph structure.
• divisor: The initial chip configuration.
• q: The sink vertex.
• ws: The workspace containing pre-allocated arrays.

Returns

• d::Divisor: The resulting divisor

q_reduced(g::ChipFiringGraph, divisor::Divisor; q::Int, ws::Workspace) -> Divisor

Finds the equivalent, q-reduced effective divisor to the one given, based on the algorithm from the user-provided Python code.

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: The graph structure.
• divisor: The initial chip configuration.
• q: The sink vertex.
• ws: The workspace containing pre-allocated arrays.

Returns

• d::Divisor: The resulting divisor

subdivide(g::ChipFiringGraph, subdivisions::Int) -> ChipFiringGraph

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

Arguments

• g::ChipFiringGraph the original graph
• subdivisions::Int number of uniform subdivisions (1 returns original graph, 2 produces 2-uniform subdivision, etc.)

Returns

• A k-uniform subdivided ChipFiringGraph