pypebbling
Exact tools for graph pebbling: reachability, solvability and minimality of pebble distributions, with move sequences anyone can replay.
A pebbling move removes two pebbles from a vertex and puts one pebble on a neighbouring vertex. A distribution is solvable if every vertex can receive a pebble by some sequence of moves. The optimal pebbling number of a graph is the smallest number of pebbles in a solvable distribution.
Install
pip install pypebbling
The package is imported as pebbling. It needs Python 3.12 or later and installs OR-Tools.
Example
from pebbling.graphs import grid_graph
from pebbling.solver import solvability
from pebbling.certify import replay
G = grid_graph(5, 5)
P = [0] * 25
for r, c in [(1, 1), (1, 3), (3, 1), (3, 3)]:
P[r * 5 + c] = 4
solvable, certs, _ = solvability(G, tuple(P))
print("solvable:", solvable)
moves = certs[0] # vertex (0, 0); vertex v is (v // 5, v % 5)
print("moves to (0, 0):", [(divmod(u, 5), divmod(w, 5)) for u, w in moves])
print("replay ok:", replay(G.adj, P, moves, 0))
What is inside
pebbling.solver: exact backward search over demands, with exact integer potentials for pruning.pebbling.ipsolver: a second exact engine, an integer flow model solved with CP-SAT.pebbling.certify: replays move sequences.naivecheck: an independent naive checker, written separately from the solver.
Source code, proofs of correctness, the validation suite and a counterexample to a conjecture of Petr, Portier and Stolarczyk are at https://github.com/hynoph/pebbling.
License
MIT
Metadata
Release files for pypebbling 0.1.1
For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.
Source distribution (sdist)
| File | Size | Uploaded | Provenance | Actions |
|---|---|---|---|---|
| pypebbling-0.1.1.tar.gz | 13.7 kB | Without provenance | Details for pypebbling-0.1.1.tar.gz |
Built distribution (wheel)
| File | Interpreter | ABI | Platform | Actions Reset |
|---|---|---|---|---|
| pypebbling-0.1.1-py3-none-any.whl | Python 3 | none | any | Details for pypebbling-0.1.1-py3-none-any.whl |
Total release size: 29.9 kB
Release files / pypebbling-0.1.1.tar.gz
| Download URL | pypebbling-0.1.1.tar.gz |
|---|---|
| Size | 13.7 kB |
| Tags | Source |
|
SHA-256 checksum How to use checksums |
b3a919932a7a51607520a800f3b29d68c98a0bd9084497d445204336fe69edef
|
|
BLAKE2b-256 checksum How to use checksums |
8d2c527eda994e19c8320db7665eea5015116c9cd1a1c471c30b7c9407d5c4bc
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/7.0.0 CPython/3.12.10
|
Release files / pypebbling-0.1.1-py3-none-any.whl
| Download URL | pypebbling-0.1.1-py3-none-any.whl |
|---|---|
| Size | 16.2 kB |
| Tags | Python 3 |
|
SHA-256 checksum How to use checksums |
1b8f95eac1bd2ccff4a024232a4b5b5e446c1a50a06a8914f31980db36a61080
|
|
BLAKE2b-256 checksum How to use checksums |
ce3498f39203fe74984748a81a90bd0183510a18ed7032917c15be7bd1ea3d37
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/7.0.0 CPython/3.12.10
|
Security for pypebbling 0.1.1
Provenance
Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.
No provenance found
None of the files in this release were uploaded with provenance metadata.
A note on package security
PyPI is a repository for distributing packages, not a service for auditing them. While third-party security researchers and our staff do their best to detect and remove malicious packages, PyPI cannot guarantee the quality, security or suitability of any given package.
To learn more about protecting yourself from malicious actors, visit our package security documentation.