Skip to main content

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 in the repository linked on this page.

License

MIT

Metadata

Release files for pypebbling 0.1.0

For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.

Source distribution (sdist)

Source distribution for pypebbling 0.1.0
File Size Uploaded Provenance Actions
pypebbling-0.1.0.tar.gz 13.7 kB Without provenance Details for pypebbling-0.1.0.tar.gz

Built distribution (wheel)

Table of built distributions (wheels) for pypebbling 0.1.0
File Interpreter ABI Platform Actions
pypebbling-0.1.0-py3-none-any.whl Python 3 none any Details for pypebbling-0.1.0-py3-none-any.whl

Total release size: 29.8 kB

Release files / pypebbling-0.1.0.tar.gz

Download URL pypebbling-0.1.0.tar.gz
Size 13.7 kB
Tags Source
SHA-256 checksum
How to use checksums
1497a1af83c2464f3e3f0c6b70abb86ca727a4483bf5bc10287bbe84974d09ae
BLAKE2b-256 checksum
How to use checksums
bc208bda3b53bb9da4a1a09bd429076a37a3ff49a13d2b2349ac68bd8ff54f96
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.0-py3-none-any.whl

Download URL pypebbling-0.1.0-py3-none-any.whl
Size 16.2 kB
Tags Python 3
SHA-256 checksum
How to use checksums
3b739d4b98ef1778f15ddf69889e3772bafd3bf422874bdacc43e38bdafd1aba
BLAKE2b-256 checksum
How to use checksums
40f5afbc6f787131d7d6ca03df988ad6c6743dcca472fb27b06437ec7a64a8d2
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.0

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.

Release history Release notifications | RSS feed

This release

0.1.0 This release

2 release files No provenance

Anthropic, PBC Visionary sponsor Bloomberg Visionary sponsor Hudson River Trading Visionary sponsor Meta Visionary sponsor NVIDIA Visionary sponsor Microsoft Sustainability sponsor Depot Continuous Integration AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Sentry Error logging StatusPage Status page