Path consistency over a relation algebra {:universe :identity :compose :converse} and
a network {[i j] → #{base relations}}, both directions stored, an unrecorded pair the
universe. Pure data: no KB, context or belief. A pass runs over bitmasks and answers
relation sets. See docs/qcn.md.
Path consistency over a relation algebra `{:universe :identity :compose :converse}` and
a network `{[i j] → #{base relations}}`, both directions stored, an unrecorded pair the
universe. Pure data: no KB, context or belief. A pass runs over bitmasks and answers
relation sets. See docs/qcn.md.(constraint net {:keys [universe identity]} i j)The constraint on [i j] in net under algebra: the identity on the diagonal,
the recorded set, else the universe (unknown).
The constraint on `[i j]` in `net` under `algebra`: the identity on the diagonal, the recorded set, else the universe (unknown).
(narrowing-of? net prior {:keys [universe]})Is net a pointwise narrowing of prior: is every pair's constraint at most as wide,
a pair net does not record being the universe? The precondition of
path-consistent-from, checked by the caller against the network prior's answer was
computed from.
Is `net` a pointwise narrowing of `prior`: is every pair's constraint at most as wide, a pair `net` does not record being the universe? The precondition of `path-consistent-from`, checked by the caller against the network `prior`'s answer was computed from.
(path-consistent net nodes algebra)Enforce composition closure over net across nodes: for every triple (i j k),
tighten R(i,k) ∩= R(i,j)∘R(j,k), to the greatest fixpoint below net. Returns the
tightened network, or :inconsistent when a constraint empties or one is unsatisfiable
as given (unsatisfiable-as-given?, over the whole network whatever nodes holds).
Each constraint is a subset of the algebra's universe. nodes must name every node
the network mentions: a node left out takes part in no triple. Extra nodes change
nothing, and the order of nodes changes nothing.
Enforce composition closure over `net` across `nodes`: for every triple (i j k), tighten R(i,k) ∩= R(i,j)∘R(j,k), to the greatest fixpoint below `net`. Returns the tightened network, or `:inconsistent` when a constraint empties or one is unsatisfiable as given (`unsatisfiable-as-given?`, over the whole network whatever `nodes` holds). Each constraint is a subset of the algebra's universe. `nodes` must name every node the network mentions: a node left out takes part in no triple. Extra nodes change nothing, and the order of `nodes` changes nothing.
(path-consistent-from net prior nodes algebra)path-consistent for net, warm-started from prior, the answer for an earlier
network net narrows (narrowing-of?): it closes prior ∩ net, revisiting only the
triples reading a pair where net is stricter. nodes need name only the nodes
neither network mentions; the rest are read off the merged network. A prior that
fails the precondition, or comes from another algebra, yields a network tighter than
net licenses.
`path-consistent` for `net`, warm-started from `prior`, the answer for an earlier network `net` narrows (`narrowing-of?`): it closes `prior ∩ net`, revisiting only the triples reading a pair where `net` is stricter. `nodes` need name only the nodes neither network mentions; the rest are read off the merged network. A `prior` that fails the precondition, or comes from another algebra, yields a network tighter than `net` licenses.
(path-consistent-naive net nodes algebra)path-consistent by repeated full sweeps of every triple: the same arguments and
answer, kept as the reference qcn_queue_test holds the arc queue against.
`path-consistent` by repeated full sweeps of every triple: the same arguments and answer, kept as the reference `qcn_queue_test` holds the arc queue against.
(path-consistent-with-support net support nodes algebra)path-consistent, carrying support from the asserted support {[i j] → #{handle}}:
a tightened constraint's support is its own prior support and that of the two
constraints that narrowed it. Returns {:network … :support …}, or
{:inconsistent [i j] :culprits #{handle}} for the pair that emptied. The support is
one witness, not minimal and not every derivation, and every handle in it was read into
the network (docs/qcn.md, "Support").
`path-consistent`, carrying support from the asserted `support` `{[i j] → #{handle}}`:
a tightened constraint's support is its own prior support and that of the two
constraints that narrowed it. Returns `{:network … :support …}`, or
`{:inconsistent [i j] :culprits #{handle}}` for the pair that emptied. The support is
one witness, not minimal and not every derivation, and every handle in it was read into
the network (docs/qcn.md, "Support").(unsatisfiable-pairs net {:keys [identity]})The pairs of net unsatisfiable before any tightening (unsatisfiable-as-given?).
Empty when only composition empties a constraint.
The pairs of `net` unsatisfiable before any tightening (`unsatisfiable-as-given?`). Empty when only composition empties a constraint.
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 |