# `Tempo.Network.Solver`
[🔗](https://github.com/elixir-tempo/tempo_network/blob/v1.0.0/lib/tempo/network/solver.ex#L1)

Consistency checking and constraint propagation for a chronological
network, by solving its Simple Temporal Problem.

The network normalises to a directed
weighted graph — one node per boundary plus the origin `z₀` — whose
all-pairs shortest paths are the **minimal network**: the tightest
bound on `b₁ − b₂` is the shortest-path weight `b₁ → b₂` (Dechter,
Meiri & Pearl 1991; the paper's Floyd 1962). The network is
**consistent** iff the graph has no negative cycle.

* `consistent?/1` — does any valid assignment of dates exist?

* `propagate/1` — the narrowest start, end, and duration each period
  can take given every constraint together.

* `contemporaneity/3` — whether two periods can, must, or cannot overlap.

* `relation/3` — the tightest Allen relation(s) still possible between two
  periods, with `relation_certainty/4` for a single named relation.

These all run in O(n³) on the boundary count (Floyd–Warshall), which is
interactive for the hundreds of periods these chronologies contain. A
duration in a unit coarser than the network's axis (a year in a network
of days) is measured by its actual length from where its period can
start, and the network is solved again as those lengths narrow, until
they settle.

A network whose builders recorded an error (see `Tempo.Network`), or one
it cannot place (a unit finer than a second, floating and zoned bounds
in one network of hours, a fraction of its unit),
returns that error from every function here, and the predicates raise
it.

# `certainly_contemporary?`

```elixir
@spec certainly_contemporary?(Tempo.Network.t(), term(), term()) :: boolean()
```

Whether two periods are *certainly* contemporary — true only when
every valid chronology has them overlapping. See `contemporaneity/3`.

### Arguments

* `network` is a `t:Tempo.Network.t/0`.

* `p1` and `p2` are ids of periods present in the network.

### Returns

* `true` when every valid chronology has the periods overlapping.

* `false` otherwise, or when the network has no valid chronology.

* It raises the exception the network's builders recorded, where they
  recorded one.

### Examples

    iex> network =
    ...>   Tempo.Network.new()
    ...>   |> Tempo.Network.add_period(:k1, from: {:not_before, 1200}, duration: {:at_most, 15})
    ...>   |> Tempo.Network.add_period(:k2, to: {:not_after, 1300}, duration: {30, 100})
    ...>   |> Tempo.Network.add_period(:s1, duration: {20, 100})
    ...>   |> Tempo.Network.add_period(:s2, duration: {20, 100})
    ...>   |> Tempo.Network.add_sequence([:k1, :k2])
    ...>   |> Tempo.Network.add_sequence([:s1, :s2])
    ...>   |> Tempo.Network.add_relation(:starts_during, :s1, :k1)
    ...>   |> Tempo.Network.add_relation(:ends_during, :s2, :k2)
    iex> Tempo.Network.Solver.certainly_contemporary?(network, :k1, :s1)
    true

# `consistent?`

```elixir
@spec consistent?(Tempo.Network.t()) :: boolean()
```

Is the network consistent — does it admit at least one valid
assignment of dates?

### Arguments

* `network` is a `t:Tempo.Network.t/0`.

### Returns

* `true` when consistent, `false` when the constraints contradict
  (the graph has a negative cycle).

* Raises the first error the network's builders recorded.

### Examples

    iex> Tempo.Network.new()
    ...> |> Tempo.Network.add_period(:k, from: ~o"1200Y", to: ~o"1180Y")
    ...> |> Tempo.Network.Solver.consistent?()
    false

# `contemporaneity`

```elixir
@spec contemporaneity(Tempo.Network.t(), term(), term()) ::
  :certain | :possible | :impossible | {:error, :inconsistent | Exception.t()}
```

Classify whether two periods overlap in time, given the whole network.

Returns `:certain` when the constraints force the periods to be
contemporary, `:possible` when they merely allow it, and `:impossible`
when they forbid it. The verdict is read from the minimal (propagated)
network, so it accounts for every constraint — not just the two
periods' own bounds — in the spirit of Geeraerts, Levy & Pluquet,
*Models and Algorithms for Chronology* (TIME 2017), Props. 7 and 10.

Two periods that merely touch (one ends exactly where the other
begins) count as contemporary, matching `add_relation(:contemporary,
…)` — the endpoints are treated as closed here.

### Arguments

* `network` is a `t:Tempo.Network.t/0`.

* `p1` and `p2` are ids of periods present in the network.

### Returns

* `:certain` when every valid chronology has the periods overlapping;

* `:possible` when some but not all valid chronologies do;

* `:impossible` when none do;

* `{:error, :inconsistent}` when the network has no valid chronology;
  or

* `{:error, reason}` for an error the network's builders recorded.

### Examples

    iex> network =
    ...>   Tempo.Network.new()
    ...>   |> Tempo.Network.add_period(:k1, from: {:not_before, 1200}, duration: {:at_most, 15})
    ...>   |> Tempo.Network.add_period(:k2, to: {:not_after, 1300}, duration: {30, 100})
    ...>   |> Tempo.Network.add_period(:s1, duration: {20, 100})
    ...>   |> Tempo.Network.add_period(:s2, duration: {20, 100})
    ...>   |> Tempo.Network.add_sequence([:k1, :k2])
    ...>   |> Tempo.Network.add_sequence([:s1, :s2])
    ...>   |> Tempo.Network.add_relation(:starts_during, :s1, :k1)
    ...>   |> Tempo.Network.add_relation(:ends_during, :s2, :k2)
    iex> Tempo.Network.Solver.contemporaneity(network, :k1, :s2)
    :impossible

# `possibly_contemporary?`

```elixir
@spec possibly_contemporary?(Tempo.Network.t(), term(), term()) :: boolean()
```

Whether two periods are *possibly* contemporary — true when at least
one valid chronology has them overlapping. See `contemporaneity/3`.

### Arguments

* `network` is a `t:Tempo.Network.t/0`.

* `p1` and `p2` are ids of periods present in the network.

### Returns

* `true` when at least one valid chronology has the periods overlapping.

* `false` otherwise, or when the network has no valid chronology.

* It raises the exception the network's builders recorded, where they
  recorded one.

### Examples

    iex> network =
    ...>   Tempo.Network.new()
    ...>   |> Tempo.Network.add_period(:k1, from: {:not_before, 1200}, duration: {:at_most, 15})
    ...>   |> Tempo.Network.add_period(:k2, to: {:not_after, 1300}, duration: {30, 100})
    ...>   |> Tempo.Network.add_period(:s1, duration: {20, 100})
    ...>   |> Tempo.Network.add_period(:s2, duration: {20, 100})
    ...>   |> Tempo.Network.add_sequence([:k1, :k2])
    ...>   |> Tempo.Network.add_sequence([:s1, :s2])
    ...>   |> Tempo.Network.add_relation(:starts_during, :s1, :k1)
    ...>   |> Tempo.Network.add_relation(:ends_during, :s2, :k2)
    iex> Tempo.Network.Solver.possibly_contemporary?(network, :k1, :s2)
    false

# `propagate`

```elixir
@spec propagate(Tempo.Network.t()) ::
  {:ok, Tempo.Network.t()} | {:error, :inconsistent | Exception.t()}
```

Propagate the network's constraints to every period's narrowest
start, end, and duration.

### Arguments

* `network` is a `t:Tempo.Network.t/0`.

### Returns

* `{:ok, network}` with each period's bounds replaced by the computed
  tightest bounds (a bound that the constraints leave unbounded
  becomes `nil`); or

* `{:error, :inconsistent}` when no valid assignment exists; or

* `{:error, reason}` for an error the network's builders recorded.

### Examples

    iex> {:ok, propagated} =
    ...>   Tempo.Network.new()
    ...>   |> Tempo.Network.add_period(:k1, from: ~o"1200Y", duration: {:at_least, ~o"P20Y"})
    ...>   |> Tempo.Network.add_period(:k2, duration: {:at_least, ~o"P35Y"})
    ...>   |> Tempo.Network.add_sequence([:k1, :k2])
    ...>   |> Tempo.Network.Solver.propagate()
    iex> propagated.periods[:k2].earliest_end
    ~o"1255Y"

# `relation`

```elixir
@spec relation(Tempo.Network.t(), term(), term()) ::
  atom() | [atom()] | {:error, :inconsistent | :unknown_period | Exception.t()}
```

The Allen interval relation(s) still possible between two periods, given
every constraint in the network.

Generalises `contemporaneity/3` from the single overlap question to the full
relational answer, in the same vocabulary `Tempo.relation/2` uses for
dated values. It reads off the **minimal network** — the same solved
shortest-path distances `contemporaneity/3` and `propagate/1` use — so it costs
no extra solve: a relation is possible iff adding its endpoint constraints to
the solved network stays consistent (no negative cycle). No qualitative
disjunction enters, so it remains polynomial.

Periods are treated as proper intervals (start strictly before end), matching
Tempo's no-degenerate-intervals ontology, and endpoints are compared
half-open — so "the end of A coincides with the start of B" is `:meets`, not
overlap. (That boundary case is still `possibly_contemporary?/3`, which asks
the looser "could they have coexisted" question.)

### Arguments

* `network` is a `t:Tempo.Network.t/0`.

* `p1` and `p2` are period identifiers added with `Tempo.Network.add_period/3`.

### Returns

* A single Allen relation atom (e.g. `:during`) when the constraints pin the
  relation to exactly one — it is *entailed*.

* A list of atoms (in Allen's canonical order) when several remain possible —
  the tightest qualitative statement the constraints support.

* `{:error, :inconsistent}` when the network has no valid assignment,
  `{:error, :unknown_period}` when an id is not in the network, or
  `{:error, reason}` for an error the network's builders recorded.

### Examples

    iex> Tempo.Network.new()
    ...> |> Tempo.Network.add_period(:a, from: ~o"1200Y", to: ~o"1250Y")
    ...> |> Tempo.Network.add_period(:b, from: ~o"1230Y", to: ~o"1280Y")
    ...> |> Tempo.Network.Solver.relation(:a, :b)
    :overlaps

    iex> Tempo.Network.new()
    ...> |> Tempo.Network.add_period(:a, duration: {:at_least, ~o"P1Y"})
    ...> |> Tempo.Network.add_period(:b, duration: {:at_least, ~o"P1Y"})
    ...> |> Tempo.Network.add_sequence([:a, :b])
    ...> |> Tempo.Network.Solver.relation(:a, :b)
    :meets

# `relation_certainty`

```elixir
@spec relation_certainty(Tempo.Network.t(), term(), term(), atom()) ::
  :certain
  | :possible
  | :impossible
  | {:error, :inconsistent | :unknown_period | Exception.t()}
```

Whether a specific Allen `relation` between two periods is `:certain`,
`:possible`, or `:impossible` under the network's constraints.

The network counterpart of `Tempo.certainty/3` on dated `±`-margin
values — the same three-valued vocabulary, read from the solved network via
`relation/3`. A relation is `:certain` when it is the *only* one the
constraints allow, `:possible` when it is one of several, `:impossible` when
ruled out.

### Arguments

* `network`, `p1`, `p2` — as for `relation/3`.

* `relation` is an Allen relation atom (e.g. `:during`, `:precedes`).

### Returns

* `:certain | :possible | :impossible`, or `{:error, reason}` as `relation/3`.

### Examples

    iex> net =
    ...>   Tempo.Network.new()
    ...>   |> Tempo.Network.add_period(:a, from: ~o"1200Y", to: ~o"1250Y")
    ...>   |> Tempo.Network.add_period(:b, from: ~o"1230Y", to: ~o"1280Y")
    iex> Tempo.Network.Solver.relation_certainty(net, :a, :b, :overlaps)
    :certain
    iex> Tempo.Network.Solver.relation_certainty(net, :a, :b, :during)
    :impossible

# `trace`

```elixir
@spec trace(Tempo.Network.t(), {:start | :end, term()}, keyword()) ::
  {:ok, map()} | {:error, :unbounded | :inconsistent | Exception.t()}
```

Explain a propagated bound as a trace — the chain of constraints that
forces it.

Reconstructs the shortest path in the constraint graph that produces
the `:earliest` or `:latest` value of a boundary, mirroring the
paper's Fig. 6c. Each step names the constraint responsible and the
bound derived so far, and `:prose` renders the whole chain as a
sentence.

### Arguments

* `network` is a `t:Tempo.Network.t/0`.

* `boundary` is `{:start, period_id}` or `{:end, period_id}`.

* `options` is a keyword list of options.

### Options

* `:bound` is `:earliest` (the default) or `:latest`.

### Returns

* `{:ok, %{value: t:Tempo.t/0, steps: list, prose: String.t()}}`;

* `{:error, :unbounded}` when the constraints leave the bound open;

* `{:error, :inconsistent}` when the network has no valid assignment;
  or

* `{:error, reason}` for an error the network's builders recorded, a
  boundary that is not `{:start, id}` or `{:end, id}`, or an option
  `trace/3` does not take.

### Examples

    iex> {:ok, trace} =
    ...>   Tempo.Network.new()
    ...>   |> Tempo.Network.add_period(:k1, from: {:not_before, ~o"1200Y"}, duration: {:at_least, ~o"P20Y"})
    ...>   |> Tempo.Network.add_period(:k2, duration: {:at_least, ~o"P35Y"})
    ...>   |> Tempo.Network.add_sequence([:k1, :k2])
    ...>   |> Tempo.Network.Solver.trace({:end, :k2})
    iex> trace.value
    ~o"1255Y"

---

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