state-space.core — org.clojars.cao/state-space 0.4.0

accumulate clj

(accumulate k init step)

Builds an extension that carries one value along every route under key k.

init is called with the start visit and returns the value at the start; step is called with the parent's value and the decoded transition and returns the value of the successor. For example, depth is (accumulate :depth (constantly 0) (fn [depth _] (inc depth))).

best-first clj

(best-first space starts)

(best-first space starts options)

Lazily selects the lowest-priority pending visit, best-first.

By default the priority is :distance, giving Dijkstra's shortest-path order. This default automatically enables distance-extension. Each successor is reached at unit cost unless :decode-edge decodes attributed successors to transition maps containing :state and an optional :weight. Weights must be finite and non-negative for Dijkstra's guarantees. Route options are as in dfs, plus :priority, a function of the visit map (default :distance) that orders the search, e.g. distance plus a heuristic for A*, or an extension-provided edge weight for Prim's algorithm. Each visit key is settled at most once, at the best priority offered for that key before settlement, so the priority must suit the problem (e.g. a consistent heuristic for A*); that is the caller's responsibility. Newly discovered candidates may have lower priorities than previously emitted visits, so custom priorities do not generally produce globally sorted results. A custom priority does not enable distance-extension; include it explicitly when the priority or results need cumulative distance. Equal priorities are emitted FIFO in enqueue order; this order depends on the iteration order of starts and successors. On infinite spaces, finite non-negative weights alone do not guarantee that a positive-cost result will eventually be emitted: an infinite region of equal or lower priority can keep it pending. Standard A* guarantees require additional assumptions, including bounded branching and edge costs bounded below by a positive value. :project and :visit-key receive a visit map containing :state and extension values, and :visit-key must not be nil. :emit is :enter (default) or :events. Event mode adds :phase :enter when a visit is selected and settled, then :phase :expand after its outgoing transitions have been handled, before selecting the next visit. An expansion is local, not completion of descendants or a post-order result. Improved pending candidates do not emit entries until selected. Phases never enter callbacks or identity functions. Invalid output modes throw ExceptionInfo when called. Unused options, including :fold, are ignored. Starts and each expanded state's transitions must be finite. Each result contains :state and extension values. Starting states are consumed and initialized only when the result is consumed; all starts are queued before the first visit is selected.

bfs clj

(bfs space starts)

(bfs space starts options)

Lazily breadth-first explores from an ordered collection of starting states.

Space and route options are the same as in dfs. :emit is :enter (default) or :events; exit-only output throws ExceptionInfo when called. Unused options, including :fold, are ignored. Events carry :phase :enter when a visit is accepted, and :phase :expand after all of its outgoing transitions have been handled. Expansion does not mean descendants have finished and does not give post-order. Successor entries can precede their parent's expansion event. An infinite successor collection can produce entries forever without that event. A pruned visit also gets an expansion event, without calling the space. Phases are output-only, not callback inputs or visit identity. In a static space, each equal state is reported once at its minimum edge-count depth. Add depth-extension to include edge-count depth. Successor generation is deferred until its frontier chunk is needed. An infinite current level can produce visits indefinitely but prevents deeper levels from being reached.

depth-extension clj

An extension that adds the number of transitions from the start as :depth.

dfs clj

(dfs space starts)

(dfs space starts options)

Lazily depth-first explores from an ordered collection of starting states.

Space is an invokable value called with the result of :project, which defaults to :state. Use :project identity for a function of the full visit map containing :state and any values supplied by :extensions. Maps and state-only functions work directly. Nil successor results are treated as leaves. Visits sharing the selected :visit-key are reported and expanded only on their first arrival. Each yielded visit contains :state.

:emit selects :enter (default), :exit, or :events. Entry and exit modes return untagged visits in pre-order and post-order respectively. With :emit :events, emits two snapshots per accepted visit, tagged with :phase :enter and :phase :exit. Entry precedes successor generation; exit follows handling the successors under deduplication and pruning rules. Back edges to active visits are skipped, so exit does not imply that every successor has exited on a cyclic graph. Pruned visits also enter and exit. Filter :enter for pre-order or :exit for post-order. :phase is reserved in event output. It is not passed to extensions, the space, :expand?, or :visit-key; route context and identity are unchanged. An infinite descending branch may produce entries forever without exits. Optional :fold performs memoized bottom-up evaluation as in postorder. It requires a non-nil :visit-key and :emit :exit or :emit :events. Entry events have no computed :value; exits carry the finished :value. Fold initialization is deferred until consumption resumes after entry.

Options may contain :project and :visit-key, both functions of the full visit map. :visit-key defaults to :state; set it to nil to disable deduplication. :decode-edge optionally maps each raw successor to a transition map containing :state; DFS uses that destination. Ordered :extensions add derived visit values and can inspect all decoded transition fields. Extensions are maps with :start and :next callbacks returning visit-context maps. Callbacks must preserve :state. Custom context fields merge in extension order, with later fields replacing earlier ones; use namespaced keys for independently reusable extensions to avoid accidental collisions. Folds reserve :value for results and :via and :back-edge for successor views. :start and :next prepare candidates before duplicate or path-repeat rejection, so they may run for visits that are never emitted. Prefer pure callbacks; use result consumption for actions on emitted visits. Invalid output modes and unsupported fold combinations throw ExceptionInfo when called. Unused options are ignored. Data and callback contracts are the caller's responsibility and are not validated.

distance-extension clj

An extension that adds cumulative transition weight (the path cost, default one) as :distance.

path-extension clj

An extension that adds the root-to-current state vector as :path context.

postorder clj

(postorder space starts)

(postorder space starts options)

Lazily returns visits in depth-first post-order.

Successors precede their parents; shared keys are evaluated once. Back edges are not followed, so finite graphs terminate even with cycles. The order is topological only for a DAG. Route options are as in dfs.

This is the exit view of the shared DFS lifecycle, without :phase tags; equivalent to dfs with :emit :exit, including optional :fold evaluation. :emit is ignored here; use dfs to select another output. Without a fold, :visit-key nil visits each occurrence, as in dfs.

Optional :fold computes a :value on each completed visit. It is a map: :init (visit -> accumulator), required :step (accumulator successor-view -> accumulator), required :finish (accumulator -> value), defaults to identity. :descend (accumulator transition child -> context-map), optional. Each newly entered key gets its own accumulator. :step runs once per examined edge in successor order, including edges to cached visits. A successor view has :state, route context, its completed :value, :via (the transition from this parent), and :back-edge. An unfinished back-edge view has no :value; the step must handle it explicitly. Use propagate for cyclic fixed points.

:descend adds or replaces child context after route extensions and before computing its visit key. It sees the parent's current accumulator, including earlier siblings' results, and runs once per examined edge, even for cached children. It must preserve :state and the reserved fields. It does not run for starts; initialize their context with a :start extension. Descended context affecting results must be included in :visit-key, just like route context. Alpha-beta cutoffs produce bounds, not necessarily exact values; do not reuse them as exact results under another window.

Return (reduced accumulator) from :init or :step to finish this visit without requesting another successor. :finish receives the unwrapped accumulator and is called exactly once per completed key, including leaves and early stops. Reducing a parent happens when consumption resumes after its child is yielded. Chunked inputs may realize extra raw successors, but no further edge is decoded after reduction stops.

Accumulators are private to parent frames: they are not route context and are not passed to :next or the space. Only :descend explicitly exposes selected fields to a child. Children are not collected; accumulate them explicitly if needed. The cache still retains completed visits. Extensions define only :start and :next, as in the other searches. :value, :via, and :back-edge are reserved and must not be extension fields. Keys must be stable and identify interchangeable computations, including any route context affecting expansion or the fold. Cached visits are not recomputed for a later arrival with the same key. These input contracts are the caller's responsibility and are not validated. A fold with :visit-key nil throws ExceptionInfo when called; unused options are ignored.

propagate clj

(propagate space initial-values {:keys [bottom join] :as options})

Lazily propagates and joins values through a state space.

initial-values maps starting states to their initial values; map keys are state identities. The space is called with :project (default :state); use :project identity to let its transitions depend on the full visit {:state state :value value}. Each decoded transition must contain :state and may contain :value, the contribution to join into that state's accumulated value. If :value is absent, the current value is propagated unchanged. Required option :join combines the current value with a contribution, and required option :bottom supplies the value for a state with no prior contribution. :bottom should be an identity for :join. :expand? can suppress expansion of a visit.

The first result is {:values initial-values :changes []}; it has no :processed key because no state has been processed yet. Each later record contains the updated :values map, its :processed state, and :changes, a vector of {:state state :value value} maps recording destination updates in transition order, including newly discovered states even at :bottom. A destination may occur more than once, with its accumulated value after each update; contributions leaving a known value unchanged add no entry. The :values map contains the values after all transitions for that record. Initial worklist construction is deferred until a processing record is requested. States whose values change are scheduled for processing again; a pending state is queued only once. The result is finite exactly when the worklist becomes empty. Exhaust it or take a prefix to observe progress; (last ...) returns the final values if propagation terminates.

For order-independent results, :join should be associative, commutative, and idempotent, and the contribution-generating behavior should be monotone in the accumulated information. Termination depends on the state space and whether values stabilize. Every expanded state must produce finitely many transitions. These are caller assumptions, not runtime checks. Input map iteration and successor order determine the order of intermediate results. Unused options, including :emit and :fold, are ignored.

simple-paths clj

(simple-paths space starts)

(simple-paths space starts options)

Lazily enumerates every visit reached by a simple path, depth-first.

Behaves like dfs without global deduplication, but never extends a path to a node whose :visit-key already occurs on that path, so paths may share nodes yet never revisit one. :visit-key defaults to :state; nil disables the check. Like dfs it only defines how the graph is traversed: which values appear in each visit is chosen with :extensions, e.g. path-extension for the route of states or trail-extension for the route with edge data. Visits are yielded for every path prefix; select goals with ordinary sequence functions, and return nil from the space to end a path at a goal. :emit selects :enter (default), :exit, or :events, as in dfs, for each accepted path occurrence rather than each globally distinct key. Exit mode gives post-order over path occurrences. :fold is ignored: shared-key memoization is different from occurrence-based evaluation. Output-mode checks and unused-option handling are as in dfs. Enumeration is depth-first, so infinite searches need not be fair.

trail-extension clj

An extension that adds :trail, the decoded transition maps from the root to the current visit. Unlike :path it keeps edge data such as labels and weights; the start is represented as {:state start}.