State-space

Lazy search over graphs and generated state spaces, for Clojure.

You describe a problem as states and a function that gives the successors of a state. State-space supplies the traversal: depth-first and breadth-first search, best-first search (Dijkstra's algorithm and A*), post-order traversal with bottom-up folds, and fixed-point propagation.

Every search returns a lazy sequence of plain maps, so finding a goal, taking a prefix, or collecting results is ordinary sequence code:

(require '[state-space.core :as ss])

(def graph
  {:start [:left :right]
   :left  [:goal]
   :right [:goal]
   :goal  []})

(first (filter #(= :goal (:state %))
               (ss/bfs graph [:start] {:extensions [ss/path]})))
;; => {:state :goal, :path [:start :left :goal]}

Documentation

• This README introduces every operation and option.
• The State-space guide (PDF) explains the algorithms, their guarantees, and the implementation.
• The Worked examples (PDF) solve more than fifty problems with the library.
• Docstrings are the reference: start with (doc state-space.core).

Both PDFs are built from state-space.tex and worked-examples.tex. Every example in this README and in both documents is run by the test suite.

Installation

Add the library to your deps.edn:

{:deps
 {org.clojars.cao/state-space {:mvn/version "0.6.0"}}}

This README describes the source in this repository. Between releases it can be ahead of the published version; CHANGELOG.md lists the differences, and the documents attached to a release describe that release. To use the source directly, depend on {:local/root "../state-space"} or a Git coordinate instead.

The library has no dependencies besides Clojure. It is tested with Clojure 1.12 on Java 21 and 25.

The model

• A state is any value from your problem: a keyword, a board, a pair such as [location fuel].
• A space is anything you can call with a state to get its successors: an adjacency map or a function. nil or a missing map entry means no successors.
• A search takes a space and a collection of starting states. It returns visits: maps with :state, plus whatever route context you ask for.

(map :state (ss/dfs graph [:start]))
;; => (:start :left :goal :right)

(defn tree-children [n]
  [(* 2 n) (inc (* 2 n))])

(map :state (take 5 (ss/bfs tree-children [1])))
;; => (1 2 3 4 5)

Starting states always come as a collection, also when there is one. To start from the state [0 0], pass [[0 0]].

Put whatever decides the future moves into the state itself. If the roads a vehicle can take depend on its remaining fuel, [junction fuel] is the state; arriving at the same junction with different fuel is then a different position without any further configuration.

Operations

Operation	Returns	Use it to
dfs	visits depth-first, each before its successors	reach or enumerate states when the length of the route does not matter
postorder	visits depth-first, each after its successors	order dependencies, or compute a value for each state from its successors with :fold
bfs	visits with the fewest transitions first	find shortest routes when every transition costs the same
best-first	visits with the lowest priority first	find least-cost routes (Dijkstra's algorithm), guide the search with :heuristic (A*), or order by your own :priority
propagate	progress records	join information that flows through a space, including around cycles, until nothing changes

The four searches share one call shape, (search space starts options), and the options below. propagate takes a map of initial values instead of starting states, and a function that joins values.

Options

All options are optional, and nil means the default. Callbacks receive the whole visit.

Option	Default	Meaning
:extensions	none	Ordered collection of extensions that add route context to visits: ss/path, ss/depth, ss/trail, ss/distance, or your own.
:decode-edge	successor is the state	Turns each successor the space returns into a transition: a map with the destination :state and any edge data. A function, or a vector of field names such as [:state :weight] for successors that are tuples.
:visit-key	:state	Says which visits count as the same position.
:dedupe	:search	How often a key may be visited: :search once in the whole search, :path once on each route, :none without limit.
:expand?	always	Predicate; a visit it rejects is still returned, but its successors are not requested.
:project	:state	What the space is called with. Use identity for a space that reads the whole visit.

postorder adds :fold; best-first adds :heuristic and :priority; propagate accepts :decode-edge, :expand?, and :project.

Route context

Extensions carry information along each route and add it to the visits:

(ss/dfs graph [:start] {:extensions [ss/depth ss/path]})
;; => ({:state :start, :depth 0, :path [:start]}
;;     {:state :left, :depth 1, :path [:start :left]}
;;     {:state :goal, :depth 2, :path [:start :left :goal]}
;;     {:state :right, :depth 1, :path [:start :right]})

Extension	Adds
ss/path	:path, the states from the start to the visit
ss/depth	:depth, the number of transitions from the start
ss/trail	:trail, the transitions from the start, with their edge data
ss/distance	:distance, the sum of the transitions' :weight (one when absent)

ss/accumulate builds an extension that carries one value. It takes the visit field, a function giving the value at a start, and a function giving the next value from the previous one and the transition:

(def fuel
  (ss/accumulate :fuel
                 (constantly 10)
                 (fn [fuel transition] (- fuel (:cost transition)))))

(ss/dfs {:camp [[:ridge 3]] :ridge [[:peak 4]]} [:camp]
        {:decode-edge [:state :cost]
         :extensions [fuel]})
;; => ({:state :camp, :fuel 10} {:state :ridge, :fuel 7} {:state :peak, :fuel 3})

:decode-edge [:state :cost] reads each successor [:ridge 3] as the transition {:state :ridge :cost 3}. Edge data stays on the transition: extensions decide what becomes part of a visit.

In general an extension is a map with optional :start and :next callbacks, each returning the fields to add to the visit being built:

(def came-from
  {:start (fn [visit] {:from nil})
   :next  (fn [parent transition visit] {:from (:state parent)})})

(map (juxt :state :from) (ss/bfs graph [:start] {:extensions [came-from]}))
;; => ([:start nil] [:left :start] [:right :start] [:goal :left])

Limit a search with :expand?, which sees this context:

(map :state (ss/bfs tree-children [1]
                    {:extensions [ss/depth]
                     :expand? #(< (:depth %) 2)}))
;; => (1 2 3 4 5 6 7)

Identity and deduplication

:visit-key says when two visits are the same position; by default, when they have the same state. :dedupe says how often a position may be visited. With the default, :search, each one is visited once: dfs and bfs keep its first arrival, and best-first the one with the best priority. That is what makes searches on graphs with cycles end.

:dedupe :path only forbids repeating a position along a route, so every simple path is explored:

(->> (ss/dfs graph [:start] {:dedupe :path :extensions [ss/path]})
     (filter #(= :goal (:state %)))
     (map :path))
;; => ([:start :left :goal] [:start :right :goal])

:dedupe :none visits every walk, like tree-seq on a tree. On a space with cycles it needs a bound such as :expand?.

Use :visit-key when positions are told apart by more, or by less, than the state. Here a state may be visited once at each depth:

(map (juxt :state :depth)
     (ss/dfs {:a [:b :c] :b [:c] :c []} [:a]
             {:extensions [ss/depth]
              :visit-key (juxt :state :depth)}))
;; => ([:a 0] [:b 1] [:c 2] [:c 1])

Least-cost routes

best-first orders visits by :distance, the sum of the weights of their transitions. Give the transitions a :weight with :decode-edge:

(def roads
  {:start [[:goal 10] [:via 2]]
   :via   [[:goal 3]]})

(first (filter #(= :goal (:state %))
               (ss/best-first roads [:start]
                              {:decode-edge [:state :weight]
                               :extensions [ss/path]})))
;; => {:state :goal, :distance 5, :path [:start :via :goal]}

This is Dijkstra's algorithm, so weights must not be negative; a negative weight throws when the search meets it. With :dedupe :path, the same search lists every route from the cheapest to the most expensive:

(->> (ss/best-first roads [:start]
                    {:decode-edge [:state :weight]
                     :dedupe :path
                     :extensions [ss/path]})
     (filter #(= :goal (:state %)))
     (map (juxt :path :distance)))
;; => ([[:start :via :goal] 5] [[:start :goal] 10])

:heuristic estimates the cost remaining from a visit. The search then orders by distance plus estimate, which is A*:

(def remaining {:start 4, :via 3, :goal 0})

(map (juxt :state :distance)
     (ss/best-first roads [:start]
                    {:decode-edge [:state :weight]
                     :heuristic (comp remaining :state)}))
;; => ([:start 0] [:via 2] [:goal 5])

For any other order, :priority replaces the default one. The search then adds no :distance: list the extensions your priority reads. This finds the route whose worst road is the best possible:

(def worst-road
  (ss/accumulate :worst (constantly 0)
                 (fn [worst transition] (max worst (:weight transition)))))

(first (filter #(= :goal (:state %))
               (ss/best-first roads [:start]
                              {:decode-edge [:state :weight]
                               :extensions [worst-road ss/path]
                               :priority :worst})))
;; => {:state :goal, :worst 3, :path [:start :via :goal]}

Bottom-up computations

postorder returns each visit after its successors. Its :fold computes a :value for each visit from the values of its successors: :init starts an accumulator for a visit, and :step updates it with each child.

(ss/postorder {:app [:lib :config] :lib [:base] :config [:base]} [:app]
              {:fold {:init (fn [{:keys [state]}] #{state})
                      :step (fn [needed child] (into needed (:value child)))}})
;; => ({:state :base, :value #{:base}}
;;     {:state :lib, :value #{:lib :base}}
;;     {:state :config, :value #{:config :base}}
;;     {:state :app, :value #{:app :lib :config :base}})

Shared successors such as :base are evaluated once and reused, and depth does not grow the stack, so this is memoized recursion without the recursion.

• Return (reduced accumulator) from :init or :step to finish a visit without looking at its remaining successors.
• An optional :finish turns the final accumulator into the :value.
• Each child passed to :step also has :transition, the transition that leads to it, and :on-path?, true when the edge returns to a visit on the current path, which is still being explored and therefore has no :value yet.
• An optional :descend passes information from the accumulator down to the next child, which is what alpha-beta pruning needs.

With :dedupe :path or :none, each occurrence is evaluated on its own instead of once per key.

Propagation

propagate is for information that must be combined where routes meet and sent on again when it changes. Give it initial values and a function that joins a state's current value with one that arrives:

(def flow
  {:database [:api]
   :api      [:worker]
   :worker   [:api]})

(:values (last (ss/propagate flow
                             {:database #{:sql}, :worker #{:jobs}}
                             into)))
;; => {:database #{:sql}, :worker #{:sql :jobs}, :api #{:sql :jobs}}

A state reached for the first time takes the arriving value; later arrivals are joined with what it has. A state whose value changed is processed again, so information travels around the cycle between :api and :worker until nothing changes. The result is a lazy sequence of progress records; the last holds the final values. Propagation ends only if values stop changing, which depends on your join and your space. Because the records are lazy, you can also take a bounded number of them and see whether it has ended.

To transform values on the way, let the space read the value and return transitions with their own :value, by passing the options {:project identity :decode-edge identity} after the join.

Tracing

state-space.trace has the same four searches. They take the same arguments and return the steps of the search as events instead of its visits:

(require '[state-space.trace :as trace])

(map (juxt :event (comp :state :visit))
     (trace/dfs {:root [:left :right]} [:root]))
;; => ([:start :root] [:enter :root]
;;     [:edge :left] [:enter :left] [:exit :left]
;;     [:edge :right] [:enter :right] [:exit :right]
;;     [:exit :root])

:start and :edge events report each candidate with :accepted?, and a :reason when it is rejected:

(filter :reason (trace/bfs graph [:start]))
;; => ({:event :edge, :from {:state :right}, :transition {:state :goal},
;;      :visit {:state :goal}, :accepted? false, :reason :already-visited})

The :enter events are exactly the visits that dfs, bfs, and best-first return; the :exit events of trace/dfs and trace/postorder are the visits of postorder.

In a depth-first trace, the reason :on-path marks an edge back to a visit that is still being explored. Such an edge closes a cycle, and the path extension shows it:

(->> (trace/dfs {:a [:b] :b [:c] :c [:a]} [:a] {:extensions [ss/path]})
     (filter #(= :on-path (:reason %)))
     (map (comp :path :visit)))
;; => ([:a :b :c :a])

Checked arguments

Arguments are checked when you call an operation, before anything runs. An unknown option, a value of the wrong shape, or starting states that are not a collection throw an ExceptionInfo. Its data name the :function and the :option (or :argument) at fault:

(try (ss/bfs graph [:start] {:extension [ss/path]})
     (catch clojure.lang.ExceptionInfo error
       (select-keys (ex-data error) [:function :option])))
;; => {:function state-space.core/bfs, :option :extension}

Its message reads: unknown option :extension. Supported options: :decode-edge, :dedupe, :expand?, :extensions, :project, :visit-key.

What a callback returns can only be checked when it runs. A decoder result without :state, an extension that replaces :state, a negative weight in a least-cost search, or a priority of nil fails in the same way when the search reaches it, instead of producing wrong visits.

Composing searches

A search is an ordinary lazy sequence, so it can be a step of something larger. The worked examples build iterative deepening with mapcat, bidirectional search with partition-by, and maximum flow with iterate, each around the searches above and without further operations.

When not to use it

A small tree walk may be clearer as a recursive function, and a dynamic program with an obvious evaluation order as a reduce. State-space earns its place when you want to describe successors and a computation without also writing the traversal: deduplication, laziness, route context, stack safety, and revisiting through cycles.

Development

clojure -M:test                 # run the tests, including every documented example
clojure -M:bench                # benchmark the public operations
clojure -M:standard-bench       # compare with direct Clojure implementations

The benchmark files document their options and workloads.

API stability

The API is still evolving before 1.0.0, and releases may change it. Pin the version you have tested and read CHANGELOG.md before upgrading.

License

MIT