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 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)

Source distribution for pypebbling 0.1.1
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)

Table of built distributions (wheels) for pypebbling 0.1.1
File Interpreter ABI Platform Actions
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.

Release history Release notifications | RSS feed

This release

0.1.1 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