(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))).
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 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. 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. 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.
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. 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. 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 space starts)(bfs space starts options)Lazily breadth-first explores from an ordered collection of starting states.
Space and options are the same as in dfs. In a static space, each equal state is reported once at its minimum edge-count depth. Add depth-extension to include edge-count depth. An infinite current level can produce visits indefinitely but prevents deeper levels from being reached.
Lazily breadth-first explores from an ordered collection of starting states. Space and options are the same as in dfs. In a static space, each equal state is reported once at its minimum edge-count depth. Add depth-extension to include edge-count depth. An infinite current level can produce visits indefinitely but prevents deeper levels from being reached.
An extension that adds the number of transitions from the start as :depth.
An extension that adds the number of transitions from the start as :depth.
(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.
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. Postorder reserves :previous, :via, and :back-edge for its callback 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. Inputs are the caller's responsibility and are not validated; violating these expectations may produce unexpected results.
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. 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. Postorder reserves :previous, :via, and :back-edge for its callback 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. Inputs are the caller's responsibility and are not validated; violating these expectations may produce unexpected results.
An extension that adds cumulative transition weight (the path cost, default one) as :distance.
An extension that adds cumulative transition weight (the path cost, default one) as :distance.
An extension that adds the root-to-current state vector as :path context.
An extension that adds the root-to-current state vector as :path context.
(postorder space starts)(postorder space starts options)Lazily returns visits in depth-first post-order.
Each visit is returned after all of its successors, so when edges point from a task to its prerequisites, prerequisites appear before the task. A node is marked known when first entered, so cyclic graphs terminate: a back edge is simply ignored, and the result is then the plain DFS post-order (a valid topological order exactly when the reachable graph is a DAG). Options are as in dfs, but :visit-key must not be nil. Its result must remain stable from entry through completion: :exit callbacks must not change fields in a way that changes the visit key.
Extensions may also define :exit, a function of a visit and the visits of its successors returning a map merged into the visit as it is emitted: a bottom-up computation over the successors' own results. Each successor appears as the visit that first reached that node: finished, with its :exit values, or, for a back edge to a node still in progress, with top-down values only. Equal visit keys must identify interchangeable computations: include relevant route context in the key when expansion, :more? pruning, or computed results depend on it. A cached result from one budget or pruning window is not automatically valid under another; later arrivals do not recompute it. These are caller expectations, not runtime checks. Successors are reported in the order the space produced them, and each carries two keys describing the edge it was reached by in this particular parent: :via, the decoded transition (so edge weights and labels are available even when the node was first reached through another edge), and :back-edge, true when the successor was still in progress. Extensions must not define :previous, :via, or :back-edge as their own context fields; these keys are reserved for postorder's callback views, not guaranteed fields on emitted visits. These expectations are not checked at runtime.
Successors are consumed and decoded one at a time. Callbacks may also see siblings finished so far: :next receives the parent with a :previous key, the vector of its already finished successors (in the same form as in :exit), and an extension's :more? callback, a function of the visit and that vector, is checked before consuming and decoding the next successor, including the first. If any callback returns false, no next successor is decoded or visited and the visit is finished with what it has. A chunked successor collection may realize more raw values when one is consumed. The check also happens once when a visit has no successors, so callbacks should not assume another successor exists. Together these hooks let information flow from earlier siblings to later ones, as in alpha-beta pruning or short-circuit evaluation.
Lazily returns visits in depth-first post-order. Each visit is returned after all of its successors, so when edges point from a task to its prerequisites, prerequisites appear before the task. A node is marked known when first entered, so cyclic graphs terminate: a back edge is simply ignored, and the result is then the plain DFS post-order (a valid topological order exactly when the reachable graph is a DAG). Options are as in dfs, but :visit-key must not be nil. Its result must remain stable from entry through completion: :exit callbacks must not change fields in a way that changes the visit key. Extensions may also define :exit, a function of a visit and the visits of its successors returning a map merged into the visit as it is emitted: a bottom-up computation over the successors' own results. Each successor appears as the visit that first reached that node: finished, with its :exit values, or, for a back edge to a node still in progress, with top-down values only. Equal visit keys must identify interchangeable computations: include relevant route context in the key when expansion, :more? pruning, or computed results depend on it. A cached result from one budget or pruning window is not automatically valid under another; later arrivals do not recompute it. These are caller expectations, not runtime checks. Successors are reported in the order the space produced them, and each carries two keys describing the edge it was reached by in this particular parent: :via, the decoded transition (so edge weights and labels are available even when the node was first reached through another edge), and :back-edge, true when the successor was still in progress. Extensions must not define :previous, :via, or :back-edge as their own context fields; these keys are reserved for postorder's callback views, not guaranteed fields on emitted visits. These expectations are not checked at runtime. Successors are consumed and decoded one at a time. Callbacks may also see siblings finished so far: :next receives the parent with a :previous key, the vector of its already finished successors (in the same form as in :exit), and an extension's :more? callback, a function of the visit and that vector, is checked before consuming and decoding the next successor, including the first. If any callback returns false, no next successor is decoded or visited and the visit is finished with what it has. A chunked successor collection may realize more raw values when one is consumed. The check also happens once when a visit has no successors, so callbacks should not assume another successor exists. Together these hooks let information flow from earlier siblings to later ones, as in alpha-beta pruning or short-circuit evaluation.
(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. 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.
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.
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.(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. Enumeration is depth-first, so infinite searches need not be fair.
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. Enumeration is depth-first, so infinite searches need not be fair.
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}.
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}.cljdoc builds & hosts documentation for Clojure/Script libraries
| Ctrl+k | Jump to recent docs |
| ← | Move to previous article |
| → | Move to next article |
| Ctrl+/ | Jump to the search field |