Tempo.Interval.RelationNetwork (Tempo Network v1.0.0)

Copy Markdown View Source

A qualitative constraint network over Allen relations, with the path-consistency propagation of Allen (1983) §3.

Where every interval is dated, Tempo.relation/2 answers directly. This module is for the case where they are not: you know how some periods relate to each other, not when any of them happened, and want to know what follows. Each pair of periods carries a set of the relations still possible; asserting a constraint narrows a set, and propagation narrows every other set that the assertion implies.

Not Tempo.Network

Tempo.Network solves the Simple Temporal Problem — metric constraints (at_least: 20, unit: :year) over dated periods, by shortest paths. It is complete and polynomial, and its relation vocabulary is convex: it cannot represent "before or after".

This module is the qualitative counterpart. It has no dates and no metric constraints, and it can represent disjunction — which is exactly why it is incomplete (below). Use Tempo.Network when you have bounds and want dates; use this when you have relations and want relations.

Sound but incomplete

propagate/1 computes path consistency, not satisfiability.

  • Every relation it removes is genuinely impossible. Pruning is sound, so a surviving set is an over-approximation you can trust as an upper bound on what might hold.

  • A network that propagates cleanly may still be unsatisfiable. Deciding satisfiability for the full algebra is NP-complete (Vilain & Kautz 1986; Nebel & Bürckert 1995), and path consistency is the standard polynomial approximation.

So {:ok, network} means "no contradiction was found", not "a consistent assignment exists". {:error, {:inconsistent, pair}} is definitive in the other direction: an empty set is a real contradiction.

Example

iex> alias Tempo.Interval.RelationNetwork, as: Net
iex> net =
...>   Net.new([:fire, :rebuild, :occupation])
...>   |> Net.constrain(:fire, [:precedes], :rebuild)
...>   |> Net.constrain(:rebuild, [:during], :occupation)
iex> {:ok, net} = Net.propagate(net)
iex> Net.between(net, :fire, :occupation)
[:precedes, :meets, :overlaps, :starts, :during]

The fire precedes the rebuild, and the rebuild happened during the occupation — so the fire is somewhere before the occupation ended, but which of those five relations holds is not determined by what was asserted.

Summary

Types

label()
relations()

A set of Allen's relations, in Allen's order: what may hold between two intervals.

t()

Functions

between(network, a, b)

The relations still possible from a to b.

consistent?(network)

Whether propagation finds no contradiction.

constrain(network, a, relations, b)

Narrow what is possible from a to b by relations.

new(labels)

A network over labels, with nothing asserted between any pair.

propagate(network)

Propagate every constraint to a fixpoint.

Types

label()

@type label() :: term()

relations()

@type relations() :: [atom()]

A set of Allen's relations, in Allen's order: what may hold between two intervals.

t()

@type t() :: %Tempo.Interval.RelationNetwork{
  edges: %{required({label(), label()}) => relations()},
  labels: [label()]
}

Functions

between(network, a, b)

@spec between(t(), label(), label()) ::
  relations() | {:error, {:unknown_label, label()}}

The relations still possible from a to b.

Arguments

  • network is a t/0.

  • a and b are labels in the network.

Returns

  • The relation set, in Allen's canonical order.

  • [:equals] when a and b are the same label.

  • {:error, {:unknown_label, label}} when a label is not in the network.

Examples

iex> net = Tempo.Interval.RelationNetwork.new([:a, :b])
iex> net = Tempo.Interval.RelationNetwork.constrain(net, :a, [:meets], :b)
iex> Tempo.Interval.RelationNetwork.between(net, :a, :b)
[:meets]

iex> net = Tempo.Interval.RelationNetwork.new([:a, :b])
iex> Tempo.Interval.RelationNetwork.between(net, :a, :zzz)
{:error, {:unknown_label, :zzz}}

consistent?(network)

@spec consistent?(t()) :: boolean()

Whether propagation finds no contradiction.

Arguments

  • network is a t/0.

Returns

  • true when propagate/1 succeeds, false when it reports an inconsistency. A true result is not proof of satisfiability — see the module docs.

Examples

iex> alias Tempo.Interval.RelationNetwork, as: Net
iex> Net.new([:a, :b])
...> |> Net.constrain(:a, [:precedes], :b)
...> |> Net.consistent?()
true

iex> alias Tempo.Interval.RelationNetwork, as: Net
iex> Net.new([:a, :b])
...> |> Net.constrain(:a, [:precedes], :b)
...> |> Net.constrain(:a, [:preceded_by], :b)
...> |> Net.consistent?()
false

constrain(network, a, relations, b)

@spec constrain(t(), label(), relations(), label()) ::
  t() | {:error, {:unknown_label, label()} | {:invalid_relation, term()}}

Narrow what is possible from a to b by relations.

Constraints accumulate: asserting twice narrows twice, and asserting something already known changes nothing. The inverse is recorded on the reverse pair automatically, so constrain(net, a, [:precedes], b) also establishes that b is preceded by a.

This records the assertion only. Call propagate/1 to draw out what it implies for other pairs.

Arguments

  • network is a t/0.

  • a and b are labels in the network.

  • relations is the set of relations to narrow by.

Returns

  • The updated t/0.

  • {:error, {:unknown_label, label}} when a label is not in the network.

  • {:error, {:invalid_relation, term}} when relations holds something that is not one of the thirteen.

Examples

iex> alias Tempo.Interval.RelationNetwork, as: Net
iex> net =
...>   Net.new([:a, :b])
...>   |> Net.constrain(:a, [:precedes, :meets], :b)
iex> Net.between(net, :b, :a)
[:met_by, :preceded_by]

Asserting a second constraint narrows rather than replaces:

iex> alias Tempo.Interval.RelationNetwork, as: Net
iex> net =
...>   Net.new([:a, :b])
...>   |> Net.constrain(:a, [:precedes, :meets], :b)
...>   |> Net.constrain(:a, [:meets, :overlaps], :b)
iex> Net.between(net, :a, :b)
[:meets]

new(labels)

@spec new([label()]) :: t()

A network over labels, with nothing asserted between any pair.

Every pair starts as the full set of thirteen relations — the state of knowing nothing — and every period equals itself.

Arguments

  • labels is a list of period identifiers. Any term may be a label.

Returns

Examples

iex> net = Tempo.Interval.RelationNetwork.new([:a, :b])
iex> Tempo.Interval.RelationNetwork.between(net, :a, :b)
...> |> length()
13

iex> net = Tempo.Interval.RelationNetwork.new([:a, :b])
iex> Tempo.Interval.RelationNetwork.between(net, :a, :a)
[:equals]

propagate(network)

@spec propagate(t()) :: {:ok, t()} | {:error, {:inconsistent, {label(), label()}}}

Propagate every constraint to a fixpoint.

Allen's §3 path consistency: for every triple, the relations possible from i to k are narrowed by what a step through j allows — R(i,k) ← R(i,k) ∩ (R(i,j) ∘ R(j,k)) — repeated until nothing changes.

Read the module docs before trusting the result: pruning is sound, but a clean pass is not proof of consistency.

Arguments

  • network is a t/0.

Returns

  • {:ok, network} with every set narrowed as far as path consistency reaches. No contradiction was found.

  • {:error, {:inconsistent, {a, b}}} when some pair narrowed to the empty set. That is definitive: the constraints cannot all hold.

Examples

iex> alias Tempo.Interval.RelationNetwork, as: Net
iex> net =
...>   Net.new([:a, :b, :c])
...>   |> Net.constrain(:a, [:precedes], :b)
...>   |> Net.constrain(:b, [:precedes], :c)
iex> {:ok, net} = Net.propagate(net)
iex> Net.between(net, :a, :c)
[:precedes]

A cycle that cannot be satisfied is reported:

iex> alias Tempo.Interval.RelationNetwork, as: Net
iex> net =
...>   Net.new([:a, :b, :c])
...>   |> Net.constrain(:a, [:precedes], :b)
...>   |> Net.constrain(:b, [:precedes], :c)
...>   |> Net.constrain(:c, [:precedes], :a)
iex> {:error, {:inconsistent, _pair}} = Net.propagate(net)