Library for studying Cayley graphs and Schreier coset graphs.
This is a library for studying Schreier coset graphs and Caley graphs.
This what we plan to support:
- BFS from given state (growth function, adjacency matrix, last layers).
- Efficient path finding (beam search).
- Random walk generation.
- Library of graphs and generators (LRX, TopSpin, Rubik Cubes, wreath, globe etc., see here).
- Efficient computing on CPU, GPU, TPU (with JAX), usable on Kaggle.
- Library of datasets with solutions to some problems (e.g. growth functions like here).
See this demo Kaggle notebook for examples on how this library can be used.
To start development, run:
git clone https://github.com/cayleypy/cayleypy.git
cd cayleypy
pip install -r requirements.txt
pip install -r requirements-dev.txt
To run only quick tests:
FAST=1 pytest
Before commiting, run these checks:
./lint.sh
pytest
To check coverage, run:
coverage run -m pytest && coverage html
The initial code for this library is based on cayleypy by Ivan Koltsov, which is itself based on code by Alexander Chervov and Kirill Khoruzhii.
Also, code from the following Kaggle notebooks was used:
- https://www.kaggle.com/code/ivankolt/generation-of-incidence-mtx-pancake (advanced BFS).
- https://www.kaggle.com/code/avm888/cayleypy-growth-function.
- https://www.kaggle.com/code/avm888/jax-version-cayleypy (how to use JAX).
- https://www.kaggle.com/code/fedimser/bfs-for-binary-string-permutations (bit operations).
- https://www.kaggle.com/code/ivankolt/lrx-4bit-uint64?scriptVersionId=221435319 (fast BFS)