Tempo.Network.Solver (Tempo v0.10.0)

Copy Markdown View Source

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.

Both run in O(n³) on the boundary count (Floyd–Warshall), which is interactive for the hundreds of periods these chronologies contain.

Summary

Functions

consistent?(network)

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

tighten(network)

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

trace(network, boundary, options \\ [])

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

Functions

consistent?(network)

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

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

Arguments

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

tighten(network)

@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

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(network, boundary, options \\ [])

@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

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"