# `Tempo.Interval.RelationNetwork`
[🔗](https://github.com/elixir-tempo/tempo_network/blob/v1.0.0/lib/tempo/interval/relation_network.ex#L1)

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.

# `label`

```elixir
@type label() :: term()
```

# `relations`

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

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

# `t`

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

# `between`

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

The relations still possible from `a` to `b`.

### Arguments

* `network` is a `t: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?`

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

Whether propagation finds no contradiction.

### Arguments

* `network` is a `t: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`

```elixir
@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:t/0`.

* `a` and `b` are labels in the network.

* `relations` is the set of relations to narrow by.

### Returns

* The updated `t: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`

```elixir
@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

* A `t:t/0`.

### 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`

```elixir
@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: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)

---

*Consult [api-reference.md](api-reference.md) for complete listing*