Docs / Concepts

One loop, clear boundaries.

DeltaSearch separates storage, domain rules, search policy, and observability. That separation is what lets the same solver work across six built-in problems and your own.

The four layers

LayerOwnsShould not own
GraphNodes, edges, attributes, lookup and mutation.Problem-specific feasibility or search strategy.
ProblemActions, reward, penalty, feasibility, reversible domain mutations.Global iteration policy or logging format.
SolverCandidate selection, budgets, stopping, best-state tracking.How a domain objective is calculated.
ObserverLogs, metrics, traces, progress, and external reporting.Changing the chosen action or mutating solver state.

The state loop

Each iteration starts from a current state. The problem enumerates candidate actions. The solver temporarily applies candidates, asks for their deltas, undoes them, and commits the best feasible improvement. The committed state becomes the next iteration’s input.

state₀
  │
  ├─ enumerate_actions(state₀)
  │       │
  │       ├─ apply_action(candidate A) → calculate_delta → undo_action
  │       ├─ apply_action(candidate B) → calculate_delta → undo_action
  │       └─ apply_action(candidate C) → calculate_delta → undo_action
  │
  └─ commit best candidate → state₁ → repeat
Why undo matters

Candidate evaluation should not leak mutations into the next candidate. The undo record is the transaction boundary. If a custom action changes more than the default graph mutation captures, extend the undo data and test the exact inverse.

The problem contract

A problem is a domain adapter. It tells DeltaSearch what a move means and how valuable it is.

enumerate_actions

Return legal candidates worth considering. Prefer bounded, deterministic ordering when reproducibility matters.

calculate_delta

Return reward change, penalty change, and feasibility for a candidate. Use local context; avoid a full graph scan.

apply_action / undo_action

Make a mutation reversible. The default path copies defensively; the incremental path trades isolation for speed.

objective and feasibility

Objective is reward minus penalty. A feasible state satisfies hard constraints independently of its score.

Extension model

Choose the narrowest extension point that solves the problem:

  1. Need a new domain? Add a SubgraphExtractionProblem subclass.
  2. Need a new selection policy? Add a solver strategy that consumes the same problem interface.
  3. Need a new output? Add an observer or serializer.
  4. Need a new graph primitive? Extend Graph with tests for complexity, ownership, and reversibility.

This keeps polymorphism useful rather than ornamental: callers depend on the problem and observer protocols, while concrete implementations vary behind them.

Ownership and concurrency

The plain Graph is the fast single-threaded value. ThreadSafeGraph wraps mutations and snapshot-producing methods with an RLock. Its live nodes and edges views are not multi-read snapshots; use node_list(), sorted_edges(), or hold graph.lock across a compound read.

Solver instances should own their problem instances. Share input data intentionally, and do not retain a mutable internal state object after a solve unless the API says it is safe.

What O(1) actually means

DeltaSearch’s O(1) claim applies to the local delta calculation for a candidate move. It does not make action enumeration, state copying, feasibility checks, or a full iteration constant time. Benchmark these pieces separately before opting into incremental=True.

total solve time
  = enumeration
  + candidate apply / undo
  + delta evaluation
  + feasibility checks
  + observer overhead
  + state-copy cost
Next: API reference →