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

• Dhar’s algorithm for efficient winnability determination

• Visualization tools for graphs and game states

• Comprehensive type hints and documentation

Installation

You can install the chipfiring package directly 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

Usage guidelines are included within the API documentation. For more examples and full-analysis workflows, check out the examples directory in the GitHubrepository.