Qualitative Reasoning ("qualreas")

The Python module, <b>qualreas</b>, provides a framework for working with the class of <b>Relation Algebras</b> like Allen's Algebra of Time Intervals and the Region Connection Calculus (RCC). Specifically, <i>qualreas</i> provides a representation of <b>Constraint Networks</b> where the nodes represent <b>Entities</b> (Spatial, Temporal, or whatever) and the edges are labelled with <b>Relation Sets</b> (<i>relsets</i>) that represent spatio-temporal constraints between the entities.

The constraint networks in qualreas can be <b>propagated</b> to achieve <b>path consistency</b> and they can be "factored" into <b>consistent singleton networks</b>.

Algebras and Networks in qualreas can be read from, or written to, <b>JSON</b> or Python dictionary formats.

Table of Contents

• How do I get set up?
  • Testing the Installation
• Repository Description
• References
• EXAMPLES
  • Imports
  • Paths to Network & Algebra
  • Constraint Network in JSON Format
    • RCC-8's Spatial Relations
  • Instantiate the Constraint Network Object
  • Summarize the Network
  • Get Entity (Network Node)
  • Get Edge by Tail & Head Node IDs
  • The Algebra "Inside" the Network
  • Perform Constraint Propagation
    • RCC8 Example Figures
  • Singleton Labelings of a Network
  • An Example of Temporal Reasoning
  • Converting Networks to/from Other Formats
    • Network to Dictionary
    • Dictionary to Network
    • Network to JSON
      • Network to JSON File
      • Network to JSON String
  • Jupyter Notebooks
    • Introduction to Algebras
    • Derivation of Interval Algebras
      • Algebra's Derived in Reich's 1994 Paper
      • Interval & Point BINARY Branching Time Algebras
      • PROPER INTERVAL Branching Time Algebras
    • Miscellaneous Examples

How do I get set up? <a class="anchor" id="setup"></a>

With respect the Python packages that <b>qualreas</b> depends on, here are the imports from the top of the source code file, <i>qualreas.py</i>:

• from bitsets import bitset, bases (https://bitsets.readthedocs.io/en/stable/)
• import os
• import json
• import random
• import string
• import networkx as nx (https://networkx.github.io/)
• from functools import reduce
• from collections import abc, OrderedDict
• import numpy as np

All but one of the dependencies, above, will be taken care of if the Anaconda Python distribution for individuals is used.

The one additional dependency required is <b>bitsets</b>. The bitsets package is not available in the Anaconda distribution, but it can be easily added by executing the following command:

pip install bitsets

Then, use <b>git</b> to clone the <b>qualreas</b> respository.

Testing the installation <a class="anchor" id="test_install"></a>

Setup an environment variable, <b>PYPROJ</b>, that points to the directory containing <b>qualreas</b>.

Then <b>cd</b> into the directory, <b>PYPROJ/qualreas/Source</b>, and execute the following command:

python qualreas.py

This test will generate output that ends with the words, END OF TESTS.

Repository Description <a class="anchor" id="repo_desc"></a>

This is a brief description of the contents of each directory in this repository.

There is a lot here that is old and even obsolete. The important directories for now are: <b>Algebras, Networks, Notebooks, Papers, and Sources</b>. Because much has been in flux, testing & documentation has mostly been done using the notebooks (Jupyter notebooks), but not all of the notebooks have been kept up-to-date. This readme is one of the notebooks, exported to <i>markdown (md).</i>

• Algebras -- Relation Algebras in JSON format
• Docs -- INCOMPLETE (Don't look in here)
• Images -- What the title says
• LICENSE -- same
• Misc -- Assorted junk (Don't look in here)
• Networks -- Constraint Networks in JSON format
• Notebooks -- Jupyter Notebooks; A description of each can be found at the end of this notebook
• Ontologies -- The .ttl file updates the W3C.org ontology of time to correspond to the Extended_Linear_Interval_Algebra [Reich 1994]
• Papers -- A collection of papers from the relevant literature
• README.md -- This file
• Source -- Two files. The one that matters is "qualreas.py"
• Tests -- NCOMPLETE (Don't look in here)
• Trash -- Because sometimes I want to backtrack w.r.t. something I wrote
• output_*.png -- Figures used in the README

References <a class="anchor" id="refs"></a>

1. [Allen, 1983] "Maintaining Knowledge about Temporal Intervals" by James F. Allen - Allen's original paper (PDF)
2. Allen's Interval Algebra or here - summarizes Allen's algebra of proper time intervals
3. [Reich, 1994] "Intervals, Points, and Branching Time" by A.J. Reich - basis for the point & branching time extensions to Allen's algebra

EXAMPLES <a class="anchor" id="examples"></a>

In the following Jupyter Notebook examples, <b>two different types</b> of contraint algebras are demonstrated:

1. The spatial constraint algebra, Region Connection Calculus 8 (RCC8)
2. The temporal interval & point algebra defined by Reich in "Intervals, Points, and Branching Time", 1994

The examples provide brief demonstrations of a <i>qualreas</i> <b>Constraint Network</b> can be...

• represented in JSON or Python dictionary formats
• instantiated from a JSON file or Python dictionary
• serialized to a JSON file/string or Python dictionary
• summarized
• propagated
• queried for details about node and edge attributes
• used to generate all consistent singleton labellings when multiple constraints (relations) are involved

A brief look at Algebras and their components and methods is provided also.

Imports <a class="anchor" id="imports"></a>

import qualreas as qr
import os
from IPython.display import Image

Paths to Network & Algebra <a class="anchor" id="paths"></a>

To begin, we will instantiate a Constraint Network and it's corresponding Algebra from two JSON files.

Each are kept in separate directories, 'Networks' and 'Algebras', within a top-level 'qualreas' directory, with the full path defined here using an environment variable:

qr_path = os.path.join(os.getenv('PYPROJ'), 'qualreas')

Once defined, an Algebra's JSON format should remain unchanged. The name of the Algebra used by a Network can then be stored in the Network's definition (in JSON) regardless of where the Network's JSON file resides. So, we only need provide the path to the directory containing Algebra files:

alg_dir = os.path.join(qr_path, "Algebras")

Networks, on the other hand, could be numerous and change often. So, we need to provide the full path to the Network's JSON file.

rcc8_file = os.path.join(qr_path, "Networks", "rcc8_example.json")

Constraint Network in JSON Format <a class="anchor" id="network_format"></a>

Here's what a network looks like in JSON format.

A node is represented as a list of two things:

1. Node ID (i.e., Node Name)
2. List of ontology classes the node belongs to (e.g., "ProperInterval", "Region")

NOTE: Networks that are based on simple relation algebras, such as Allen's Interval Algebra and the Region Connection Calculus, only involve relations among <i>entities</i> that are all from the same ontology class, such as Proper Time Intervals or Spatial Regions. So, the <b>ontology classes of entities being related by the relations</b> does not need to be considered when, for example, composing relations. However, when ontology classes are integrated, such as Proper Time Intervals and Time Points, then the ontology classes of the entities being related become important.

An edge is represented as a list of three things, representing a directed edge, labeled with a constraint:

1. Tail Node ID
2. Head Node ID
3. Constraint

See graphical depiction below:

Image("Images/Edge_Notation_Meaning.png", width=300, height=100)

The network, shown in JSON format below, is the example from the Wikipedia page on the Region Connection Calculus (RCC8). The URL is also in the "description" field of the JSON format below. The network, below, is depicted as a labeled graph near the end of this example.

!cat {rcc8_file}

{
    "name": "Wikipedia RCC8 Example",
    "algebra": "RCC8_Algebra",
    "abbreviations": {"dec": "DC|EC"},
    "description": "See https://en.wikipedia.org/wiki/Region_connection_calculus#Examples",
    "nodes": [
        ["House1", ["Region"]],
        ["House2", ["Region"]],
        ["Property1", ["Region"]],
        ["Property2", ["Region"]],
        ["Road", ["Region"]]
    ],
    "edges": [
        ["House1", "Hous