Scenario extraction over a qualitative constraint network — turning "here is what is still possible" into "here is one way it could be".
Path consistency leaves a set of relations on every pair. That is the right answer to what is entailed, and the wrong shape for a caller that wants a concrete arrangement: a drawing of the regions, a timeline of the intervals, an example to show someone. A scenario is one consistent choice of a single base relation for every pair — a singleton-valued network that survives path consistency, and so an arrangement nothing believed rules out.
The search is ordinary backtracking, with the two refinements that make it bearable: fewest possibilities first, so the most constrained pair is decided while it is still cheap to be wrong about it, and re-tighten after every choice, so a decision that empties some other pair is caught at once rather than at the leaf.
Calculus-generic. It takes a vaelii.impl.qcn-kb calculus, so it works for RCC-8
topology, cardinal direction, Allen's intervals, the point algebra and anything added
later, with no line of it aware of which. Everything it needs is on qcn and qcn-kb's
public surface: the network, its nodes, a constraint, and the pass.
Deterministic. The same believed facts yield the same scenario every time, and two KBs built by asserting the same facts in a different order yield the same scenario as each other. Both orderings the search makes — which pair to decide next, and which relation to try first — break their ties on content: nodes and relations are ordered by how they are written, never by a handle id or by map iteration order. Handles are allocated in assertion order, so keying on one would smuggle that order into the answer, which is what the whole engine forbids.
The count is exponential, so nothing here enumerates eagerly. scenarios is a lazy
sequence — one scenario costs one path down the search tree, not the tree — and takes a
:limit for a caller that would rather say how many it wants than remember to bound the
sequence itself. See docs/scenario.md.
Scenario extraction over a qualitative constraint network — turning "here is what is still possible" into "here is one way it could be". Path consistency leaves a *set* of relations on every pair. That is the right answer to what is entailed, and the wrong shape for a caller that wants a concrete arrangement: a drawing of the regions, a timeline of the intervals, an example to show someone. A **scenario** is one consistent choice of a single base relation for *every* pair — a singleton-valued network that survives path consistency, and so an arrangement nothing believed rules out. The search is ordinary backtracking, with the two refinements that make it bearable: **fewest possibilities first**, so the most constrained pair is decided while it is still cheap to be wrong about it, and **re-tighten after every choice**, so a decision that empties some *other* pair is caught at once rather than at the leaf. **Calculus-generic.** It takes a `vaelii.impl.qcn-kb` calculus, so it works for RCC-8 topology, cardinal direction, Allen's intervals, the point algebra and anything added later, with no line of it aware of which. Everything it needs is on `qcn` and `qcn-kb`'s public surface: the network, its nodes, a constraint, and the pass. **Deterministic.** The same believed facts yield the same scenario every time, and two KBs built by asserting the same facts in a different order yield the same scenario as each other. Both orderings the search makes — which pair to decide next, and which relation to try first — break their ties on **content**: nodes and relations are ordered by how they are written, never by a handle id or by map iteration order. Handles are allocated in assertion order, so keying on one would smuggle that order into the answer, which is what the whole engine forbids. **The count is exponential**, so nothing here enumerates eagerly. `scenarios` is a lazy sequence — one scenario costs one path down the search tree, not the tree — and takes a `:limit` for a caller that would rather say how many it wants than remember to bound the sequence itself. See docs/scenario.md.
(relations scen)A scenario read as {[i j] → relation}, the singletons unwrapped. The network form is
what composes with qcn; this is what reads.
A scenario read as `{[i j] → relation}`, the singletons unwrapped. The network form is
what composes with `qcn`; this is what reads.(scenario calc kb context)One scenario of calc consistent with what is believed in context — a concrete
arrangement of every pair — or nil when the believed facts are unsatisfiable.
Which one is a function of the facts alone: the search is deterministic, so this is repeatable and comparable across KBs.
One scenario of `calc` consistent with what is believed in `context` — a concrete arrangement of every pair — or nil when the believed facts are unsatisfiable. Which one is a function of the facts alone: the search is deterministic, so this is repeatable and comparable across KBs.
(scenarios calc kb context)(scenarios calc kb context {:keys [limit]})Every scenario of calc consistent with what is believed in context, as a lazy
sequence of singleton-valued networks {[i j] → #{relation}}, both directions written.
Lazy on purpose: the number of scenarios is exponential in the node count, so realizing
the sequence in full is not something a caller should do by accident. Take what you need,
or pass {:limit n} and let this do the taking.
Empty when the believed facts are unsatisfiable — an arrangement nothing rules out cannot exist when everything is ruled out. A context with fewer than two nodes has exactly one scenario, the empty one, since there is no pair to decide.
Every scenario of `calc` consistent with what is believed in `context`, as a **lazy**
sequence of singleton-valued networks `{[i j] → #{relation}}`, both directions written.
Lazy on purpose: the number of scenarios is exponential in the node count, so realizing
the sequence in full is not something a caller should do by accident. Take what you need,
or pass `{:limit n}` and let this do the taking.
Empty when the believed facts are unsatisfiable — an arrangement nothing rules out cannot
exist when everything is ruled out. A context with fewer than two nodes has exactly one
scenario, the empty one, since there is no pair to decide.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 |