Alpha release · PyPI package coming soon

Better graph solutions,
one local Δ at a time.

An alpha-stage Python framework for heuristic subgraph extraction. Define reward, penalty, and feasibility once; DeltaSearch handles candidate moves, rollback, and search budgets.

Read the docs View the source
  • Python 3.10+
  • stdlib core
  • MIT licensed
  • typed API
  • alpha · local install
  • 6
    NP-hard problems
  • 8
    solver strategies
  • 380+
    tests in CI
  • 80%
    coverage enforced
  • 0
    core dependencies
  • local
    delta per move
Overview

A single engine for six NP-hard problems

Turn a graph objective into a small, testable problem contract. DeltaSearch owns the search loop while your code defines domain rules, feasibility, and what a good move means.

One framework, many problems

Maximum Planar Subgraph, Connected Dominating Set, Independent Set, Prize Collecting Vertex Cover, Facility Location, Steiner Tree — monotone and non-monotone alike. Same interface, six realizations.

General purpose

Local deltas

Candidate scoring stays local instead of recomputing the objective from scratch. Reversible actions make the search loop inspectable.

Incremental · reversible

Easy to inspect

Typed interfaces, explicit budgets, observers, thread-safe graph access, and a standard-library core make experiments easier to reproduce.

Typed · Observable · Alpha
Framework

Five steps from input graph to answer

A tiny protocol, a greedy core, and pluggable solvers. Define your own problem in a handful of methods, or reach for a built-in one.

  1. Seed

    evaluate_initial_state builds a starting subgraph.

  2. Enumerate

    enumerate_actions lists candidate add/remove moves.

  3. Score

    calculate_delta scores a candidate from local context.

  4. Commit · Undo

    apply_action or undo_action, always reversible.

  5. Converge

    Stop on budget, stall, or objective target.

In practice

A real run, shown at readable scale

  • This is a real Maximum Planar Subgraph solve rendered from the repository’s demo generator — not a decorative mockup.
  • 62 nodes · 229 candidate edges. The solver keeps adding edges while an incremental Euler-bound filter screens each candidate move.
  • It reaches the Euler upper bound: 3V − 6 = 180 edges. That is a useful bound for simple planar graphs, not a proof of planarity.
  • Each candidate uses an incremental delta instead of recomputing the objective from scratch at every iteration.
✓ 3V − 6 Euler bound reached · representative view · GreedySolver
Built-in problems

The classics, covered out of the box

Each problem is a fleshed-out SubgraphExtractionProblem — instantiate it on a Graph, hand it to a solver, done.

Monotone

Maximum Planar Subgraph

MaximumPlanarSubgraphProblem

Keep as many edges as possible while screening candidates against an Euler-bound feasibility rule.

Monotone

Minimum Connected Dominating Set

MinimumConnectedDominatingSetProblem

The smallest connected vertex set that dominates the whole graph.

Monotone

Maximum Weight Independent Set

MaximumWeightedIndependentSetProblem

The heaviest set of mutually non-adjacent vertices.

Non-monotone

Prize Collecting Vertex Cover

PrizeCollectingVertexCoverProblem

Balance vertex cost against uncovered-edge penalties, collecting prizes.

Non-monotone

Uncapacitated Facility Location

UncapacitatedFacilityLocationProblem

Where to open facilities to serve demand at the lowest total cost.

Non-monotone

Minimum Weighted Steiner Tree

MinimumWeightedSteinerTreeProblem

Connect a set of terminals through optional nodes at minimum edge cost.

Performance

Understand the search as it runs.

Local deltas

Each move is scored from local context via calculate_delta, not a full graph re-evaluation.

Undo-stack rollback

Every mutation is logged in an undo stack. Backtracking restores prior state without re-scoring.

Thread-safe access

ThreadSafeGraph protects mutations and explicit snapshots with an RLock; hold the lock when coordinating live views.

Observable convergence

The observer protocol exposes every action, delta, and objective — logging, metrics, and tracing for free.

objective vs iteration · heuristic run
Convergence chart from a heuristic solve: objective climbs monotonically to the Euler edge bound
Max Planar Subgraph 62 nodes 229 edges in 180 edges out
Solvers

Choose your search strategy.

The greedy core is the floor, not the ceiling. Every strategy shares the same problem interface, so you can upgrade the search without rewriting the problem.

MultiStartSolver

Many random starts; the best result wins.

BeamSearchSolver

Top-κ candidate states explored in parallel.

AnytimeSolver

Best-so-far progress under a time budget.

AdaptiveBeamSolver

Diversity-aware beam ordering for better coverage.

LearnedGuidanceSolver

Online ML steers action choice as it explores.

MultiObjectiveSolver

Pareto-optimal frontiers across competing objectives.

StreamingSolver

Keep solving as the graph mutates under you.

HybridPipeline

Two-stage retrieval + reasoning, end to end.

API

Three lines to your first solve

Define a problem, point a solver at it, and read the result. Optional observers, early-stopping, and NetworkX interop when you need them.

solve.py 
from delta_search import Graph, GreedySolver, PrizeCollectingVertexCoverProblem

# Build an input graph with O(1) adjacency lookups.
graph = Graph[int].from_edges(
    [(1, 2), (2, 3), (3, 1), (3, 4),
     (4, 5), (5, 2), (1, 5)]
)

# Solve: cover every edge, keep the prize, pay vertex cost.
problem = PrizeCollectingVertexCoverProblem(graph, default_penalty=2.0)
result = GreedySolver(problem).solve(max_iterations=200)

print(result.best_objective)   # 95.0 — objective found
print(result.iteration)        # steps taken to get there
More patterns — custom problems, observers, early stopping, and NetworkX interop — in the developer docs. Alpha setup: git clone the repo, then use pip install -e . locally.

Explore better graphs.

An alpha-stage toolkit for six NP-hard problems, local deltas, and a search you can inspect as it converges.

Star on GitHub Read the arXiv paper

Alpha release · PyPI package coming soon · Python 3.10+ · MIT