(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. 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.
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. 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.
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 :value for fold 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. 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 :value for fold 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. 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.
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. Options are as in dfs; :visit-key must not be nil.
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. 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.
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. 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.
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. Options are as in dfs; :visit-key must not be nil. 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. 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. 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. 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.
(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.
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.(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 |