# chipfiring: A Python Package for Efficient Mathematical Analysis of Chip-Firing Games on Multigraphs

Dhyey Dharmendrakumar Mavani, Tairan Ji, Nathan Pflueger

► To cite this version:

Dhyey Dharmendrakumar Mavani, Tairan Ji, Nathan Pflueger. chipfiring: A Python Package for Efficient Mathematical Analysis of Chip-Firing Games on Multigraphs. 2026. hal-05488164

HAL Id: hal-05488164

https://hal.science/hal-05488164v1

Preprint submitted on 2 Feb 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
chipfiring: A PYTHON PACKAGE FOR EFFICIENT MATHEMATICAL ANALYSIS OF CHIP-FIRING GAMES ON MULTIGRAPHS

**Dhyey Dharmendrakumar Mavani**
Departments of Mathematics, Statistics and Computer Science
Amherst College
Amherst, MA, 01002
ddmavani2003@gmail.com

**Tairan (Ryan) Ji**
Department of Computer Science
Amherst College
Amherst, MA 01002
tji26@amherst.edu

**Nathan Pflueger**
Department of Mathematics
Amherst College
Amherst, MA 01002
npflueger@amherst.edu

August 5, 2025

**ABSTRACT**

This paper presents *chipfiring*, a comprehensive Python package for the mathematical analysis of chip-firing games on finite graphs. The package provides a robust toolkit for defining graphs and chip configurations (divisors), performing chip-firing operations, and analyzing fundamental properties such as winnability, linear equivalence, and divisor rank. We detail the core components of the library, including its object-oriented graph and divisor implementations, integrated Laplacian matrix computations, and an efficient implementation of Dhar's algorithm for determining the solvability of the dollar game. The *chipfiring* package is designed for researchers and students in graph theory, combinatorics, and algebraic geometry, providing essential algorithms and data structures for exploring these rich mathematical models. We describe the library's architecture, illustrate its usage with comprehensive examples, and highlight its specialized contributions compared to general-purpose graph libraries.

**Keywords** Chip-firing · Graph Theory · Divisors on Graphs · Dhar's Algorithm · Python · Mathematical Software

# 1 Introduction

The chip-firing game, also known as the dollar game or sandpile model, is a discrete dynamical system on a graph that has found diverse applications across mathematics and physics, from modeling self-organized criticality [1] to providing insights into the structure of algebraic curves [2]. In its most common formulation, vertices on a graph are endowed with a number of chips (which can be negative, representing debt), and a vertex can "fire" by sending a chip to each of its neighbors. A central problem is to determine if a given configuration of chips, or *divisor*, can reach a state with no vertices in debt through a sequence of legal firing moves.

Despite the model's importance, a dedicated, user-friendly software package for its study in Python has been lacking. While general-purpose graph libraries exist, they do not provide the specialized data structures, operations, and algorithms central to chip-firing theory. The *chipfiring* package aims to fill this gap.

This paper describes our Python-based scientific software package for setting up and analyzing chip-firing games. We focus on the tools for constructing graphs and divisors, performing firing moves, and solving the winnability problem. The package provides a clean, object-oriented API with comprehensive documentation and type hints, following modern Python standards. The package also includes interactive visualizations for selected functions to help mathematicians develop intuition and assist students in learning key concepts. The package is available on PyPI, detailed documentation is deployed via ReadTheDocs, and the source code is available on the project's GitHub repository.

• PyPI: https://pypi.org/project/chipfiring
* Documentation: https://chipfiring.readthedocs.io

* GitHub: https://github.com/DhyeyMavani2003/chipfiring

Since the package is readily available on the Python Package Index (PyPI), it can be installed by running:

```
pip install chipfiring
```

For the rest of this paper, we will refer to version 1.1.1 of the package.

The package has minimal dependencies, requiring only NumPy for numerical computations, NetworkX for specific gonality-based algorithms, and Dash, Dash Cytoscape, and Dash Bootstrap Components for visualization capabilities. This lightweight approach ensures easy integration into existing mathematical computing environments with official support for Python versions 3.8, 3.9, 3.10, 3.11, 3.12, and 3.13, as confirmed by intermittent GitHub-Actions runners on our GitHub repository.

The chipfiring package is a specialized tool. While libraries like NetworkX [3] are excellent for general graph analysis, they lack the domain-specific features for chip-firing. Table 1 provides a feature comparison.

<table><caption>Table 1: Feature comparison with general graph libraries.</caption><thead><tr><td>Feature</td><td>chipfiring</td><td>General Library (e.g., NetworkX)</td></tr></thead><tbody><tr><td>Graph Representation</td><td>Yes</td><td>Yes</td></tr><tr><td>Divisor/State Object</td><td>Yes</td><td>No</td></tr><tr><td>Chip-Firing Operations</td><td>Yes</td><td>No</td></tr><tr><td>Dhar's Algorithm</td><td>Yes</td><td>No</td></tr><tr><td>Divisor Rank/Reduction</td><td>Yes</td><td>No</td></tr><tr><td>Linear Equivalence Testing</td><td>Yes</td><td>No</td></tr><tr><td>Q-Reduction Algorithm</td><td>Yes</td><td>No</td></tr></tbody></table>

In the following sections, we will review the mathematical background, which is also summarized in [4]. We will provide embedded commentaries and demonstrations on using the chipfiring package. Comprehensive discussion of the functions and arguments within our API framework may be found at https://chipfiring.readthedocs.io.

The organization and notation of this paper closely follows the textbook of Corry and Perkinson [5], and our package consists in large part of implementing the algorithms and formalizing the abstractions therein. We have also drawn inspiration from the excellent exposition on chip-firing and graph gonality in [6], and have included some premade constructions for the reader to experiment with the graphs studied there. Indeed, a reader new to this subject would be well served to study Corry and Perkinson's excellent textbook, or the paper [6], side-by-side with this paper and a Python notebook, trying experiments and examples of each new idea using the chipfiring package. We hope very much that some readers, who will undoubtedly encounter functionality they wish were present or possible improvements to the implementations, will contribute to the project; see Section 6.3.

## 2 Creating and visualizing graphs

Before proceeding to the details of the chipfiring game, we demonstrate the syntax for creating (multi-) graphs in the chipfiring package. Graphs are created by specifying a set of vertex names, represented as strings, and a list of edges with specified multiplicities. Once created, a graph can be visually displayed using the visualize command. Here is a first example.

```python
from chipfiring import CFGraph, CFDivisor, visualize

# Define a graph
vertices = {"Alice", "Bob", "Charlie", "Elise"}
edges = [
    ("Alice", "Bob", 1), ("Alice", "Charlie", 1), ("Alice", "Elise", 2),
    ("Bob", "Charlie", 1), ("Charlie", "Elise", 1)
]
graph = CFGraph Problem vertices, edges

# Note that this launches a web-based interactive visualization at localhost:8050,
# so the program will halt until the user manually closes the visualization
```
Chip-Firing Visualizer

Graph Visualization

<figure><img src="image_2.png" /></figure>

Chip-Firing Visualizer

Graph Visualization

<figure><img src="image_3.png" /><figcaption>Figure 1: Screenshots of two example CFGraph visualizations.</figcaption></figure>

```python
# (Ctrl + C in the terminal)
visualize(graph)
```

The resulting visualization is shown in Figure 1.

The package also provides several pre-built graph constructions studied in [6], which is an excellent introduction to the study on graph gonality. The code below shows how to create these graphs, and visualize the octahedron graph. The output is shown in Figure 1.

```python
from chipfiring import tetrahedron, cube, octahedron, dodecahedron, icosahedron,
visualize
```

```python
# Platonic solid graphs (available for research purposes)
tetra = tetrahedron()  # K_4
cube_graph = cube()    # 3-regular, 8 vertices
octa = octahedron()    # Complete tripartite K_{2,2,2}
dodec = dodecahedron() # 3-regular, 20 vertices
icos = icosahedron()  # 5-regular, 12 vertices
```

```python
# For example, we can visualize the octahedron
visualize(octa)
```

## 3 The Dollar Game

Consider a graph $G = (V, E)$ with $V$ as a set of vertices representing people and $E$ as a set of edges representing relationships between them. The more edges between individuals, the stronger the relationship. At each vertex, we also record their wealth via an integer representing the number of dollars they have, with negative values indicating debt. The goal is to find a sequence of lending/borrowing moves after which everyone becomes debt-free. In one move, a vertex can lend money (fire) or borrow money by taking or sending 1 unit of currency across each edge it shares in the graph. This is called the *dollar game on G*, and if such a **sequence exists**, the game is said to be **winnable**.

Let us walk through an example in Figure 2 to illustrate the setup better.

Alice starts with a wealth of 2, Bob is in debt with -3, Charlie has 4, and Elise is slightly in debt with -1. The edges between vertices represent relationships; in each turn, a person can either lend, borrow, or do nothing with **all** the edges they are connected to. For instance, Charlie can lend 1 to each of Elise, Alice, and Bob, which takes Elise out of debt, leaving Alice with 2 and Bob with -2. The game continues until no one remains in debt, and if such a redistribution is possible, the game is considered **winnable**.

Before exploring solutions to this game, let us formalize this setup. Our discussion closely follows the exposition of [5].
<figure><img src="image_4.png" /><figcaption>Figure 2: Situational wealth distribution & relationship setup.</figcaption></figure>

## 3.1 Divisors & Linear Equivalence

When we mention a **graph**, we refer to a *finite, connected, undirected multigraph without loop edges*. Essentially, a **multigraph** $G = (V, E)$ consists of two components: a set of vertices $V$ and a multiset of edges $E$, where each edge is an unordered pair $\{v, w\}$ representing connections between vertices. The prefix “multi” means that pairs like $\{v, w\}$ can appear multiple times in $E$. We often simplify notation by writing an edge as $vw$. A multigraph $G$ is considered finite if both $V$ and $E$ are finite and connected if there is a path of edges between any two vertices.

**Definition 3.1.** (cf. [5, Definition 1.3]) A **divisor** on the graph $G$ is an element of the *free abelian group* on its vertices:

$$ \mathrm{Div}(G) = \mathbb{Z}^V = \left\{ \sum_{v \in V} D(v)v : D(v) \in \mathbb{Z} \right\}. $$

Divisors can be thought of as ways to describe the wealth distribution on $G$. If $D = \sum_{v \in V} D(v) \cdot v \in \mathrm{Div}(G)$, then $D(v)$ gives the amount of money at the vertex (or person) $v$, with negative values representing debt. The total money in the system is captured by the *degree* of the divisor as defined below.

**Definition 3.2.** (cf. [5, Definition 1.4]) The **degree** of a divisor $D = \sum_{v \in V} D(v) \cdot v \in \mathrm{Div}(G)$ is defined as:

$$ \mathrm{deg}(D) = \sum_{v \in V} D(v). $$

For instance, from the example presented earlier in Figure 2, the divisor $D$ can be represented as $D = 2(A) - 3(B) + 4(C) - (E)$, and thus the $\mathrm{deg}(D) = 2 - 3 + 4 - 1 = 2$.

We use $\mathrm{Div}^k(G)$ to denote all divisors with degree $k$, and $\mathrm{Div}_+(G)$ for divisors with a non-negative degree. Note that the word “degree” can refer to two things in our sub-domain at the intersection of graph theory and combinatorics, so for clarity, we write $\mathrm{val}(v)$ (valence of $v$) for the number of edges connected to $v$.

In the package, multigraphs and divisors are represented by the CFGraph and CFDivisor classes, which are specifically designed for chip-firing operations. The setup for the example above can be reproduced as follows:

```python
from chipfiring import CFGraph, CFDivisor

# Define a graph
vertices = {"Alice", "Bob", "Charlie", "Elise"}
edges = [
    ("Alice", "Bob", 1), ("Alice", "Charlie", 1), ("Alice", "Elise", 2),
    ("Bob", "Charlie", 1), ("Charlie", "Elise", 1)
]
graph = CFGraph Problem vertices, edges

# Define a divisor
```
What is interesting here is that the order in which lending or borrowing happens does not matter. This gives the dollar game an **abelian property**, meaning the operations commute with each other.

**Definition 3.4.** (cf. [5, Definition 1.6]) Suppose $D'$ is obtained from $D$ by lending from all the vertices in some subset $W \subseteq V$. In this case, we call this a **set-lending** (or **set-firing**) move by $W$, denoted $D \xrightarrow{W} D'$.

Using these definitions, let us try to perform set-firing on the example divisor shown in Figure 2 earlier in this section.

<figure><img src="image_5.png" /><figcaption>Figure 4: Application of set-firing moves leading to a win in the case of the divisor mentioned in Figure 2</figcaption></figure>

As shown in Figure 4, we can have a firing-set $W_1 = \{A, E, C\}$. After this firing move, all the internal lending and borrowing between the members of the firing set cancels out, and effective lending of 2 happens to $B$ from $A \& C$ lending 1 each. Now, to get $B$ out of debt, we repeat the same set-firing move on this newly obtained divisor with $W_2 = W_1$. This gives us the divisor that can be represented as $0(A) + 1(B) + 2(C) - 1(E)$. Finally, to get $E$ out of debt, we can carefully engineer our firing set to be $W_3 = \{B, C\}$. This ensures we take the minimum number of lenders out of debt (vaguely speaking). After this move, as shown in the figure, all the graph members come out of debt, signifying that we have won the game!

The above steps can be performed via chipfiring as follows:

```
# First firing: Alice, Elise, Charlie set fire
divisor.set_fire({"Alice", "Elise", "Charlie"})
```

```
# Second firing: Alice, Elise, Charlie set fire (again)
divisor.set_fire({"Alice", "Elise", "Charlie"})
```

```
# Third firing: Bob, Charlie set fire
divisor.set_fire({"Bob", "Charlie"})
```

**Proposition 3.5.** (cf. [5, Exercise 1.7]) Borrowing from a vertex $v \in V$ is just like lending from all vertices in $V \setminus v$, and if we perform set-lending from all vertices in $V$, the net effect is zero.

**Definition 3.6.** (cf. [5, Definition 1.8]) A divisor $D$ is said to be **linearly equivalent** to another divisor $D'$, denoted $D \sim D'$, if we can obtain $D'$ from $D$ by a sequence of lending moves.

**Definition 3.7.** (cf. [5, Definition 1.11]) The **divisor class** determined by $D \in \text{Div}(G)$ is:

$$[D] = \{D' \in \text{Div}(G) : D' \sim D\}.$$
One can think of a divisor class as a self-contained economy where the total wealth does not change, but the distribution of wealth might shift around. In simpler terms, it represents all possible money distributions that can be achieved through lending.

**Definition 3.8.** (cf. [5, Definition 1.13]) A divisor $D$ is **effective** if $D(v) \ge 0$ for all $v \in V$, meaning no one is in debt. The set of effective divisors on $G$ is denoted by $\text{Div}_+(G)$.<fnref n="1" /> We write this as $D \ge 0$.

Thus, we can see that using the above definitions, the **objective** of the dollar game becomes: *Is a given divisor linearly equivalent to an effective divisor?*

**Definition 3.9.** (cf. [5, Definition 1.14]) A divisor $D$ is **winnable** if $D$ is linearly equivalent to an effective divisor. Otherwise, it is **unwinnable**.

Linear equivalence, effectiveness, and winnability can be checked in chipfiring as follows:

```python
from chipfiring import linear_equivalence, is_winnable
divisor1.is_effective()
linear_equivalence(divisor1, divisor2)
is_winnable(divisor1)
```

**Definition 3.10.** (cf. [5, Definition 1.22]) A complete linear system of $D \in \text{Div}(G)$ is:

$$|D| = \{E \in \text{Div}(G) : E \sim D, E \ge 0\}.$$

Equivalently, a complete linear system is the set of all effective divisors on graph $G$ that are linearly equivalent to $D$.

## 3.2 Laplacian & Firing Script

In general, a Laplacian aims to measure the “equitability” or evenness of a diffusive process in pure sciences. Similar to the continuous case, we define a discrete Laplacian by drawing some parallels. Before we start defining the Laplacian, let us generalize our notion of set-firing of $V$ from the previous section into a firing-script, where we plan to compactly encode the essential information for the move in which some vertices in lending subset $V$ lend/borrow multiple times, for instance.

**Definition 3.11.** (cf. [5, Definition 2.2]) A firing script is a function $\sigma: V \to \mathbb{Z}$, which denotes the number of times each vertex $v$ lends (fires) if $\sigma(v) > 0$. If $\sigma(v) < 0$, it denotes the number of borrowing moves. Moreover, if $\sigma(v) = 0$, the vertex $v$ does not participate in the move.<fnref n="2" />

Furthermore, a discrete Laplacian operator is used to map a firing script to a divisor, and we define it as follows:

**Definition 3.12.** (cf. [5, Definition 2.1]) The discrete Laplacian operator on $G$ is the linear mapping $L: \mathbb{Z}^V \to \mathbb{Z}^V$ defined by

$$L(f)(v) := \sum_{vw \in E} (f(v) - f(w)),$$

where the space $\mathbb{Z}^V := \{f: V \to \mathbb{Z}\}$ contains $\mathbb{Z}$-valued functions on the vertices of $G$.

In the context of chip firing games, we can think of the discrete Laplacian as a tool that maps a firing script in $M(G)$ to a resulting divisor in $\text{Div}(G)$. If $\sigma: V \to \mathbb{Z}$ is a firing script, then the resulting divisor after firing is given by:

$$\begin{aligned}
D' &= D - \sum_{v \in V} \sigma(v) \left( \text{val}(v)v - \sum_{vw \in E} w \right) = D - \sum_{v \in V} \sigma(v) \sum_{vw \in E} (v-w) \\
&= D - \sum_{v \in V} \left( \text{val}(v)\sigma(v) - \sum_{vw \in E} \sigma(w) \right) v = D - \sum_{v \in V} \sum_{vw \in E} (\sigma(v) - \sigma(w))v
\end{aligned}$$

Thus, any divisor can & should be reached by a firing script from any other divisor in the linearly equivalent set.

**Definition 3.13.** (cf. [5, Definition 2.3, Exercise 2.4]) The script-firing with firing script $\sigma$ is denoted by $D \xrightarrow{\sigma} D'$, and because degree is preserved under firing moves, we also have $\text{deg}(L(\sigma)) = 0$.

<footnote n="1">¹Since the set $\text{Div}_+(G)$ does not have inverses, it is NOT a subgroup of $\text{Div}(G)$, but rather a commutative monoid.</footnote>

<footnote n="2">²**Aside:** The collection of all firing scripts form an abelian group $M(G)$ or $\mathbb{Z}^V$ [5, Definition 2.2].</footnote>
**Definition 3.14.** (cf. [5, p. 20]) The **principal divisor** associated to a firing script $\sigma$ is

$$ \mathrm{div}(\sigma) := \sum_{v \in V} \left( \mathrm{val}(v) \cdot \sigma(v) - \sum_{vw \in E} \sigma(w) \right) v. $$

It is also worth noting that the set of principal divisors form a subgroup $\mathrm{Prin}(G) < \mathrm{Div}^0(G)$. This also means that linear equivalence class of D is coset of $\mathrm{Prin}(G)$: $[D] = D + \mathrm{Prin}(G)$. From this, we also define the Picard Group as $\mathrm{Pic}(G) = \mathrm{Div}(G)/\mathrm{Prin}(G)$ and the Jacobian Group as $\mathrm{Jac}(G) = \mathrm{Div}^0(G)/\mathrm{Prin}(G)$. The Jacobian group is also called the *critical group*. [2, 7]

The matrix representation of the Laplacian operator will be the Laplacian matrix, which is can also be written as follows.
**Definition 3.15.** (cf. [5, Definition 2.6]) The *Laplacian matrix*, also denoted by $L$, is the $|V| \times |V|$ integer matrix with

$$ L_{ij} = L(\chi_j)(v_i) = \begin{cases} \mathrm{val}(v_i) & \text{if } i = j \\ -\begin{pmatrix} \# \text{ of edges between } v_j \text{ and } v_i \end{pmatrix} & \text{if } i \neq j. \end{cases} $$

Here $\chi_j(v_i) = \begin{cases} 1 & i = j \\ 0 & i \neq j. \end{cases}$ is the firing script of $v_j$ making a single lending move (to $v_i$).

It is also evident that $L = \mathrm{Deg}(G) - A^T$, where $\mathrm{Deg}(G)$ is a diagonal matrix with vertex-degrees of $G$, and $A$ is the adjacency matrix. All lending moves are encoded in $L$ because the lending move by $v_j$ corresponds to subtracting the $j$th column of $L$ from a divisor at hand. For instance, given a firing-script column vector $\vec{\sigma}$, we can say $D' = D - L\vec{\sigma}$.

As an illustration, going back to the example we have discussed so far in Figure 4, we can see that the Laplacian matrix assumes the following form:

$$ L = \begin{bmatrix} 4 & -1 & -1 & -2 \\ -1 & 2 & -1 & 0 \\ -1 & -1 & 3 & -1 \\ -2 & 0 & -1 & 3 \end{bmatrix}, \text{ which is filled in with headers as } \begin{array}{c|cccc} & V_{\mathrm{Alice}} & V_{\mathrm{Bob}} & V_{\mathrm{Charlie}} & V_{\mathrm{Elise}} \\ \hline & 4 & -1 & -1 & -2 \\ V_{\mathrm{Alice}} & -1 & 2 & -1 & 0 \\ V_{\mathrm{Bob}} & -1 & -1 & 3 & -1 \\ V_{\mathrm{Charlie}} & -2 & 0 & -1 & 3 \\ V_{\mathrm{Elise}} & -1 & -1 & -1 & 3 \end{array} $$

Moreover, from Figure 4, we can see that to win (reach an effective divisor), Bob borrowed twice, and then Bob and Charlie both can be considered to lend once. So, we can represent this in the form of a firing script (ordered column

vector) as: $\vec{\sigma} = \begin{bmatrix} 0 \\ -1 \\ 1 \\ 0 \end{bmatrix}$. Thus,

$$ D' = \begin{bmatrix} 2 \\ -3 \\ 4 \\ -1 \end{bmatrix} - \begin{bmatrix} 4 & -1 & -1 & -2 \\ -1 & 2 & -1 & 0 \\ -1 & -1 & 3 & -1 \\ -2 & 0 & -1 & 3 \end{bmatrix} \begin{bmatrix} 0 \\ -1 \\ 1 \\ 0 \end{bmatrix} = \begin{bmatrix} 2 \\ -3 \\ 4 \\ -1 \end{bmatrix} - \begin{bmatrix} 0 \\ -3 \\ 4 \\ -1 \end{bmatrix} = \begin{bmatrix} 2 \\ 0 \\ 0 \\ 0 \end{bmatrix} $$

We can see that the final result $D'$ matches the effective divisor we obtained in Figure 4 right when we hit the win condition. The above example can be performed in chipfiring as follows:

```python
from chipfiring import CFGraph, CFLaplacian, CFiringScript
import numpy as np

# Create Laplacian for a CFGraph
laplacian = CFLaplacian(graph)

# Create a firing script (net firings at each vertex)
script = {"Charlie": 1, "Bob": -1} # Charlie lends 1, Bob borrows 1
firing_script = CFiringScript(graph, script)

# Apply the Laplacian: D' = D - L * firing_script
result_divisor = laplacian.apply(initial_divisor, firing_script)
print(f"Result: {result_divisor degrees_to_str()}")
```
# 4 Algorithms for Winnability

Having defined our setup and objective (winnability), we now consider some algorithms for winnability determination.

## 4.1 Greedy Algorithm

One way to play the dollar game is for each in-debt vertex to attempt to borrow its way out of debt. The problem is that borrowing once from each vertex is the same as not borrowing at all. Solving this gives an algorithm for the dollar game, which is essentially repeatedly choosing an in-debt vertex and making a borrowing move at that vertex until either the game is won or it becomes impossible to go on without reaching a state in which all of the vertices have made borrowing moves. Below, we first present an adaptation of the algorithm's pseudocode from [5, §3.1].

**Note on Uniqueness of the greedy algorithm script:** The greedy algorithm 3 can be modified to produce a firing script if its input is winnable. Initialize by setting $\sigma = 0$, and then each time step 6 of the algorithm below is invoked, replace $\sigma$ by $\sigma - v$. It turns out that the resulting script is independent of the order in which vertices are added.

**Algorithm 1 Greedy algorithm for the dollar game. (Adapted from [5, Algorithm 1])**

**Require:** $D \in \text{Div}(G)$.

**Ensure:** TRUE if $D$ is winnable; FALSE if not.

1: **initialization:** $M = \emptyset \subseteq V$, the set of marked vertices.

2: **while** $D$ not effective **do**

3: **if** $M \neq V$ **then**

4: choose any vertex in debt: $v \in V$ such that $D(v) < 0$

5: modify $D$ by performing a borrowing move at $v$

6: **if** $v$ is not in $M$ **then**

7: add $v$ to $M$

8: **end if**

9: **else**

10: /* required to borrow from all vertices */

11: **return** FALSE

/* unwinnable */

12: **end if**

13: **end while**

14: **return** TRUE

/* winnable */

Let's now introduce the greedy algorithm Pythonic API from our chipfiring package.

```python
from chipfiring import CFGraph, CFDivisor, GreedyAlgorithm

# Initialize Greedy Algorithm with a CFGraph and a CFDivisor
algorithm = GreedyAlgorithm(graph, divisor)

# Run the algorithm to determine winnability
# The winnability determination and a CFiringScript object are returned
winnable, firing_script = algorithm.play()
```

## 4.2 “Benevolence” Algorithm

Rather than implementing greed, one might try its opposite: a “benevolent” vertex $q$ might choose to concentrate all the games’ debt upon itself. One particular form of benevolence that is of significant theoretical and algorithmic importance is encapsulated in the following notion. Informally, one can view this notion as follows: the vertex $q$ volunteers to be the only vertex in debt, on the condition that the remaining vertices move as much money as possible in $q$’s direction, without going into debt.

**Definition 4.1.** (cf. [5, Definition 3.4]) Let $q \in V$. A divisor $D \in \text{Div}(G)$ is called *q-reduced* if both

1. $D(v) \ge 0$ for all $v \in V \setminus \{q\}$, and

2. For every nonempty subset $S \subseteq V \setminus \{q\}$, there exists a vertex $v \in S$ such that $D(v) < \text{outdeg}_S(v)$, where $\text{outdeg}_S(v)$ denotes the number of edges $vw$ such that $w \notin S$.

<footnote n="3">³Proof of the validity of the greedy algorithm, and the uniqueness of generated firing script can be found in [5, §3.1].</footnote>
It is convenient to have a shorthand for this second condition, which is provided by the next definition.

**Definition 4.2.** (cf. [5, Definition 3.3]) Let $D \in \text{Div}(G)$, and let $S \subseteq V$. Suppose $D'$ is obtained from $D$ by firing each of the vertices in $S$ once. Then $D \xrightarrow{S} D'$ is a **legal set-firing** if $D'(v) \ge 0$ for all $v \in S$, i.e., after firing $S$, none of the vertices in $S$ are in debt. In this case, we say it is **legal to fire** $S$. [Note: if it is legal to fire $S$, then the vertices in $S$ must also be out of debt *before* firing.]

Now observe that the second condition of Definition 4.1 may be rephrased as: it is not legal to fire any nonempty set $S$ that does not contain $q$. It is in this sense that the chips of $D$ cannot be pulled any closer to $q$. The existence of such a divisor is neatly established by a minimization argument, using the following order.

**Definition 4.3.** (cf. [5, Exercise 3.7]) Given divisors $D, D' \in \text{Div}(G)$ and a spanning tree $(T, q)$ of $G$ rooted at a vertex $q$, let $v_1 = q, v_2, \dots, v_n$ be a tree ordering of the vertices, where:

* $T$ is a connected, cycle-free subgraph of $G$ that includes all vertices and contains exactly $n-1$ edges (i.e., a spanning tree),

* the ordering respects the structure of $T$, meaning that if $v_i$ lies on the unique path from $q$ to $v_j$ in $T$, then $i < j$.

We say that $D' \prec D$ if either:

1. $\deg(D') < \deg(D)$, or

2. $\deg(D') = \deg(D)$ and there exists an index $i$ such that $D'(v_i) > D(v_i)$, and for all $j < i$, $D'(v_j) = D(v_j)$. Equivalently, $D \neq D'$ and, for the minimum index $i$ such that $D'(v_i) \neq D(v_i)$, we have $D'(v_i) > D(v_i)$.

In other words, $\prec$ is the reverse lexicographic order on divisors of the same degree, where the coefficients are written according to the chosen tree ordering. The utility of $\prec$ is that it encapsulates the idea that $D' \prec D$ if the chips of $D'$ have been “pulled closer to” $q$, in a sense.

**Proposition 4.4.** (cf. [5, Exercise 3.7]) Fix a divisor $D$, and let $\mathcal{D}$ denote the set of all divisors $D' \sim D$ such that $D'(v) \ge 0$ for all $v \neq q$. Suppose that $D'$ is minimal in $\mathcal{D}$ under the order $\prec$. Then $D'$ is $q$-reduced.

*Proof.* Suppose to the contrary that $D' \in \mathcal{D}$ is not $q$-reduced. Then there is some legal set-firing $D' \xrightarrow{S} D''$ where $\emptyset \neq S \subseteq V \setminus q$. Let $v_i \in S$ be the minimum element of $S$ under the chosen tree ordering, and let $v_j$ be the parent of $v_i$ in the spanning tree. Then firing $S$ sends at least one chip from $v_i$ to $v_j$. Furthermore, none of the vertices $v_2, \dots, v_j$ is in $S$, so none of these vertices lose chips when firing $S$. Since at least one of them gains a chip, this implies that $D'' \prec D'$, so $D'$ is not minimal. $\square$

In fact, the converse of Proposition 4.4 is also true, though we omit the proof; see [5, Theorem 3.6]. That is, the $q$-reduced divisors $D_q \sim D$ is unique. It follows from definitions that if any $D' \sim D$ is effective, then $D_q$ must be. Therefore:

**Proposition 4.5.** (cf. [5, Corollary 3.7]) Let $D \in \text{Div}(G)$, and let $D'$ be the $q$-reduced divisor linearly equivalent to $D$. Then $|D| \neq \emptyset$ if and only if $D' \ge 0$. In other words, $D$ is winnable if and only if $D'(q) \ge 0$.

From this, we obtain a version of “benevolence” guaranteed to produce an effective $E \sim D$ if it exists. This can be done by following the steps, which are adapted from [5, §3.2].

1. Pick some “benevolent vertex” $q \in V$. Call $q$ the source vertex, and let $V \setminus \{q\}$ be the set of non-source vertices.

2. Let $q$ lend/fire so many chips that the non-source vertices, sharing among themselves, are out of debt. This is done to concentrate the debt at the source vertex.

3. At this stage, only $q$ is in debt, and it makes no further lending or borrowing moves. It is now the job of the non-source vertices to try to relieve $q$ of its debt. Look for $S \subseteq V \setminus \{q\}$ with the legal set-firing property as stated in definition 4.2. Having found such an $S$, make the corresponding set-lending move.

4. Repeat until no such $S$ remains. The resulting divisor is said to be $q$-reduced. More importantly, if, in the end, $q$ is no longer in debt, $D$ is winnable. Otherwise, $|D| = \emptyset$, or equivalently $D$ is unwinnable.

In the chipfiring package, this procedure can be performed with the following syntax.
from chipfiring import q_reduction, is_q_reduced

# Given any divisor, return a q-reduced divisor
q_red_div = q_reduction(divisor)

# Check if any given divisor is q_reduced
is_q_reduced(divisor)

As mentioned in [5], some naturally interesting questions about this strategy are: Is it always possible to complete step 2? Is step 3 guaranteed to terminate? If the strategy does not win, does this mean the game is unwinnable? (After all, the moves in step 3 are constrained.) Is the resulting q-reduced divisor unique? Can the strategy be efficiently implemented?

The following sections gradually show that the answer to all of these questions is “yes,” and explain the implementation of q_reduction.

## 4.3 Configurations & related preliminaries

In many computations, it is useful to choose a special vertex $q$ and ignore any chips at $q$. Following [5], we use the word configuration for a divisor without a specified degree at $q$.

**Definition 4.6.** (cf. [5, §2.2]) Fix a vertex $q \in V$ and define $\tilde{V} := V \setminus \{q\}$. Then a configuration $c$ is an element of the subgroup

$$ \mathrm{Config}(G, q) = \mathbb{Z}\tilde{V} \subseteq \mathbb{Z}V = \mathrm{Div}(G). $$

We also write $c' \ge c$ for $c, c' \in \mathrm{Config}(G)$ if $c(v) \ge c'(v)$ for all $v \in \tilde{V}$. A configuration $c$ is said to be non-negative ($c \ge 0$) is $c(v) \ge 0$ for all $v \in \tilde{V}$. We define lending & borrowing operations on configurations the same way as with divisors, but in the case of configurations, we do not keep track of the number of chips present at $q$.

**Definition 4.7.** (cf. [5, §2.2]) The degree of a configuration $c$ is calculated as $\mathrm{deg}(c) = \sum_{v \in \tilde{V}} c(v)$.

**Definition 4.8.** (cf. [5, §2.2]) Configurations $c$ and $c'$ are said to be linearly equivalent, written as $c \sim c'$ if they can be transformed into one another through a sequence of lending and borrowing operations.

**Note:** Unlike linearly equivalent divisors, linearly equivalent configurations need not have the same degree. In effect, the difference of degrees tells how many chips were fired to or from $q$. More precisely, $c \sim c'$ as configurations if and only if $c - \mathrm{deg}(c)q \sim c' - \mathrm{deg}(c')q$ as divisors.

For instance, let us consider a slight relabeling of the example in Figure 2, where Bob is labeled as $q$, and thus we consider configurations with respect to Bob. We can see configurations $c \sim c'$ as depicted in Figure 5.

<figure><img src="image_6.png" /><figcaption>Figure 5: Application of firing move by Charlie, on configurations with respect to $q = \text{Bob}$. This is the same graph as Figure 2.</figcaption></figure>

The notion of a q-reduced divisor corresponds to the notion of *superstable* configuration, as defined below.
**Definition 4.9.** (cf. [5, Definition 3.11]) Let $c \in \text{Config}(G)$, and let $S \subseteq \tilde{V}$. Suppose $c'$ is the configuration obtained from $c$ by firing the vertices in $S$. Then $c \xrightarrow{S} c'$ is a **legal set-firing** if $c'(v) \ge 0$ for all $v \in S$.

**Definition 4.10.** (cf. [5, Definition 3.12]) The configuration $c \in \text{Config}(G)$ is **superstable** if $c \ge 0$ and has no legal nonempty set-firings. Equivalently, for all nonempty $S \subseteq \tilde{V}$, there exists $v \in S$ such that $c(v) < \text{outdeg}_S(v)$.

Now, let's introduce our chipfiring package API corresponding to these notions.

```python
from chipfiring import CFConfig

# Given any divisor, and a vertex q, initialize a configuration
conf_wrt_Bob = CFConfig(divisor, q_name="Bob")

# Retrieve degrees at non-q vertices of the configuration
degree_of_conf_wrt_Bob = conf_wrt_Bob.get_degree_sum()

# Calculate outdegree of the configuration
# with respect to vertex v and set S
conf_wrt_Bob.get_out_degree_S(
    v_name_in_S = "Alice",
    S_names = {"Alice", "Charlie"}
)

# Check if a given set S is legal set-firing
conf_wrt_Bob.is superstable(
    S_names = {"Alice", "Charlie"}
)

# Check superstability of configuration
conf_wrt_Bob.is_sustable()

# Retrieving underlying properties of configuration
print(f"Degree at q: {config.get_q_underlying_degree()}")
print(f"Configuration on V~: {config.get_v_tilde_names()}")
```

## 4.4 Dhar's Algorithm

Upon rebranding *q*-reducedness as superstability, we can rephrase the task set before us: given a configuration $c$, we wish to repeatedly find legal sets to fire until we arrive at a superstable configuration. Naturally, we wish to find such sets without having to search through the entire parameter space of $2^{|\tilde{V}|} - 1$ plausible subsets. A beautiful answer to this need is provided by *Dhar's burning algorithm*. This algorithm was introduced in [1]; we follow the exposition of it in [5, §3.4.1].

Let $c \in \text{Config}(G, q)$, and assume $c \ge 0$ (if we begin with a non-effective configuration, we should first lend generously from $q$ and spread the wealth). Now, to find a legal set-firing for $c$, if it exists, imagine the edges of our graph are made of wood so that when vertex $q$ is ignited, the fire spreads along its incident edges. Furthermore, think of the configuration $c$ as $c(v)$ firefighters present at each $v \in \tilde{V}$, given that each firefighter can only control the fire coming from a single edge. This tells us that a vertex is protected only if the number of burning incident edges is $\le c(v)$. Otherwise, the firefighters fail, and the vertex is set on fire.<fnref n="4" /> In the end, we conclude that the unburnt vertices constitute a set that may be legally fired from $c$ and that if this set is empty, then by Definition 4.10, $c$ is superstable. We adapt below the pseudocode version of the algorithm from [5, §3.4.1].

Let us run through Dhar's algorithm described above in Figure 6 while continuing from the starting linearly equivalent configuration ($c'$), which we obtained in Figure 5. After the vertex $q$ is set on fire, it sets two edges on fire (one between Alice and Bob and one between Bob and Charlie). However, since there are $3 \ge 1$ firemen at Alice's vertex, and there are $1 \ge 1$ firefighters at Charlie's vertex, the algorithm terminates and outputs the legal set firing as the set $S = \{\text{Alice, Elise, Charlie}\}$ as expected.

Since we have Dhar's algorithm as a tool, let us revisit the procedure of finding *q*-reduced divisors (the “benevolence” algorithm) as described in Section 4.2. Below, we present an adaptation of the pseudocode version of the updated

<footnote n="4">⁴Fun Note (cf. [5, p. 46]): No need to worry; firefighters are rescued by an underground tunnel built by Amherst College.</footnote>
**Algorithm 2** Dhar's algorithm.

**Require:** a nonnegative configuration $c$

**Ensure:** a legal firing set $S \subseteq \tilde{V}$, empty iff $c$ is superstable

1: **initialization:** $S = \tilde{V}$

2: **while** $S \neq \emptyset$ **do**

3: &nbsp;&nbsp;&nbsp;&nbsp;**if** $c(v) < \text{outdeg}_S(v)$ for some $v \in S$ **then**

4: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$S = S \setminus \{v\}$

5: **else**

6: &nbsp;&nbsp;&nbsp;&nbsp;**return** $S$

7: **end if**

8: **end while**

9: **return** $S$

/* c is not superstable */

<figure><img src="image_7.png" /><figcaption>Figure 6: Application of Dhar's Algorithm on the same graph as Figure 5</figcaption></figure>

algorithm described in [5, §3.4.2]. This algorithm has some additional peculiar optimizations, which can help decrease the runtime.

**Algorithm 3** Find the linearly equivalent $q$-reduced divisor.

**Require:** $D \in \text{Div}(G)$ and $q \in V$

**Ensure:** the unique $q$-reduced divisor linearly equivalent to $D$

1: Use a greedy algorithm to bring each vertex $v \neq q$ out of debt, so that we may assume $D(v) \ge 0$ for all $v \neq q$.

2: Repeatedly apply Dhar's algorithm until $D$ is $q$-reduced.

The Dhar's algorithm implementation from chipfiring can be used as follows; it returns the firing set as well as an "orientation," which is defined in Definition 5.3:

```python
from chipfiring import CFGraph, CFDivisor, DharAlgorithm

# Initialize Dhar's algorithm with a CFGraph, CFDivisor, and the name of the 'q' vertex
dhar_algo = DharAlgorithm(graph, divisor, "Bob")

# Run the algorithm to find the maximal legal firing set
firing_set, orientation = dhar_algo.run()
```

## 4.5 An Efficient Winnability Determination Algorithm

Now, using all the tools & algorithms we have developed so far, let's devise an efficient winnability determination algorithm. We formalize the algorithm in the form of pseudocode below. Recall that $D_q(q) \ge 0$ directly translates to **winnability** by Proposition 4.5.
<caption>**Algorithm 4 Efficient Winnability Determination Algorithm**</caption>

**Require:** $D \in \text{Div}(G)$
**Ensure:** TRUE if $D$ is winnable; FALSE if not
1: Choose source vertex $q \in V$
2: Let $\tilde{V} \leftarrow V \setminus \{q\}$
3: Fire from $q$ and share among vertices in $\tilde{V}$ until only $q$ is in debt
4: **while** Dhar's Algorithm returns a non-empty set **do**
5: &nbsp;&nbsp;&nbsp;&nbsp;Apply Dhar's Algorithm to current configuration $c$
6: &nbsp;&nbsp;&nbsp;&nbsp;Fire the returned set if non-empty
7: &nbsp;&nbsp;&nbsp;&nbsp;**end while**
8: &nbsp;&nbsp;&nbsp;&nbsp;$D_q(q) \leftarrow \text{deg}(D) - \text{deg}(c)$
9: &nbsp;&nbsp;&nbsp;&nbsp;**if** $D_q(q) \ge 0$ **then**
10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**return** TRUE
11: &nbsp;&nbsp;&nbsp;&nbsp;**else**
12: &nbsp;&nbsp;&nbsp;&nbsp;**return** FALSE
13: **end if**

\* Set of non-source vertices \*/

\* Calculate chips on source vertex \*/

\* winnable \*/

\* unwinnable \*/

Furthermore, one of the strategies that can be used in step 3 of the algorithm below is to systematically concentrate all debt at our distinguished vertex $q$ through a reverse-distance prioritized approach. The key insight is that we can move debt away from vertices furthest from $q$ first, working our way inward toward $q$ systematically.

This strategy works by ordering all non-source vertices based on their distance from $q$, which we can determine through a simple breadth-first search (BFS) traversal. Then, proceeding from the vertices furthest from $q$ and moving inward, we perform borrowing operations on any vertex with a negative chip count (in debt). When a vertex borrows, it receives chips equal to its degree but must distribute one chip along each incident edge to its neighbors. This borrowing operation effectively pushes debt closer to $q$.

By processing vertices in reverse distance order (from furthest to closest to $q$), we ensure that once a vertex is out of debt, it remains out of debt throughout the process. This is because we only process vertices closer to $q$ after all vertices further from $q$ have been handled. The result is a configuration where only the source vertex $q$ may be in debt, with all other vertices having non-negative chip counts. In practice, the number of Dhar iterations is typically small. This makes the algorithm more efficient than exhaustive approaches that might simulate all possible chip-firing sequences.

As an illustration, we implemented this BFS-based debt clustering strategy along with Dhar's algorithm as a Python API in the chipfiring package. Upon running our implementation on the example from Figure 5, we can see that it outputs the following: "The game is winnable using Dhar's algorithm with a legal firing set of Alice, Charlie, Elise".

An example demonstrating how to use our package's implementation of the Efficient Winnability Determination Algorithm is below. Note that our implementation has an optional optimized mode that utilizes various matrix optimizations, theorems, lemmas, and properties to accelerate determination; note that you might not get the associated induced orientation and q-reduced divisor under this mode. There is also an optional visualize parameter that, if set to true, automatically generates an interactive visualization that will allow you to view the steps taken by EWD to generate the determination. The visualization of running EWD on the example from Figure 2 can be seen at Figure 7.

```python
from chipfiring import CFGraph, CFDivisor, EWD

# Given a CFGraph and CFDivisor, run the EWD algorithm to check for winnability.
# The function returns the winnability status, the q-reduced divisor,
# the final edge orientation, and a visualizer object (if enabled).
is_winnable, q_reduced, orientation, visualizer = EWD(
    graph,
    divisor,
    optimized = True,
    visualize = True
)

# Visualize
# Note that this launches a web-based interactive visualization at localhost:8050,
# so the program will halt until the user manually closes the visualization
# (Ctrl + C in the terminal)
visualizer.visualize()
```
<figure><img src="image_8.png" /><figcaption>Figure 7: Screenshot of an example visualization of the EWD Algorithm</figcaption></figure>

# 5 Riemann-Roch for Graphs & Rank Determination

In this section, we will build on some final tools, mainly including orientations and Baker-Norine ranks, which will, in turn, help us state and better understand the Riemann-Roch theorem for graphs. This will help us to quantify “winnability,” and study algorithms to quickly do the same. The notion of “rank” considered herein originated in [2], where the graph Riemann-Roch theorem was first stated and proved. The original proof hinges crucially on a set, denoted by $\mathcal{N}$ in [2] and sometimes called “moderators,” with two important interpretations: on the one hand, as maximal unwinnable divisors, and on the other hand as divisors arising from graph orientations. Therefore our chipfiring package provides tools for both the Baker-Norine rank and graph orientations.

**Definition 5.1.** Maximal unwinnable divisors are those unwinnable divisors $D$ such that for any unwinnable divisor $D'$, if $D \le D'$, then $D = D'$. Equivalently, $D$ is maximal unwinnable if $D$ is unwinnable, but $D + v$ is winnable for each $v \in V$.

**Definition 5.2.** Maximal superstable configurations are those superstable configurations $c$ such that for any superstable configuration $c'$, if $c \le c'$, then $c = c'$.

## 5.1 Orientations and Genus

**Definition 5.3.** A graph orientation $\mathcal{O}$ assigns a specific direction to each edge of the graph within the multiset of edges. For any edge $e = uv \in E$, we define $e^- = u$ as the starting vertex (tail) and $e^+ = v$ as the ending vertex (head), meaning that the edge $e$ is directed from $u$ to $v$.

**Definition 5.4.** The reverse orientation of $\mathcal{O}$, denoted by $\bar{\mathcal{O}}$, swaps the roles of the head and the tail of each edge. For instance, $e$ under $\bar{\mathcal{O}}$ would become $\bar{e}$ with $\bar{e}^- = v$ as the starting vertex (tail) and $\bar{e}^+ = u$ as the ending vertex (head).

A vertex $w$ is called a source for an orientation $\mathcal{O}$ if all edges incident to $w$ are directed away from $w$. Equivalently, if for all edges $e \in \mathcal{O}$, $e^+ \neq w$. Similarly, a vertex $v$ is called a sink for an orientation $\mathcal{O}$ if all edges incident to $v$ are directed towards $v$. Equivalently, for all edges $e \in \mathcal{O}$, $e^- \neq v$.

**Definition 5.5.** For any vertex $v \in V$ under an orientation $\mathcal{O}$, the outdegree counts the edges that start from $v$ (i.e. $\text{outdeg}_{\mathcal{O}}(v) = |\{e \in \mathcal{O}: e^- = v\}|$), while the indegree is the number of edges directed towards $v$ (i.e. $\text{indeg}_{\mathcal{O}}(v) = |\{e \in \mathcal{O}: e^+ = v\}|$).

**Definition 5.6.** (cf. [5, Definition 4.8]) A divisor associated with a given orientation $\mathcal{O}$ on the graph $G$ is defined as:

$$D(\mathcal{O}) = \sum_{v \in V} (\text{indeg}_{\mathcal{O}}(v) - 1) \cdot v.$$

**Definition 5.7.** (cf. [5, Definition 4.8]) The configuration associated to a source vertex $q \in V$ under $\mathcal{O}$ is defined as:

$$c(\mathcal{O}) = \sum_{v \in \bar{V}} (\text{indeg}_{\mathcal{O}}(v) - 1) \cdot v.$$

**Definition 5.8.** (cf. [5, Definition 5.7]) The canonical divisor $K$ of a graph $G$ is defined as: $K := D(\mathcal{O}) + D(\bar{\mathcal{O}})$. The canonical divisor only depends on graph $G$ and is independent of orientation because for any vertex $v \in V$, we have

$$K(v) = (\text{indeg}_{\mathcal{O}}(v) - 1) + (\text{outdeg}_{\mathcal{O}}(v) - 1) = \text{val}(v) - 2.$$
and thus, the canonical divisor can also be written as: $K := \sum_{v \in V} (\mathrm{val}(v) - 2) \cdot v$.

The name of the “canonical divisor” arises from algebraic geometry. See for example [8, Remark 4.19].

**Definition 5.9.** A *directed path* is a sequence of vertices connected by edges, where each vertex (except the first and last) acts as both the head of the previous edge and the tail of the next one.

**Note:** All vertices along a directed path are distinct, except possibly the start & end vertices.

**Definition 5.10.** A *directed cycle* is a directed path in which the start and end vertices are identical.

**Definition 5.11.** An orientation $\mathcal{O}$ is *acyclic* if it does not contain any cycle of directed edges.

**Note:** In the case of acyclic orientations, multiple edges between two vertices must be oriented in the same direction.

**Lemma 5.12.** An *acyclic orientation* can be determined by its *indegree sequence*: if $\mathcal{O}$ and $\mathcal{O}'$ are *acyclic orientations* of $G$ and $\mathrm{indeg}_{\mathcal{O}}(v) = \mathrm{indeg}_{\mathcal{O}'}(v)$ for all $v \in V$, then $\mathcal{O} = \mathcal{O}'$.

See [5, Lemma 4.3] for a proof.

If we revisit Dhar’s algorithm, as introduced in Section 4.4, we see that a bit more content may be extracted from it: the path of the fire tells us an acyclic orientation. This acyclic orientation is useful in other problems. We include the pseudocode for modified Dhar’s algorithm below. This algorithm is based on the discussion in [5, §4.2].

**Algorithm 5 Orientation-based Dhar’s Algorithm**

**Require:** a nonnegative configuration $c$ and source vertex $q$

**Ensure:** a pair $(S, \mathcal{O})$ where $S \subseteq \tilde{V}$ is a legal firing set (empty if and only if $c$ is superstable) and $\mathcal{O}$ is the resulting orientation

1: **initialization:** $S \leftarrow \tilde{V}$, $\mathcal{O} \leftarrow \emptyset$, $B \leftarrow \{q\}$ /* $B$ is burning set */

2: **while** $B \neq V$ **do**

3: **for** each $v \in S$ **do**

4: $E_v \leftarrow$ edges between $v$ and $B$ /* potentially burning edges */

5: **if** $|E_v| > c(v)$ **then**

6: $S \leftarrow S \setminus \{v\}$

7: $B \leftarrow B \cup \{v\}$

8: **for** each $e \in E_v$ **do**

9: Orient $e$ towards $v$ in $\mathcal{O}$ /* record burning direction */

10: **end for**

11: **end if**

12: **end for**

13: **if** no new vertices added to $B$ **then**

14: **return** $(S, \mathcal{O})$ /* $c$ is not superstable */

15: **end if**

16: **end while**

17: **return** $(\emptyset, \mathcal{O})$ /* $c$ is superstable */
In the package, Dhar's algorithm returns the orientation in the form of a CFOrientation object:

```python
from chipfiring import CFGraph, CFDivisor, DharAlgorithm

# Run Dhar's algorithm
dhar = DharAlgorithm(graph, divisor, "Alice")
unburntVertices, orientation = dhar.run()

# Examine the resulting orientation
# Note that the dict will omit any unoriented vertices
orientation_dict = orientation.to_dict()[orientations]
print(orientation_dict)
```

A CFOrientation object can also be initialized directly for experimentation as follows:

```python
# Edges between Alice and Bob are directed from Alice to Bob
# Edges between Bob and Charlie are directed from Bob to Charlie
# All other edges are unoriented
orientations = [('Alice', "Bob"), ("Bob", "Charlie")]
orientation = CFOrientation(graph, orientations)
```

The crucial facts linking orientations to winnability is the following. Proofs may be found in [5]. See also [2].

**Proposition 5.13.** ([5, Theorem 4.8]) Fix $q \in V$. Then, the correspondence $\mathcal{O} \mapsto c(\mathcal{O})$, is a bijection between acyclic orientations $\mathcal{O}$ of $G$, with unique source $q$, and maximal superstable configurations $c(\mathcal{O}) \in \text{Config}(G, q)$.

**Definition 5.14.** The *genus* of a graph is its topological Euler characteristic: $g = |E| - |V| + 1$.

The word *genus* is sometimes used for other notions in graph theory. Here, we define it in this way so that it mirrors the genus in the classical Riemann-Roch formula for algebraic curves. Alternatively, in the setup of [8] (for example), genus *g* algebraic curves may be specialized / tropicalized to genus *g* graphs.

**Proposition 5.15.** ([5, Corollary 4.9(1,2)]) Let *c* be a superstable configuration and *D* be a divisor. Then,

1. *c* is maximal if and only if $\deg(c) = g$.

2. *D* is maximal winnable if and only if its *q*-reduced form is *c* − *q*, with maximal superstable *c*.

**Proposition 5.16.** ([5, Corollary 4.9(3,4)]) Let *D* be a divisor on *G*.

1. The correspondence $\mathcal{O} \mapsto D(\mathcal{O})$ is a bijection between acyclic orientations of $G$ with unique source $q$ and maximal unwinnable $q$-reduced divisors of $G$.

2. If *D* is a maximal unwinnable divisor, then $\deg(D) = g - 1$. Thus, $\deg(D) \ge g$ implies *D* is winnable.

## 5.2 Rank

One of our winnability questions pertained to “Are some games more winnable than others?” One way to answer this is by defining the (Baker-Norine) *rank function*, which is central to proving the Riemann-Roch theorem for graphs and will lend us the ability to formalize further the answer to the question “How many chips can be removed for the divisor to remain still winnable?”

**Definition 5.17.** The *rank function* $r(D) : D \to \mathbb{Z}$ is defined as:

1. $r(D) = -1$ if and only if $|D| = 0$.

2. $r(D) \ge k$ for $k \ge 0$ if and only if the dollar game is winnable starting from all divisors obtained from *D* by removing *k* dollars.

3. $r(D) = k$ if and only if $r(D) \ge k$ and there exists an effective divisor *E* such that $\deg(E) = k + 1$ and $D - E$ is unwinnable.

It is worth restating that the problem of computing the rank of a general divisor on a general graph is **NP**-hard [9], which means the time it takes for an algorithm to compute the rank is non-polynomial. Specifically, this time grows exponentially with the size of the graph [5, §5.1]. So while rank can be computed in small or special cases, one should not expect our package’s rank function to scale well to large graphs in general.

**Corollary 5.18.** For divisors *D*, *D'* with $r(D)$, $r(D') \ge 0$, we have $r(D + D') \ge r(D) + r(D')$.
## 5.3 Riemann-Roch Theorem for Graphs

**Theorem 5.19.** (Riemann-Roch for graphs [2]). Let $D$ be a divisor on a (loopless, undirected) graph $G$ of genus $g = |E| - |V| + 1$ with canonical divisor $K$. Then,

$$r(D) - r(K - D) = 1 + \deg(D) - g.$$

The reader new to this story may enjoy trying to prove the following consequences of Riemann-Roch.

**Corollary 5.20.** A divisor $D$ is maximal unwinnable if and only if the divisor $K - D$ is maximal unwinnable.

**Theorem 5.21** (Clifford's Theorem, [2, Corollary 3.5] or [5, Corollary 5.13]). Suppose $D \in \mathrm{Div}(G)$ is a divisor with $r(D) \ge 0$ and $r(K - D) \ge 0$, then we have $r(D) \le \frac{1}{2} \deg(D)$.

We remark that, while Corollary 5.20 is an easy consequence of Riemann-Roch, in a sense that says the story backwards. Indeed, the original proof of Riemann-Roch in [2] deduces it as a consequence of this Corollary, which is first demonstrated with the aid of orientations; see the bottom of p. 15 of [2].

**Corollary 5.22.** Let $D \in \mathrm{Div}(G)$.

1. If $\deg(D) < 0$, then $r(D) = -1$.

2. If $0 \le \deg(D) \le 2g - 2$, then $r(D) \le \frac{1}{2} \deg(D)$.

3. If $\deg(D) > 2g - 2$, then $r(D) = \deg(D) - g$.

## 5.4 Computing rank in the package

Here's an illustration of our chipfiring package API for efficient rank calculation:

```python
from chipfiring import rank

# Compute the rank with optional optimizations
# Setting optimized=True enables the use of theoretical results (e.g., Corollary 4.23)
# to short-circuit expensive EWD calls when a shortcut applies.
# Note: While faster, this mode may not return intermediate structures
# like q-reduced divisors or orientations.
result = rank(divisor, optimized=True)

# Access the rank and logs
print("Rank:", resultrank)
print(result.get_log_summary())
```

## 5.5 Gonality

An interesting question arising from ranks of divisors is to determine the gonality of a given finite graph, or specific families of graphs. We briefly state the question here and show how to study it in our package. An excellent introduction to this subject is [6], from which we have chosen some worked examples below.

**Definition 5.23.** The gonality of a graph $G$ is the minimal degree of a divisor $D$ of rank at least 1.

An important open problem, motivated by algebraic geometry, is Baker's gonality conjecture [8, Conjecture 3.10(1)], which states that every graph of genus $g$ has gonality at most $\lfloor \frac{1}{2}g + \frac{3}{2} \rfloor$. Gonality is difficult to compute in general, especially for large graphs, but for small graphs it can be determined by exhaustive search. Such a search is implemented in `chipfiring.CFGonality`. For example, our package confirms the gonalities of platonic solid graphs, as reported in [6]. While this search take less than a few seconds for the tetrahedron, cube, and octahedron, the dodecahedron and tetrahedron take considerably more time, due to the number of divisors that must be considered. For example, the computation below took 10 minutes and 24 seconds on a Macbook Pro M2.

```python
# Compute the gonalities of Platonic solid graphs
from chipfiring import tetrahedron, cube, octahedron, dodecahedron, icosahedron,
    gonality

tetra = tetrahedron()  # K_4
```
```python
cube_graph = cube() # 3-regular, 8 vertices
octa = octahedron() # Complete tripartite K_{2,2,2}
dodec = dodecahedron() # 3-regular, 20 vertices
icos = icosahedron() # 5-regular, 12 vertices

print(gonality(tetra).gonality) # Output: 3
print(gonality(cube_graph).gonality) # Output: 4
print(gonality(octa).gonality) # Output: 4
print(gonality(dodec).gonality) # Output: 6
print(gonality(icos).gonality) # Output: 9
```

The reason that the word “gonality” must be written twice in each in the computations above is that gonality(G) returns an object that records not just the gonality computed, but a log of the computation and an example of a rank-1 divisor of minimum degree. For example, the command `D = gonality(tetra).winning_strategies[0]` will give a degree 3 divisor of rank 1 on the tetrahedron graph.

While the modules (`CFCombinatorics`, `CFGonality`, `CFGonalityDhar`, `CFPlatonicSolids`) are functional, they may be subject to future modifications as the underlying theory and implementation continue to develop.

## 5.6 An extended example: gonalities of chains of loops

As an example of a more intensive computation that our package makes possible, we give below a longer example of a graph that has attracted considerable interest in divisor theory of graphs: the chain of loops (or chains of cycles). Such graphs first gained attention in [10], where it was shown that, if chosen sufficiently generically, they are “Brill–Noether general;” among other this means that their gonality is exactly $\lfloor \frac{1}{2}g + \frac{3}{2} \rfloor$. Later, the third author developed tools in [11] that suffice to determine ranks of all divisors on all chains of loops. Later, Jensen and Sawyer [12] used these tools to classify the gonalities of all chains of cycles.

The code below shows how to use the `chipfiring` package to verify the Jensen-Sawyer classification of gonalities of chains of cycles. For simplicity and to limit the number of cases, we investigate the following special case.

**Example 5.24.** Consider a genus 5 chain of cycles of the following form. G consists of 5 cycles, where the nth cycle consists of $m_n$ vertices $z_{n,0}, \dots, z_{n,m_n-1}$ arranged in a cycle, and there is a single edge from each cycle to the next, joining $z_{n,0}$ to $z_{n+1,m_n+1-1}$. The numbers $m_1, \dots, m_5$ are called the cycle lengths or torsion orders. According to the classification in [12], the gonality of this graph is

$$ \operatorname{gon}(G) = \begin{cases} 2 & \text{if } m_2 = m_3 = m_4 = 2, \\ 3 & \text{if } \operatorname{gon}(G) \neq 2 \text{ and } m_2 = 2, m_3 = 3, \text{ or } m_4 = 2, \\ 4 & \text{otherwise.} \end{cases} $$

The following code demonstrates how to use our package to build a chain of cycles of this kind, compute its gonality, and verify that it accords with the classification of Jensen and Sawyer. In order to reduce to finitely many cases, we limit all cycle lengths to 2, 3, 4, or 5.

```python
from chipfiring import CFGraph
from chipfiring import gonality
import itertools

def chain(cycle_lengthths: list[int]):
    if not all(isinstance(l, int) and l >= 2 for l in cycle_lengthths):
        raise ValueError("All cycle lengths must be integers greater than or equal to
                          2.")
    vertices = {f"z_{i+1}_{j}" for i, l in enumerate(cycle_lengthths) for j in range(1)}
    # edges = [(f"z_{i+1}_{j}", f"z_{i+1}_{j+1}") for i, j in enumerate(cycle_lengthths) for j in range(1)]
    edges = []
    for i, l in enumerate(cycle_lengthths):
        if l == 2:
            edges.append((f"z_{i+1}_0", f"z_{i+1}_1", 2))
        else:
            for j in range(1):
                edges.append((f"z_{i+1}_{j}", f"z_{i+1}_{j+1}", 1))
```
```python
for i, l in enumerate(cycle_lengthols):
    if i == 0: continue
    edges.append((f"z_{i}_0", f"z_{i+1}_{1-1}", 1))
    return CFGraph(vertices, edges)

def expectedGonality(cycle_lengthols: list[int]) -> int:
    if not all(isinstance(l, int) and l >= 2 for l in cycle_lengthols):
        raise ValueError("All cycle lengths must be integers greater than or equal to
                          2.")
    if cycle_lengthols[1] == 2 and cycle_lengthols[2] == 2 and cycle_lengthols[3] == 2:
        return 2
    elif cycle_lengthols[1] == 2 or cycle_lengthols[2] == 3 or cycle_lengthols[3] == 2:
        return 3
    else:
        return 4

lengthes = [2, 3, 4, 5]

for cycle_lengthols in itertools product(lengthChoices, repeat=5):
    cycle_lengthols = list(cycle_lengthols)
    G = chain(cycle_lengthols)
    expected = expectedGonality(cycle_lengthols)
    computed = gonality(G).gonality
    print(cycle_lengthols, f"Expected: {expected}", f"Computed: {computed}", expected ==
          computed)
```

As one would hope, the output of this code consists of 1024 lines, one for each choice of cycle lengths, confirming that our package computed the same gonality as that predicted by theoretical means. This computation is expensive, since it requires a considerable exhaustive search. On a Macbook Pro M2, this computation was completed in 167 minutes and 14 seconds.

# 6 Conclusion and Future Directions

This paper introduces the chipfiring Python package, a dedicated computational toolkit designed explicitly for the mathematical analysis of chip-firing games on multigraphs. We have developed specialized data structures, algorithms, and theoretical frameworks useful for exploration and experimentation within this domain.

Key contributions of the chipfiring package include specialized object-oriented classes such as CFGraph, CFDivisor, CFLaplacian, CFOrientation, CFConfig, CFiringScript, and CFDataProcessor tailored specifically for chip-firing dynamics. Algorithmically, we have implemented efficient methodologies such as Dhar's burning algorithm (CFDhar), the Greedy algorithm (CFGreedyAlgorithm), and rank calculation techniques (CFRank). These tools collectively also facilitate rapid and precise analyses of winnability (EWD, is_winnable), linear equivalence (linear equivalence), and q-reduction (q_reduction, is_q_reduced). Furthermore, comprehensive documentation, intuitive APIs, and interactive visualization modules (CFVisualizer) augment the educational and research applicability of the package, making it accessible to a broad audience.

## 6.1 Current Scope and Limitations

The current scope of the chipfiring package focuses primarily on finite, undirected multigraphs without loops, supporting fundamental mathematical operations pertinent to chip-firing theory. While extensive, our current implementation is optimized primarily for standard scenarios encountered frequently in graph theory, algebraic geometry, and combinatorial optimization contexts. Presently, the package's computational complexity allows efficient analyses on medium-sized graphs but faces scalability challenges when handling extremely large-scale systems, highlighting an area ripe for future optimization.

Moreover, the package currently does not fully integrate advanced symbolic computation tools, limiting exact arithmetic operations. The visualization functionalities provided are adequate for typical educational and research needs but could be further enhanced to represent more complex and dynamic chip-firing processes clearly.
## 6.2 Future Directions

Several exciting avenues exist for future development and enhancement of the chipfiring package. One promising direction is the extension to more general classes of graphs, including directed, weighted, and loop-containing variants, which would greatly broaden the package's applicability and research scope. Furthermore, incorporating symbolic computation capabilities and sandpile models [13] could significantly enhance mathematical rigor and exactness, particularly valuable in theoretical explorations requiring precise arithmetic operations.

Additionally, performance optimization using parallel computing techniques, GPU acceleration, and efficient sparse matrix computations would greatly enhance scalability and facilitate the handling of larger and more complex graphs.

On the theoretical front, integrating more extensive modules supporting ongoing research in graph theory, including divisor specialization, Brill-Noether theory [10, 14], and advanced combinatorial bounds [15] will keep the package relevant to current research topics.

## 6.3 Community Engagement and Availability

The chipfiring package is actively maintained and openly available to the mathematical and computational community. We strongly encourage community engagement through feedback, contributions, and feature requests via the project's GitHub repository. This package is licensed under the permissive MIT License.

# 7 Acknowledgments

We thank Ralph Morrison for feedback and guidance. Special thanks to the Amherst College Department of Mathematics for supporting this research project. We also acknowledge the influence of existing mathematical software packages (i.e. numpy, networkx, matplotlib, pandas, dash) that inspired our approach to specialized scientific computing tools. Portions of the code were developed with the assistance of AI coding tools, including Cursor with Gemini 2.5 Pro, Claude 3.5 Sonnet, and Claude 3.7 Sonnet.

## References

[1] Deepak Dhar. Self-organized critical state of sandpile automaton models. *Physical review letters*, 64(14):1613–1616, 1990. 1, 12

[2] Matthew Baker and Serguei Norine. Riemann–Roch and Abel–Jacobi theory on a finite graph. *Advances in Mathematics*, 215(2):766–788, 2007. 1, 8, 15, 17, 18

[3] Aric Hagberg, Pieter Swart, and Daniel S Chult. Exploring network structure, dynamics, and function using NetworkX. In *Proceedings of the 7th Python in Science Conference*, volume 836, pages 11–15, 2008. 2

[4] Dhyey Dharmendrakumar Mavani. Lean4 machine assisted proof framework for chip firing game & graphical Riemann–Roch, April 2025. https://dhyeymavani.com/publication/math-thesis-lean/math-thesis-lean.pdf. 2

[5] Scott Corry and David Perkinson. Divisors and sandpiles: an introduction to chip-firing. *American Mathematical Society*, 2018. 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 16, 17, 18

[6] Marchelle Beougher, Kexin Ding, Max Everett, Robin Huang, Chan Lee, Ralph Morrison, and Ben Weber. Chip-firing on the platonic solids: a primer for studying graph theory. 07 2024. 2, 3, 18

[7] Norman Biggs. Chip-firing and the critical group of a graph. *Journal of Algebraic Combinatorics*, 9(1):25–45, 1999. 8

[8] Matthew Baker. Specialization of linear systems from curves to graphs. *Algebra Number Theory*, 2(6):613–653, 2008. With an appendix by Brian Conrad. 16, 17, 18

[9] V. Kiss and L. Tóthmérész. Chip-firing games on eulerian digraphs and NP-hardness of computing the rank of a divisor on a graph. *Discrete Applied Mathematics*, 193:48–56, 2015. 17

[10] F. Cools, J. Draisma, S. Payne, and E. Robeva. A tropical proof of the Brill–Noether theorem. *Advances in Mathematics*, 230:759–776, 2012. 19, 21
[11] Nathan Pflueger. Special divisors on marked chains of cycles. *J. Combin. Theory Ser. A*, 150:182–207, 2017. 19

[12] David Jensen and Kalila Lehmann. Scrollar invariants of tropical curves. arxiv:2001.02710, 2024. 19

[13] David Perkinson, Jacob Perlman, and John Wilmes. Primer for the algebraic geometry of sandpiles, 2011. 21

[14] N. Pflueger. Brill–Noether varieties of k-gonal curves. *Advances in Mathematics*, 312:46–63, 2017. 21

[15] B. Osserman. Limit linear series and the Amini-Baker construction. *arXiv preprint arXiv:1707.03845*, 2017. 21
# Appendices

## A Data Import Format

### A.1 JSON Import Formats

#### A.1.1 Graph (CFGraph)

```json
{
  "vertices": ["vertex1", "vertex2", "vertex3"],
  "edges": [
    ["vertex1", "vertex2", valence],
    ["vertex2", "vertex3", valence]
  ]
}
```

* **vertices**: Array of vertex names (strings)

* **edges**: Array of [source, target, valence] tuples where valence is a positive integer

#### A.1.2 Divisor (CFDivisor)

```json
{
  "graph": {
    "vertices": ["vertex1", "vertex2"],
    "edges": [["vertex1", "vertex2", 1]]
  },
  "degrees": {
    "vertex1": 2,
    "vertex2": -1
  }
}
```

* **graph**: Graph object with vertices and edges structure

* **degrees**: Object mapping vertex names to integer degrees (can be negative)

#### A.1.3 Orientation (CFOrientation)

```json
{
  "graph": {
    "vertices": ["vertex1", "vertex2"],
    "edges": [["vertex1", "vertex2", 1]]
  },
  "orientations": [
    ["source", "sink"],
    ["vertex1", "vertex2"]
  ]
}
```

* **graph**: Graph object with vertices and edges structure

* **orientations**: Array of [source, sink] pairs defining edge directions
### A.1.4 Firing Script (CFiringScript)

```json
{
    "graph": {
        "vertices": ["vertex1", "vertex2"],
        "edges": [["vertex1", "vertex2", 1]]
    },
    "script": {
        "vertex1": 3,
        "vertex2": 0
    }
}
```

* **graph**: Graph object with vertices and edges structure

* **script**: Object mapping vertex names to firing counts (non-negative integers)

## A.2 TXT Import Formats

### A.2.1 Graph (CFGraph)

```
VERTICES: vertex1, vertex2, vertex3
EDGE: vertex1, vertex2, valence
EDGE: vertex2, vertex3, valence
```

* **VERTICES**: Comma-separated list of vertex names

* **EDGE**: Format `source, target, valence` where valence is a positive integer

### A.2.2 Divisor (CFDivisor)

```
GRAPH_VERTICES: vertex1, vertex2, vertex3
GRAPH EDGE: vertex1, vertex2, valence
GRAPH EDGE: vertex2, vertex3, valence
---DEGREES---
DEGREE: vertex1, degree_value
DEGREE: vertex2, degree_value
```

* **GRAPH_VERTICES**: Comma-separated list of vertex names

* **GRAPH EDGE**: Format `source, target, valence`

* **---DEGREES---**: Separator line

* **DEGREE**: Format `vertex_name, degree_value` (degree can be negative)

### A.2.3 Orientation (CFOrientation)

```
GRAPH_VERTICES: vertex1, vertex2, vertex3
GRAPH EDGE: vertex1, vertex2, valence
GRAPH EDGE: vertex2, vertex3, valence
---ORIENTATIONS---
ORIENTED: source, sink
ORIENTED: vertex1, vertex2
```

* **GRAPH_VERTICES**: Comma-separated list of vertex names

* **GRAPH EDGE**: Format `source, target, valence`

* **---ORIENTATIONS---**: Separator line

* **ORIENTED**: Format `source, sink` defining edge direction
### A.2.4 Firing Script (CFiringScript)

GRAPH_VERTICES: vertex1, vertex2, vertex3
GRAPH EDGE: vertex1, vertex2, valence
GRAPH EDGE: vertex2, vertex3, valence
---SCRIPT---
FIRING: vertex_name, firing_count
FIRING: vertex1, 3

* **GRAPH_VERTICES**: Comma-separated list of vertex names

* **GRAPH EDGE**: Format source, target, valence

* **---SCRIPT---**: Separator line

* **FIRING**: Format vertex_name, firing_count (non-negative integer)