Chip-Firing Game

A Python package for the chip-firing games (i.e. the dollar game, the gonality game, etc.) on graphs, with a focus on mathematical properties and algorithms.

Overview

The chip-firing game is a mathematical model that can be used to study various phenomena in graph theory, algebraic geometry, and other areas of mathematics.

In the dollar game variant, we consider a graph where:

• Vertices represent people

• Edges represent relationships between people

• Each vertex has an integer value representing wealth (negative values indicate debt)

• Players can perform lending/borrowing moves by sending money across edges

The goal is to find a sequence of moves that makes everyone debt-free. If such a sequence exists, the game is said to be winnable.

Features

• Mathematical graph implementation with support for multigraphs

• Divisor class with operations for lending and borrowing

• Laplacian matrix computations

• Linear equivalence checking

• Set-firing moves

• Non-mutating winnability predicates and q-reduction with an explicit source

• Baker-Norine rank and graph gonality helpers

• Dhar’s burning algorithm and graph orientations

• Visualization tools for graphs and game states

• Type hints and API documentation

Installation

Python 3.8 or newer is required. Install the package from PyPI using pip:

pip install chipfiring

Note: the most up-to-date version of the package can be found at https://pypi.org/project/chipfiring/.

Contents

Documentation

• Contributing
  • Development Setup
  • Running Tests
  • Building Documentation
  • Code Style
  • Pull Requests
  • Issues and Feature Requests
  • Code of Conduct
• API Documentation
  • Graph Module
  • Divisor Module
  • Laplacian Module
  • Configuration Module
  • Orientation Module
  • Firing Script Module
  • Algorithm Module
  • Greedy Algorithm Module
  • Dhar Algorithm Module
  • Rank Module
  • Visualize Module
  • Data Processor Module
  • Gonality Game Module

API Documentation

The complete API documentation for the chipfiring package can be found in the API Documentation section.

Basic Usage

from chipfiring import CFDivisor, CFGraph, is_winnable, q_reduction

graph = CFGraph({"q", "a", "b"}, [("q", "a", 1), ("a", "b", 1)])
divisor = CFDivisor(graph, [("q", 1), ("a", 0), ("b", -1)])

print(is_winnable(divisor))
reduced = q_reduction(divisor, q_name="q")
print(reduced.degrees_to_str())

The input divisor is unchanged by these helpers. Usage details are included in the API documentation. For complete workflows, see the examples directory.