Lazy exploration of graphs and generated state spaces.
A space is anything callable with a state that returns a collection of successor states, or nil for none: an adjacency map or a function. A search takes a space and a collection of starting states, and returns a lazy sequence of visits. A visit is a map with :state plus whatever route context was requested through :extensions.
(bfs {:a [:b :c] :b [:d]} [:a] {:extensions [path]}) ;; => ({:state :a :path [:a]} {:state :b :path [:a :b]} ;; {:state :c :path [:a :c]} {:state :d :path [:a :b :d]})
Operations dfs depth-first, each visit before its successors postorder depth-first, each visit after its successors; bottom-up folds bfs breadth-first, fewest transitions first best-first lowest priority first: Dijkstra's algorithm, A*, or your own propagate joins values flowing through a space until they stabilize
Options shared by the four searches. Every option is optional, and nil means the default. Callbacks receive the whole visit unless stated otherwise. :extensions ordered collection of extensions adding route context to visits: path, depth, trail, distance, or your own. :decode-edge turns each successor the space returns into a transition, a map with the destination :state and any edge data. Either a function, or a vector of field names for successors that are tuples, such as [:state :weight]. By default a successor is the destination state itself. :visit-key says which visits count as the same position. Default :state. :dedupe how often a key may be visited: :search (default) once in the whole search, :path once on each route, so every simple path is explored, or :none without limit. :expand? predicate; a visit it rejects is still returned but its successors are not requested. :project what the space is called with. Default :state; use identity for a space that reads the whole visit.
Arguments are checked when an operation is called: unknown options, values of the wrong shape, and starts that are not a collection throw ExceptionInfo before any callback runs. Its data hold the :function and the :option or :argument at fault. Results are lazy, so what a callback returns is checked, and a callback's own failure surfaces, when the visit that needs it is consumed.
state-space.trace offers the same searches as streams of events.
Lazy exploration of graphs and generated state spaces.
A space is anything callable with a state that returns a collection of
successor states, or nil for none: an adjacency map or a function. A search
takes a space and a collection of starting states, and returns a lazy
sequence of visits. A visit is a map with :state plus whatever route
context was requested through :extensions.
(bfs {:a [:b :c] :b [:d]} [:a] {:extensions [path]})
;; => ({:state :a :path [:a]} {:state :b :path [:a :b]}
;; {:state :c :path [:a :c]} {:state :d :path [:a :b :d]})
Operations
dfs depth-first, each visit before its successors
postorder depth-first, each visit after its successors; bottom-up folds
bfs breadth-first, fewest transitions first
best-first lowest priority first: Dijkstra's algorithm, A*, or your own
propagate joins values flowing through a space until they stabilize
Options shared by the four searches. Every option is optional, and nil
means the default. Callbacks receive the whole visit unless stated otherwise.
:extensions ordered collection of extensions adding route context to
visits: path, depth, trail, distance, or your own.
:decode-edge turns each successor the space returns into a transition,
a map with the destination :state and any edge data. Either
a function, or a vector of field names for successors that
are tuples, such as [:state :weight]. By default a
successor is the destination state itself.
:visit-key says which visits count as the same position.
Default :state.
:dedupe how often a key may be visited: :search (default) once in
the whole search, :path once on each route, so every simple
path is explored, or :none without limit.
:expand? predicate; a visit it rejects is still returned but its
successors are not requested.
:project what the space is called with. Default :state; use identity
for a space that reads the whole visit.
Arguments are checked when an operation is called: unknown options,
values of the wrong shape, and starts that are not a collection throw
ExceptionInfo before any callback runs. Its data hold the :function and
the :option or :argument at fault. Results are lazy, so what a callback
returns is checked, and a callback's own failure surfaces, when the visit
that needs it is consumed.
state-space.trace offers the same searches as streams of events.(accumulate k init step)Builds an extension that carries one value along every route, in the visit field k.
(init visit) gives the value at a starting visit. (step value transition) gives a successor's value from its parent's value and the transition between them. For example, depth is
(accumulate :depth (constantly 0) (fn [depth _] (inc depth)))
An extension is a map with optional :start and :next callbacks, each returning a map of fields to add to the visit being built:
{:start (fn [visit] fields) :next (fn [parent transition visit] fields)}
Extensions run in order and see the fields added by earlier ones. They run for every candidate, including arrivals that deduplication then rejects, so they should be pure. They must not replace :state.
Builds an extension that carries one value along every route, in the
visit field k.
(init visit) gives the value at a starting visit. (step value transition)
gives a successor's value from its parent's value and the transition
between them. For example, depth is
(accumulate :depth (constantly 0) (fn [depth _] (inc depth)))
An extension is a map with optional :start and :next callbacks, each
returning a map of fields to add to the visit being built:
{:start (fn [visit] fields)
:next (fn [parent transition visit] fields)}
Extensions run in order and see the fields added by earlier ones. They run
for every candidate, including arrivals that deduplication then rejects,
so they should be pure. They must not replace :state.(best-first space starts)(best-first space starts options)Lazily explores a space in priority order, lowest first.
By default the priority is the cumulative :distance of a visit, the sum of the :weight of its transitions (one each unless :decode-edge provides weights). This is Dijkstra's algorithm: visits come in nondecreasing distance and the first visit of a state is a least-cost route to it. That requires non-negative weights, so a negative weight throws when reached.
Options: :extensions :decode-edge :visit-key :dedupe :expand? :project, described in the namespace documentation, and :heuristic (fn [visit] estimate) of the remaining cost, added to :distance to order visits. This is A*. With the default :dedupe :search the first visit of a goal is optimal when the estimate is consistent. :priority (fn [visit] priority) replacing the default ordering. Values must be mutually comparable and not nil. The search then adds no :distance; list the extensions the priority reads. It cannot be combined with :heuristic.
(first (filter #(= :goal (:state %)) (best-first {:a [[:goal 9] [:b 2]] :b [[:goal 3]]} [:a] {:decode-edge [:state :weight] :extensions [path]}))) ;; => {:state :goal :distance 5 :path [:a :b :goal]}
With :dedupe :search each key is returned once, by the best-priority arrival offered before it is selected. With :path every simple path is returned in priority order, so the visits of a goal list its routes from cheapest to most expensive; :none does the same for walks.
Equal priorities are returned in the order they were found. The starts and the successors of each visit must be finite: all are examined before the next visit is selected.
Lazily explores a space in priority order, lowest first.
By default the priority is the cumulative :distance of a visit, the sum of
the :weight of its transitions (one each unless :decode-edge provides
weights). This is Dijkstra's algorithm: visits come in nondecreasing
distance and the first visit of a state is a least-cost route to it. That
requires non-negative weights, so a negative weight throws when reached.
Options: :extensions :decode-edge :visit-key :dedupe :expand? :project,
described in the namespace documentation, and
:heuristic (fn [visit] estimate) of the remaining cost, added to
:distance to order visits. This is A*. With the default
:dedupe :search the first visit of a goal is optimal when
the estimate is consistent.
:priority (fn [visit] priority) replacing the default ordering. Values
must be mutually comparable and not nil. The search then
adds no :distance; list the extensions the priority reads.
It cannot be combined with :heuristic.
(first (filter #(= :goal (:state %))
(best-first {:a [[:goal 9] [:b 2]] :b [[:goal 3]]} [:a]
{:decode-edge [:state :weight]
:extensions [path]})))
;; => {:state :goal :distance 5 :path [:a :b :goal]}
With :dedupe :search each key is returned once, by the best-priority
arrival offered before it is selected. With :path every simple path is
returned in priority order, so the visits of a goal list its routes from
cheapest to most expensive; :none does the same for walks.
Equal priorities are returned in the order they were found. The starts and
the successors of each visit must be finite: all are examined before the
next visit is selected.(bfs space starts)(bfs space starts options)Lazily explores a space breadth-first.
All starts come first, then their successors, level by level. With the default :dedupe :search each visit key is returned once, at its fewest transitions from any start, so the first visit of a goal is a shortest route when every transition costs the same. :dedupe :path returns every simple path, shortest first.
Options: :extensions :decode-edge :visit-key :dedupe :expand? :project, described in the namespace documentation.
(first (filter #(= :d (:state %)) (bfs {:a [:b :c] :b [:d] :c [:d]} [:a] {:extensions [path]}))) ;; => {:state :d :path [:a :b :d]}
Successors are requested only when the search reaches them. An infinite level yields visits forever without reaching the next level.
Lazily explores a space breadth-first.
All starts come first, then their successors, level by level. With the
default :dedupe :search each visit key is returned once, at its fewest
transitions from any start, so the first visit of a goal is a shortest
route when every transition costs the same. :dedupe :path returns every
simple path, shortest first.
Options: :extensions :decode-edge :visit-key :dedupe :expand? :project,
described in the namespace documentation.
(first (filter #(= :d (:state %))
(bfs {:a [:b :c] :b [:d] :c [:d]} [:a]
{:extensions [path]})))
;; => {:state :d :path [:a :b :d]}
Successors are requested only when the search reaches them. An infinite
level yields visits forever without reaching the next level.Extension adding :depth, the number of transitions from the start.
Extension adding :depth, the number of transitions from the start.
(dfs space starts)(dfs space starts options)Lazily explores a space depth-first and returns each visit before its successors (pre-order).
Starts and successors are taken in the order given. With the default :dedupe :search, each visit key is returned and expanded on its first arrival only, so cycles end. :dedupe :path explores every simple path instead, and :dedupe :none every walk.
Options: :extensions :decode-edge :visit-key :dedupe :expand? :project, described in the namespace documentation.
(map :state (dfs {:a [:b :c] :b [:d] :c [:d]} [:a])) ;; => (:a :b :d :c)
An infinite branch keeps later siblings from being reached. Use postorder for visits in completion order.
Lazily explores a space depth-first and returns each visit before its
successors (pre-order).
Starts and successors are taken in the order given. With the default
:dedupe :search, each visit key is returned and expanded on its first
arrival only, so cycles end. :dedupe :path explores every simple path
instead, and :dedupe :none every walk.
Options: :extensions :decode-edge :visit-key :dedupe :expand? :project,
described in the namespace documentation.
(map :state (dfs {:a [:b :c] :b [:d] :c [:d]} [:a]))
;; => (:a :b :d :c)
An infinite branch keeps later siblings from being reached. Use postorder
for visits in completion order.Extension adding :distance, the sum of the :weight of the transitions from the start. A transition without :weight counts one.
Extension adding :distance, the sum of the :weight of the transitions from the start. A transition without :weight counts one.
Extension adding :path, the vector of states from the start to the visit.
Extension adding :path, the vector of states from the start to the visit.
(postorder space starts)(postorder space starts options)Lazily explores a space depth-first and returns each visit after its successors (post-order).
On an acyclic space this is a dependency order: everything a state leads to comes before the state. With the default :dedupe :search an edge back to a visit that is still being explored is not followed, so finite spaces with cycles end too.
Options: :extensions :decode-edge :visit-key :dedupe :expand? :project, described in the namespace documentation, and :fold.
:fold computes a :value for each visit from the values of its successors. It is a map of callbacks:
:init (fn [visit] accumulator) required :step (fn [accumulator child] accumulator) required :finish (fn [accumulator] value) default identity :descend (fn [accumulator transition child] fields)
(postorder {:app [:lib :config] :lib [:base]} [:app] {:fold {:init (constantly 1) :step (fn [size child] (+ size (:value child)))}}) ;; => ({:state :base :value 1} {:state :lib :value 2} ;; {:state :config :value 1} {:state :app :value 4})
:step runs once per outgoing edge, in order. Its child is the successor's visit with three more fields: :value, its result; :transition, the transition from this parent; and :on-path?, true when the edge returns to a visit on the current path. Such a visit is still being explored and has no :value.
Returning (reduced accumulator) from :init or :step completes the visit without requesting further successors. :finish turns the final accumulator into the visit's :value.
:descend passes information down: it returns fields to add to a child before the child is entered, and sees the accumulator after the earlier siblings. It does not run for starts.
With :dedupe :search a key is evaluated once and its result is reused by every edge that reaches it, so :visit-key must include any route context the result depends on. With :path or :none each occurrence is evaluated on its own; under :path a child that would repeat a key of the current path arrives with :on-path? true and is not entered.
Visit fields named :value, :transition, and :on-path? are reserved by a fold. The stack does not grow with the depth of the space.
Lazily explores a space depth-first and returns each visit after its
successors (post-order).
On an acyclic space this is a dependency order: everything a state leads
to comes before the state. With the default :dedupe :search an edge back
to a visit that is still being explored is not followed, so finite spaces
with cycles end too.
Options: :extensions :decode-edge :visit-key :dedupe :expand? :project,
described in the namespace documentation, and :fold.
:fold computes a :value for each visit from the values of its successors.
It is a map of callbacks:
:init (fn [visit] accumulator) required
:step (fn [accumulator child] accumulator) required
:finish (fn [accumulator] value) default identity
:descend (fn [accumulator transition child] fields)
(postorder {:app [:lib :config] :lib [:base]} [:app]
{:fold {:init (constantly 1)
:step (fn [size child] (+ size (:value child)))}})
;; => ({:state :base :value 1} {:state :lib :value 2}
;; {:state :config :value 1} {:state :app :value 4})
:step runs once per outgoing edge, in order. Its child is the successor's
visit with three more fields: :value, its result; :transition, the
transition from this parent; and :on-path?, true when the edge returns to
a visit on the current path. Such a visit is still being explored and has
no :value.
Returning (reduced accumulator) from :init or :step completes the visit
without requesting further successors. :finish turns the final accumulator
into the visit's :value.
:descend passes information down: it returns fields to add to a child
before the child is entered, and sees the accumulator after the earlier
siblings. It does not run for starts.
With :dedupe :search a key is evaluated once and its result is reused by
every edge that reaches it, so :visit-key must include any route context
the result depends on. With :path or :none each occurrence is evaluated on
its own; under :path a child that would repeat a key of the current path
arrives with :on-path? true and is not entered.
Visit fields named :value, :transition, and :on-path? are reserved by a
fold.
The stack does not grow with the depth of the space.(propagate space initial-values join)(propagate space initial-values join options)Lazily propagates values through a space, joining what arrives at each state and processing a state again whenever its value changes.
initial-values maps starting states to their values. Each processed state sends a contribution along every transition: the transition's :value when it has one, otherwise the state's own value. A state reached for the first time takes the contribution as its value; later contributions are combined with (join current contribution).
Options, all optional :decode-edge as for the searches. Use identity for a space that returns transitions with their own :value contributions. :project what the space is called with. Default :state; identity passes the visit {:state state :value value}. :expand? predicate of the visit; false sends nothing onward.
Returns a lazy sequence of progress records. The first holds the initial values; each later one describes one processed state:
{:values {state value} all values after this step :processed state absent from the first record :changes [{:state :value}] updates made by this step, in order}
(:values (last (propagate {:a [:b] :b [:a :c]} {:a #{1} :c #{2}} into))) ;; => {:a #{1} :c #{1 2} :b #{1}}
The sequence ends when no state is waiting to be processed, so (last ...) holds the fixed point. Whether that happens depends on the problem: values must stop changing. The result does not depend on processing order when join is associative, commutative, and idempotent, and contributions only grow as values grow. Each state's successors must be finite.
Lazily propagates values through a space, joining what arrives at each
state and processing a state again whenever its value changes.
initial-values maps starting states to their values. Each processed state
sends a contribution along every transition: the transition's :value when
it has one, otherwise the state's own value. A state reached for the first
time takes the contribution as its value; later contributions are combined
with (join current contribution).
Options, all optional
:decode-edge as for the searches. Use identity for a space that returns
transitions with their own :value contributions.
:project what the space is called with. Default :state; identity
passes the visit {:state state :value value}.
:expand? predicate of the visit; false sends nothing onward.
Returns a lazy sequence of progress records. The first holds the initial
values; each later one describes one processed state:
{:values {state value} all values after this step
:processed state absent from the first record
:changes [{:state :value}] updates made by this step, in order}
(:values (last (propagate {:a [:b] :b [:a :c]} {:a #{1} :c #{2}} into)))
;; => {:a #{1} :c #{1 2} :b #{1}}
The sequence ends when no state is waiting to be processed, so (last ...)
holds the fixed point. Whether that happens depends on the problem: values
must stop changing. The result does not depend on processing order when
join is associative, commutative, and idempotent, and contributions only
grow as values grow. Each state's successors must be finite.Extension adding :trail, the vector of transitions from the start to the visit. Unlike :path it keeps edge data such as labels and weights. Its first element is {:state start}.
Extension adding :trail, the vector of transitions from the start to the
visit. Unlike :path it keeps edge data such as labels and weights. Its
first element is {: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 |