# `Tempo.Network.Solver`
[🔗](https://github.com/kipcole9/tempo/blob/v0.20.0/lib/tempo/network/solver.ex#L1)

Consistency checking and bound tightening for a chronological
network, by solving its Simple Temporal Problem.

The network normalises (`Tempo.Network.Normalize`) 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?

* `tighten/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.

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

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

### Examples

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

# `contemporaneity`

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

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 (tightened)
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; or

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

### Examples

    iex> network =
    ...>   Tempo.Network.new()
    ...>   |> Tempo.Network.add_period(:k1, start: {:not_before, 1200}, duration: {:at_most, 15})
    ...>   |> Tempo.Network.add_period(:k2, end: {: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`.

# `relation`

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

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
grounded values. It reads off the **minimal network** — the same solved
shortest-path distances `contemporaneity/3` and `tighten/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, or
  `{:error, :unknown_period}` when an id is not in the network.

### Examples

    iex> Tempo.Network.new()
    ...> |> Tempo.Network.add_period(:a, start: ~o"1200Y", end: ~o"1250Y")
    ...> |> Tempo.Network.add_period(:b, start: ~o"1230Y", end: ~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}
```

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

The network counterpart of `Tempo.relation_certainty/3` on grounded `±`-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, start: ~o"1200Y", end: ~o"1250Y")
    ...>   |> Tempo.Network.add_period(:b, start: ~o"1230Y", end: ~o"1280Y")
    iex> Tempo.Network.Solver.relation_certainty(net, :a, :b, :overlaps)
    :certain
    iex> Tempo.Network.Solver.relation_certainty(net, :a, :b, :during)
    :impossible

# `tighten`

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

Tighten every period's start, end, and duration to the narrowest
bounds the network implies.

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

### Examples

    iex> {:ok, tightened} =
    ...>   Tempo.Network.new()
    ...>   |> Tempo.Network.add_period(:k1, start: ~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.tighten()
    iex> tightened.periods[:k2].earliest_end
    ~o"1255Y"

# `trace`

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

Explain a tightened 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

* `: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;
  or

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

### Examples

    iex> {:ok, trace} =
    ...>   Tempo.Network.new()
    ...>   |> Tempo.Network.add_period(:k1, start: {: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*