Metadata-Version: 2.4
Name: pypebbling
Version: 0.1.1
Summary: Exact pebbling reachability and solvability on graphs, with replayable move certificates and an independent checker
Author: Eric Lee
License-Expression: MIT
Project-URL: Repository, https://github.com/hynoph/pebbling
Requires-Python: >=3.12
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: ortools>=9.15
Provides-Extra: test
Requires-Dist: pytest>=8.4; extra == "test"
Dynamic: license-file

# 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

```bash
pip install pypebbling
```

The package is imported as `pebbling`. It needs Python 3.12 or later and installs OR-Tools.

## Example

```python
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
