raven-csp 0.1.0

Centralized and distributed CSP framework (CSP/DCSP)

CSP / DCSP Framework

A Python framework for centralized and distributed constraint satisfaction:

• csp/: core CSP modeling, propagation, search, encoding, benchmark definitions
• dcsp/: distributed architectures and algorithms (variable-agent and constraint-agent models)

The framework is designed so you can model once and solve either centrally or distributed with minimal API changes.

---

Table of Contents

1. Feature Overview
2. Repository Structure
3. Installation
4. Import Cheat Sheet (what to import for what)
5. Central CSP Workflows
6. Distributed CSP Workflows
7. Tree-based / Constraint-Agent Mapping Workflow
8. Graph Export and Visualization
9. Benchmarks
10. Testing and Verification
11. Documentation Website (MkDocs + GitHub Pages)
12. Contributing

---

1) Feature Overview

Central CSP (csp)

• CSP modeling (CSP, variables, constraints)
• Propagation: gac, vlac
• Search: bt, fc, mac, mc (+ aliases/suffix forms)
• Optional binarization support: dual, hidden, double
• Built-in benchmark registry (csp.benchmarks)

Distributed CSP (dcsp)

• Architectures:
  • variable-agent (variable, var, one-var)
  • constraint-agent (constraint, cons)
• Distributed propagation:
  • dgac (distributed-gac, distributed_gac)
• Distributed search:
  • sbt, abt, awcs, afc, dba, dsa, aas, compapo
• Constraint-agent utilities:
  • assignment validation
  • pseudo-tree assignment generation

---

2) Repository Structure

csp/                    # Centralized CSP package
  api.py                # run_propagation, run_search, print_result
  core.py               # CSP data model
  solvers.py            # search backends
  propagation.py        # GAC
  propagation_vlac.py   # VLAC
  encodings.py          # dual/hidden/double encoding
  benchmarks.py         # benchmark registry + factories

dcsp/                   # Distributed CSP package
  api.py                # run_distributed_search/propagation
  architectures/        # agent-model builders
  algorithms/           # distributed algorithms
  propagation.py        # DGAC implementation
  mapping.py            # model mapping helpers

main.py                 # Comment-first usage guide (all calls disabled)
README.md               # This document
docs/                   # MkDocs documentation source
tests/                  # Unit tests
mkdocs.yml              # MkDocs site config

---

3) Installation

Use Python 3.10+.

python -m venv .venv
source .venv/bin/activate  # Windows: .venv\Scripts\activate
python -m pip install -U pip

Optional dependencies by feature:

• sympy → required for VLAC symbolic processing
• numpy → required by constraints that use np.* (e.g. some engineering constraints)
• networkx + matplotlib → graph export/visualization
• pytest (optional) or built-in unittest for tests
• mkdocs + mkdocs-material for docs site

---

4) Import Cheat Sheet (what to import for what)

4.1 Minimal central CSP solving

from csp.core import CSP
from csp.api import run_search, print_result

4.2 Central propagation

from csp.core import CSP
from csp.api import run_propagation, print_result

4.3 Binarization support

from csp import binarize_csp

4.4 Benchmark loading

from csp import benchmarks

4.5 Distributed search (CSP or prebuilt model)

from dcsp.api import run_distributed_search
from csp.api import print_result

4.6 Distributed propagation (DGAC)

from dcsp.api import run_distributed_propagation
from csp.api import print_result

4.7 Constraint-agent model building and mapping helpers

from dcsp import (
    build_constraint_agent_model,
    validate_constraint_assignment,
    build_pseudotree_constraint_assignment,
)

4.8 Graph export / visualization

from csp.core import CSP
# then use csp.to_graph(), csp.visualize_graph(...)

---

5) Central CSP Workflows

5.1 Build a model manually

from csp.core import CSP

csp = CSP()
csp.add_variable("x", {1, 2, 3})
csp.add_variable("y", {1, 2, 3})
csp.add_constraint("c1", "x < y")

5.2 Run propagation

from csp.api import run_propagation, print_result

pr = run_propagation("gac", csp)
print_result(pr)

if pr.ok:
    csp_reduced = pr.reduced_csp
else:
    csp_reduced = csp

Supported run_propagation algorithms:

• gac (aliases: ac, ac3, arc)
• vlac

5.3 Run search

from csp.api import run_search, print_result

sr = run_search(
    "mac-gac",
    csp,
    deterministic=True,
    heuristics=["mrv", "lcv"],
    find_all_solutions=False,
)
print_result(sr)

Supported run_search algorithms:

• bt / backtracking
• fc / forward-checking / forward_checking
• mac / maintaining-arc-consistency / maintaining_arc_consistency
• mc / min-conflicts / minconflicts
• suffix variants: fc-gac, fc-vlac, mac-gac, mac-vlac

Important options:

• deterministic: deterministic tie-break/order behavior
• heuristics: mrv, degree, lcv, shuffle_variable, shuffle_values
• find_all / find_all_solutions
• max_solutions
• propagation (gac/vlac for FC/MAC)
• decode_solutions, keep_aux_vars (for binarized CSPs)

---

6) Distributed CSP Workflows

6.1 Distributed search from raw CSP

from csp.core import CSP
from dcsp.api import run_distributed_search
from csp.api import print_result

csp = CSP()
csp.add_variable("x", {1, 2, 3})
csp.add_variable("y", {1, 2, 3})
csp.add_constraint("c1", "x != y")

res = run_distributed_search(
    "abt",
    csp,
    architecture="variable",
    max_delay=3,
    random_seed=0,
    deterministic_init=True,
)
print_result(res)

6.2 Distributed search from prebuilt model

from dcsp import build_constraint_agent_model
from dcsp.api import run_distributed_search

assignment = [("c1",)]
model = build_constraint_agent_model(csp, assignment=assignment)

res = run_distributed_search("aas", model, runtime="mp", max_events=400_000)

Supported distributed algorithms (and aliases):

• SBT: sbt, sync, synchronous
• ABT: abt, async
• AWCS: awcs, weak, weak-commitment
• AFC: afc, forward, asynchronous-forward-checking
• DBA: dba, breakout, distributed-breakout
• DSA: dsa, stochastic, distributed-stochastic
• AAS: aas, asynchronous-aggregation
• CompAPO: compapo, apo, mediation

Key options:

• architecture, architecture_kwargs (if input is raw CSP)
• max_delay, max_events, random_seed
• deterministic_init
• runtime: sim or mp
• find_all_solutions, max_solutions
• record_protocol, protocol_path

---

7) Tree-based / Constraint-Agent Mapping Workflow

Use this when you want constraint-agent decomposition (including tree-style workflows):

from dcsp import (
    build_pseudotree_constraint_assignment,
    validate_constraint_assignment,
    build_constraint_agent_model,
)

assignment = build_pseudotree_constraint_assignment(csp, bundle_size=None)
validate_constraint_assignment(csp, assignment)
model = build_constraint_agent_model(csp, assignment=assignment)

bundle_size behavior:

• None → automatic low-coupling grouping (non-uniform group sizes possible)
• 1 → one constraint per agent
• >1 → fixed chunk size in DFS order

---

8) Graph Export and Visualization

from csp.core import CSP

# ... build csp ...
g = csp.to_graph()
ax = csp.visualize_graph(layout="bipartite", show=False)

visualize_graph(...) options include:

• layout: spring, bipartite, kamada_kawai, circular
• with_labels, node_size, font_size
• variable_color, constraint_color, edge_color
• figsize, show

---

9) Benchmarks

Load by name:

from csp import benchmarks
spec = benchmarks.load(["send_more_money_single"])[0]
csp = spec.factory()

Available built-ins include:

• send_more_money_single
• send_more_money_carries
• sudoku_binary
• sudoku_product
• warehouse_location
• manufacturbility_problem (translated engineering benchmark)

---

10) Testing and Verification

Run unit tests:

python -m unittest discover -s tests -p "test_*.py" -v

Run bytecode checks:

python -m compileall csp dcsp tests main.py

Current tests cover:

• benchmark registration/build
• run_search alias behavior and max_solutions
• mapping consistency and validation
• DGAC incomplete vs quiescent termination diagnostics
• safe-eval support for round(...)

---

11) Documentation Website (MkDocs + GitHub Pages)

This repo includes full docs in docs/ with mkdocs.yml.

Local preview:

python -m pip install mkdocs mkdocs-material
mkdocs serve

Static build:

mkdocs build

GitHub Pages deployment:

• workflow file: .github/workflows/docs.yml
• action builds MkDocs and publishes site/

Update site_url and repo_url in mkdocs.yml to your real GitHub org/repo.

---

12) Contributing

• Keep public APIs backward compatible where feasible.
• Add/update tests with behavior changes.
• Keep docs and comments in English.
• Prefer deterministic settings in examples for reproducibility.

13) Publish to PyPI (pip install ready)

This repository is now structured for PEP 517/518 packaging via pyproject.toml.

13.1 Build distributions locally

python -m pip install --upgrade build twine
python -m build

Artifacts are generated in dist/ (.whl and .tar.gz).

13.2 Validate package metadata and files

python -m twine check dist/*

13.3 Upload to TestPyPI first (recommended)

python -m twine upload --repository testpypi dist/*

Then verify installation:

python -m pip install --index-url https://test.pypi.org/simple/ raven-csp

13.4 Upload to PyPI

python -m twine upload dist/*

13.5 What else you need before first release

1. Create PyPI and TestPyPI accounts.
2. Generate API tokens and store them securely (~/.pypirc or CI secrets).
3. Replace placeholder URLs in pyproject.toml:
   • Homepage
   • Documentation
   • Repository
   • Issues
4. Tag a release in Git (v0.1.0, etc.).
5. Optionally add CI publish workflow (GitHub Actions) that publishes on tags.

13.6 Optional dependency installs for users

pip install raven-csp[all]
pip install raven-csp[vlac]
pip install raven-csp[graph]
pip install raven-csp[engineering]