---
# YAML header created by ox-ravel
title: "Allen's interval algebra"
author: "Thomas S. Dye"
date: "`r Sys.Date()`"
output:
  html_document:
    fig_caption: false
    toc: true
    toc_float:
      collapsed: false
      smooth_scroll: false
    toc_depth: 3
vignette: >
  %\VignetteIndexEntry{5.ArchaeoPhases : Allen's Interval Algebra}
  %\VignetteEngine{knitr::rmarkdown}
  %\VignetteEncoding{UTF-8}
---

5. ArchaeoPhases : Allen's Interval Algebra

`=============`

\`\`\`{r, echo = FALSE, message = FALSE}
knitr::opts\_chunk$set(comment = "")
options(width = 120, max.print = 20)
library(ArchaeoPhases)

\`\`\`


## Introduction

Version \`ArchaeoPhases 1.6\` adds facilities to compute Allen's interval
algebra. This vignette provides an overview of the algebra and illustrates how
it might be used analytically and empirically, given MCMC output from a Bayesian
calibration.


## Overview of Allen's Interval Algebra

Allen's interval algebra identifies 13 basic relations that are distinct,
exhaustive, and qualitative. The algebra is defined for definite intervals whose
endpoints are single values. It can also be used with indefinite intervals whose
endpoints are not single values.

It is conventional to express an Allen relation with a notation that indicates
two intervals and a set of relations. For example, given definite intervals *A*
and *B*, where *A* precedes *B*, their Allen relation can be represented as
*A/(p)/B*. Given indefinite intervals *C* and *D*, where *C* starts before *D*
starts and ends before *D* ends, an Allen relation that expresses this
incomplete information is *C/(pmo)/D*. Note that the Allen set (pmo) in the
relation of *C* and *D* is a superset of the Allen set (p) in the relation of
*A* and *B*. In this circumstance, when two Allen sets are related as
superset/subset, the relation indicated by the superset is *weaker* and the
relation indicated by the subset is *stronger*. An Allen relation thus provides
a precise vocabulary for characterizing the state of knowledge about the
relation between two intervals, regardless of whether the intervals are definite
or indefinite.

<table id="orgdef23c0" border="2" cellspacing="0" cellpadding="6" rules="groups" frame="hsides">


<colgroup>
<col  class="org-left" />

<col  class="org-left" />

<col  class="org-left" />

<col  class="org-left" />
</colgroup>
<tbody>
<tr>
<td class="org-left">Relation</td>
<td class="org-left">&#xa0;</td>
<td class="org-left">&#xa0;</td>
<td class="org-left">Converse</td>
</tr>


<tr>
<td class="org-left">precedes</td>
<td class="org-left">(p)</td>
<td class="org-left">(P)</td>
<td class="org-left">preceded by</td>
</tr>


<tr>
<td class="org-left">meets</td>
<td class="org-left">(m)</td>
<td class="org-left">(M)</td>
<td class="org-left">met by</td>
</tr>


<tr>
<td class="org-left">overlaps</td>
<td class="org-left">(o)</td>
<td class="org-left">(O)</td>
<td class="org-left">overlapped by</td>
</tr>


<tr>
<td class="org-left">finished by</td>
<td class="org-left">(F)</td>
<td class="org-left">(f)</td>
<td class="org-left">finishes</td>
</tr>


<tr>
<td class="org-left">contains</td>
<td class="org-left">(D)</td>
<td class="org-left">(d)</td>
<td class="org-left">during</td>
</tr>


<tr>
<td class="org-left">starts</td>
<td class="org-left">(s)</td>
<td class="org-left">(S)</td>
<td class="org-left">started by</td>
</tr>


<tr>
<td class="org-left">equals</td>
<td class="org-left">(e)</td>
<td class="org-left">&#xa0;</td>
<td class="org-left">&#xa0;</td>
</tr>
</tbody>
</table>

It is often useful to visualize the basic Allen relations as a Nökel lattice. In
a Nökel lattice, the immediate neighbors of a relation differ from it in the
placement of a single interval end-point.

```{r  basic_relations }
## Load ArchaeoPhases
library(ArchaeoPhases)
## Plot the basic Allen relations
allen_illustrate("basic") 
```


## Analytic Inquiry with the Algebra

Interval algebra is carried out with a composition function that returns the relation of two intervals given their relations to a common third interval.  As implemented here, the function expects the relation of one interval to the common interval and the relation of the common interval to the remaining interval.  The function also accepts a title for the resulting Nokel lattice.

In this example, the composition function deduces that the interval represented
by a context inferior to a reference context precedes the interval represented
by a context superior to the reference context.

```{r  analyze_stratigraphy }
## Load ArchaeoPhases
library(ArchaeoPhases)
## Plot lattice for two contexts on the same line of a Harris matrix
allen_analyze("m", "m", "Composite relation of two contexts on the same line") 
```

The same lattice can be created with a convenience function.

```{r  illustrate_stratigraphy }
## Load ArchaeoPhases
library(ArchaeoPhases)
## Illustrate composite relations in a stratigraphic sequence
allen_illustrate("sequence") 
```


## Empirical Inquiry with the Algebra

Empirical inquiry with Allen's interval algebra compares intervals estimated by
Bayesian calibration of age determinations from Anglo-Saxon female burials.
First, we check for the expected result of the identity relation by comparing an
interval with itself.

```{r  identity_relation }
## Load ArchaeoPhases
library(ArchaeoPhases)
## Load the Anglo Saxon burials dataset
library(ArchaeoPhases.dataset)
library(ggplot2)
data(AngloSaxonBurials)
## Identify the burials with bead BE1-Dghnt
be1.dghnt <- c("UB-4503 (Lec148)", "UB-4506 (Lec172/2)",
"UB-6038 (CasD183)", "UB-4512 (EH091)", "UB-4501 (Lec014)",
"UB-4507 (Lec187)", "UB-4502 (Lec138)", "UB-4042 (But1674)",
"SUERC-39100 (ERL G266)")
chains <- list(list("BE1-Dghnt" = be1.dghnt,
                    "BE1-Dghnt" = be1.dghnt))
allen_observe(data = AngloSaxonBurials,
              chains = chains) 
```

Next we compare the depositional histories of two bead types recovered from
well-dated Anglo Saxon female burials in England.

Note that the Allen relation and its converse are calculated.

```{r  relation_and_converse }
## Load ArchaeoPhases
library(ArchaeoPhases)
## Load the Anglo Saxon burials dataset
library(ArchaeoPhases.dataset)
data(AngloSaxonBurials)
## Identify the burials with bead BE1-Dghnt
be1.dghnt <- c("UB-4503 (Lec148)", "UB-4506 (Lec172/2)",
"UB-6038 (CasD183)", "UB-4512 (EH091)", "UB-4501 (Lec014)",
"UB-4507 (Lec187)", "UB-4502 (Lec138)", "UB-4042 (But1674)",
"SUERC-39100 (ERL G266)")
## Identify the burials with bead BE1-CylRound
be1.cylround <- c("UB-4965 (ApD117)", "UB-4735 (Ber022)", "UB-4739 (Ber134/1)", "UB-6473 (BuD250)", "UB-6476 (BuD339)", "UB-4729 (MH068)", "UB-4835 (ApD134)", "UB-4708 (EH083)", "UB-4733 (MH095)", "UB-4888 (MelSG089)", "UB-4963 (SPTip208)", "UB-4890 (MelSG075)", "UB-4732 (MH094)", "SUERC-51539 (ERL G353)", "SUERC-51551 (ERL G193)")
chains <- list(list("BE1-Dghnt" = be1.dghnt, "BE1-CylRound" = be1.cylround), list("BE1-CylRound" = be1.cylround, "BE1-Dghnt" = be1.dghnt))
allen_observe(data = AngloSaxonBurials,
              chains = chains) 
```

It can be useful to observe the frequency with which two intervals are related
according to the relations in an Allen set. For instance, we might be interested
in which of our two beads might be the trunk from which the other branched. This
can be done by observing the frequency with which each bead type is related as
*row(oFD)col* to the other bead. The following code shows that BE1-CylRound is the
better trunk candidate.

```{r  observe_frequency }
## Load ArchaeoPhases
library(ArchaeoPhases)
## Load the Anglo Saxon burials dataset
library(ArchaeoPhases.dataset)
data(AngloSaxonBurials)
## Identify the burials with bead BE1-Dghnt
be1.dghnt <- c("UB-4503 (Lec148)", "UB-4506 (Lec172/2)",
"UB-6038 (CasD183)", "UB-4512 (EH091)", "UB-4501 (Lec014)",
"UB-4507 (Lec187)", "UB-4502 (Lec138)", "UB-4042 (But1674)",
"SUERC-39100 (ERL G266)")
## Identify the burials with bead BE1-CylRound
be1.cylround <- c("UB-4965 (ApD117)", "UB-4735 (Ber022)", "UB-4739 (Ber134/1)", "UB-6473 (BuD250)", "UB-6476 (BuD339)", "UB-4729 (MH068)", "UB-4835 (ApD134)", "UB-4708 (EH083)", "UB-4733 (MH095)", "UB-4888 (MelSG089)", "UB-4963 (SPTip208)", "UB-4890 (MelSG075)", "UB-4732 (MH094)", "SUERC-51539 (ERL G353)", "SUERC-51551 (ERL G193)")
chains <- list("BE1-Dghnt" = be1.dghnt, "BE1-CylRound" = be1.cylround)
res <- allen_observe_frequency(AngloSaxonBurials, chains, "oFD")
res$rounded.percentage 
```

