state-space.core — org.clojars.cao/state-space 0.5.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.

:priority accepts a visit-map function or a keyword naming a visit field; it defaults to :distance. The default, including explicit :priority :distance, enables distance-extension and gives Dijkstra's shortest-path order. 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. Other priorities, such as distance plus a heuristic for A* or an extension-provided edge weight for Prim's algorithm, do not automatically enable distance-extension; include it explicitly when the priority or results need cumulative distance. User extensions run after the required distance extension and can replace :distance, affecting the default priority. 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. 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 output reports start and edge candidates with :disposition and (for queued candidates) :effect or :reason, as well as :visit events. A visit emits :phase :enter when selected and settled, then :phase :expand after its outgoing transitions have been handled. An expansion is local, not completion of descendants. Improved pending candidates do not emit visits until selected. Event envelopes 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. A nil :visit-key throws ExceptionInfo when called. 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. Event output interleaves :candidate records for starts and queued transitions with :visit records. Each :candidate event is emitted when the start or transition is queued and is marked :scheduled. A queued duplicate may later emit a :skip visit event with :reason :already-visited. Visit records carry :phase :enter when selected and :phase :expand after all outgoing transitions have been handled. Expansion does not mean descendants have finished. 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. With the default :visit-key :state, each state in a static space 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 {:event :candidate ...} records for each start and decoded transition, interleaved with {:event :visit ...} lifecycle records. Visit records contain :phase :enter or :exit and a nested :visit map. Candidate records contain :origin, :visit, and :disposition; edge candidates also contain :from and :transition. Rejected candidates have a :reason. Entry precedes successor generation; exit follows handling the successors under deduplication and pruning rules. Back edges to active visits are rejected as candidates, so exit does not imply that every successor has exited on a cyclic graph. Pruned visits enter and exit. Filter visit events by :phase for pre-order or post-order. Event envelope fields are 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 optional :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. With a visit key that identifies repeated states, back edges are not followed, so finite graphs terminate even with cycles. Setting :visit-key nil disables this cycle check; traversal of a cycle may then not terminate. 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 event tags; equivalent to dfs with :emit :exit, including optional :fold evaluation. :emit :events opts into the full DFS event stream; other :emit values are ignored. 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. :emit :events wraps each progress record in {:event :progress :record ...}; the default :emit :enter preserves the bare records. Other :emit values throw ExceptionInfo. :fold is ignored. A missing :bottom or nil :join throws ExceptionInfo when called.

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. Event mode includes candidate decisions rejected for repeating a state on the current path. 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}.