NOTE: The code below derives Allen’s original algebra of proper time intervals.
- “Maintaining Knowledge about Temporal Intervals” by J.F. Allen - Allen’s original paper
- Allen’s Interval Algebra or here - summarizes Allen’s algebra of proper time intervals
- “Intervals, Points, and Branching Time” by A.J. Reich - basis for the extensions here to Allen’s algebra
- W3C Time Ontology in OWL - temporal vocabulary used here is based on the W3C vocabulary of time
- bitsets Python package - used to implement Algebra relation sets and operations
- NetworkX Python package - used to represent directed graph of constraints
- Python format string syntax - used in Algebra summary method
- Spatial Ontology - I’m still looking for a standard spatial vocabulary; maybe start here
- Qualitative Spatial Relations (QSR) Library - an alternative library to the one defined here
import os
import qualreas as qr
import numpy as np
import sys
sys.setrecursionlimit(10000)
path = os.path.join(os.getenv('PYPROJ'), 'qualreas')
pt_alg = qr.Algebra(os.path.join(path, "Algebras/Linear_Point_Algebra.json"))
pt_alg.summary()
Algebra Name: Linear_Point_Algebra Description: Linear Point Algebra Equality Rels: = Relations: NAME (SYMBOL) CONVERSE (ABBREV) REFLEXIVE SYMMETRIC TRANSITIVE DOMAIN RANGE LessThan ( <) GreaterThan ( >) False False True Pt Pt Equals ( =) Equals ( =) True True True Pt Pt GreaterThan ( >) LessThan ( <) False False True Pt Pt Domain & Range Abbreviations: Pt = Point PInt = Proper Interval
qr.print_point_algebra_composition_table(pt_alg)
Linear_Point_Algebra Elements: <, =, > ============================== rel1 ; rel2 = composition ============================== < < < < = < < > <|=|> ------------------------------ = < < = = = = > > ------------------------------ > < <|=|> > = > > > > ------------------------------
The definition of less than, below, either restricts intervals to be proper (‘<’) or allows intervals to be degenerate (‘=|<’) (i.e., integrates points and intervals).
#less_than_rel = '=|<'
less_than_rel = '<'
allen_alg_name = "Derived_Allen_Algebra"
allen_alg_desc = "Allens algebra derived from point relations"
verbose = True
%time test_allen_alg_dict = qr.derive_algebra(pt_alg, less_than_rel, name=allen_alg_name, description=allen_alg_desc, verbose=verbose)
========================== <,<,<,< B (['ProperInterval'], ['ProperInterval']) [['=' '<' '<' '<'] ['>' '=' '<' '<'] ['>' '>' '=' '<'] ['>' '>' '>' '=']] ========================== <,<,=,< M (['ProperInterval'], ['ProperInterval']) [['=' '<' '<' '<'] ['>' '=' '=' '<'] ['>' '=' '=' '<'] ['>' '>' '>' '=']] ========================== <,<,>,< O (['ProperInterval'], ['ProperInterval']) [['=' '<' '<' '<'] ['>' '=' '>' '<'] ['>' '<' '=' '<'] ['>' '>' '>' '=']] ========================== <,<,>,= FI (['ProperInterval'], ['ProperInterval']) [['=' '<' '<' '<'] ['>' '=' '>' '='] ['>' '<' '=' '<'] ['>' '=' '>' '=']] ========================== <,<,>,> DI (['ProperInterval'], ['ProperInterval']) [['=' '<' '<' '<'] ['>' '=' '>' '>'] ['>' '<' '=' '<'] ['>' '<' '>' '=']] ========================== =,<,>,< S (['ProperInterval'], ['ProperInterval']) [['=' '<' '=' '<'] ['>' '=' '>' '<'] ['=' '<' '=' '<'] ['>' '>' '>' '=']] ========================== =,<,>,= E (['ProperInterval'], ['ProperInterval']) [['=' '<' '=' '<'] ['>' '=' '>' '='] ['=' '<' '=' '<'] ['>' '=' '>' '=']] ========================== =,<,>,> SI (['ProperInterval'], ['ProperInterval']) [['=' '<' '=' '<'] ['>' '=' '>' '>'] ['=' '<' '=' '<'] ['>' '<' '>' '=']] ========================== >,<,>,< D (['ProperInterval'], ['ProperInterval']) [['=' '<' '>' '<'] ['>' '=' '>' '<'] ['<' '<' '=' '<'] ['>' '>' '>' '=']] ========================== >,<,>,= F (['ProperInterval'], ['ProperInterval']) [['=' '<' '>' '<'] ['>' '=' '>' '='] ['<' '<' '=' '<'] ['>' '=' '>' '=']] ========================== >,<,>,> OI (['ProperInterval'], ['ProperInterval']) [['=' '<' '>' '<'] ['>' '=' '>' '>'] ['<' '<' '=' '<'] ['>' '<' '>' '=']] ========================== >,=,>,> MI (['ProperInterval'], ['ProperInterval']) [['=' '<' '>' '='] ['>' '=' '>' '>'] ['<' '<' '=' '<'] ['=' '<' '>' '=']] ========================== >,>,>,> BI (['ProperInterval'], ['ProperInterval']) [['=' '<' '>' '>'] ['>' '=' '>' '>'] ['<' '<' '=' '<'] ['<' '<' '>' '=']] 13 consistent networks CPU times: user 869 ms, sys: 428 ms, total: 1.3 s Wall time: 714 ms
test_allen_alg_dict
{'Name': 'Derived_Allen_Algebra', 'Description': 'Allens algebra derived from point relations', 'Relations': {'B': {'Name': 'Before', 'Converse': 'BI', 'Domain': ['ProperInterval'], 'Range': ['ProperInterval'], 'Reflexive': False, 'Symmetric': False, 'Transitive': True}, 'BI': {'Name': 'After', 'Converse': 'B', 'Domain': ['ProperInterval'], 'Range': ['ProperInterval'], 'Reflexive': False, 'Symmetric': False, 'Transitive': True}, 'D': {'Name': 'During', 'Converse': 'DI', 'Domain': ['ProperInterval'], 'Range': ['ProperInterval'], 'Reflexive': False, 'Symmetric': False, 'Transitive': True}, 'DI': {'Name': 'Contains', 'Converse': 'D', 'Domain': ['ProperInterval'], 'Range': ['ProperInterval'], 'Reflexive': False, 'Symmetric': False, 'Transitive': True}, 'E': {'Name': 'Equals', 'Converse': 'E', 'Domain': ['ProperInterval'], 'Range': ['ProperInterval'], 'Reflexive': True, 'Symmetric': True, 'Transitive': True}, 'F': {'Name': 'Finishes', 'Converse': 'FI', 'Domain': ['ProperInterval'], 'Range': ['ProperInterval'], 'Reflexive': False, 'Symmetric': False, 'Transitive': True}, 'FI': {'Name': 'Finished-by', 'Converse': 'F', 'Domain': ['ProperInterval'], 'Range': ['ProperInterval'], 'Reflexive': False, 'Symmetric': False, 'Transitive': True}, 'M': {'Name': 'Meets', 'Converse': 'MI', 'Domain': ['ProperInterval'], 'Range': ['ProperInterval'], 'Reflexive': False, 'Symmetric': False, 'Transitive': False}, 'MI': {'Name': 'Met-By', 'Converse': 'M', 'Domain': ['ProperInterval'], 'Range': ['ProperInterval'], 'Reflexive': False, 'Symmetric': False, 'Transitive': False}, 'O': {'Name': 'Overlaps', 'Converse': 'OI', 'Domain': ['ProperInterval'], 'Range': ['ProperInterval'], 'Reflexive': False, 'Symmetric': False, 'Transitive': False}, 'OI': {'Name': 'Overlapped-By', 'Converse': 'O', 'Domain': ['ProperInterval'], 'Range': ['ProperInterval'], 'Reflexive': False, 'Symmetric': False, 'Transitive': False}, 'S': {'Name': 'Starts', 'Converse': 'SI', 'Domain': ['ProperInterval'], 'Range': ['ProperInterval'], 'Reflexive': False, 'Symmetric': False, 'Transitive': True}, 'SI': {'Name': 'Started-By', 'Converse': 'S', 'Domain': ['ProperInterval'], 'Range': ['ProperInterval'], 'Reflexive': False, 'Symmetric': False, 'Transitive': True}}, 'TransTable': {'B': {'B': 'B', 'BI': 'B|BI|D|DI|E|F|FI|M|MI|O|OI|S|SI', 'D': 'B|D|M|O|S', 'DI': 'B', 'E': 'B', 'F': 'B|D|M|O|S', 'FI': 'B', 'M': 'B', 'MI': 'B|D|M|O|S', 'O': 'B', 'OI': 'B|D|M|O|S', 'S': 'B', 'SI': 'B'}, 'BI': {'B': 'B|BI|D|DI|E|F|FI|M|MI|O|OI|S|SI', 'BI': 'BI', 'D': 'BI|D|F|MI|OI', 'DI': 'BI', 'E': 'BI', 'F': 'BI', 'FI': 'BI', 'M': 'BI|D|F|MI|OI', 'MI': 'BI', 'O': 'BI|D|F|MI|OI', 'OI': 'BI', 'S': 'BI|D|F|MI|OI', 'SI': 'BI'}, 'D': {'B': 'B', 'BI': 'BI', 'D': 'D', 'DI': 'B|BI|D|DI|E|F|FI|M|MI|O|OI|S|SI', 'E': 'D', 'F': 'D', 'FI': 'B|D|M|O|S', 'M': 'B', 'MI': 'BI', 'O': 'B|D|M|O|S', 'OI': 'BI|D|F|MI|OI', 'S': 'D', 'SI': 'BI|D|F|MI|OI'}, 'DI': {'B': 'B|DI|FI|M|O', 'BI': 'BI|DI|MI|OI|SI', 'D': 'D|DI|E|F|FI|O|OI|S|SI', 'DI': 'DI', 'E': 'DI', 'F': 'DI|OI|SI', 'FI': 'DI', 'M': 'DI|FI|O', 'MI': 'DI|OI|SI', 'O': 'DI|FI|O', 'OI': 'DI|OI|SI', 'S': 'DI|FI|O', 'SI': 'DI'}, 'E': {'B': 'B', 'BI': 'BI', 'D': 'D', 'DI': 'DI', 'E': 'E', 'F': 'F', 'FI': 'FI', 'M': 'M', 'MI': 'MI', 'O': 'O', 'OI': 'OI', 'S': 'S', 'SI': 'SI'}, 'F': {'B': 'B', 'BI': 'BI', 'D': 'D', 'DI': 'BI|DI|MI|OI|SI', 'E': 'F', 'F': 'F', 'FI': 'E|F|FI', 'M': 'M', 'MI': 'BI', 'O': 'D|O|S', 'OI': 'BI|MI|OI', 'S': 'D', 'SI': 'BI|MI|OI'}, 'FI': {'B': 'B', 'BI': 'BI|DI|MI|OI|SI', 'D': 'D|O|S', 'DI': 'DI', 'E': 'FI', 'F': 'E|F|FI', 'FI': 'FI', 'M': 'M', 'MI': 'DI|OI|SI', 'O': 'O', 'OI': 'DI|OI|SI', 'S': 'O', 'SI': 'DI'}, 'M': {'B': 'B', 'BI': 'BI|DI|MI|OI|SI', 'D': 'D|O|S', 'DI': 'B', 'E': 'M', 'F': 'D|O|S', 'FI': 'B', 'M': 'B', 'MI': 'E|F|FI', 'O': 'B', 'OI': 'D|O|S', 'S': 'M', 'SI': 'M'}, 'MI': {'B': 'B|DI|FI|M|O', 'BI': 'BI', 'D': 'D|F|OI', 'DI': 'BI', 'E': 'MI', 'F': 'MI', 'FI': 'MI', 'M': 'E|S|SI', 'MI': 'BI', 'O': 'D|F|OI', 'OI': 'BI', 'S': 'D|F|OI', 'SI': 'BI'}, 'O': {'B': 'B', 'BI': 'BI|DI|MI|OI|SI', 'D': 'D|O|S', 'DI': 'B|DI|FI|M|O', 'E': 'O', 'F': 'D|O|S', 'FI': 'B|M|O', 'M': 'B', 'MI': 'DI|OI|SI', 'O': 'B|M|O', 'OI': 'D|DI|E|F|FI|O|OI|S|SI', 'S': 'O', 'SI': 'DI|FI|O'}, 'OI': {'B': 'B|DI|FI|M|O', 'BI': 'BI', 'D': 'D|F|OI', 'DI': 'BI|DI|MI|OI|SI', 'E': 'OI', 'F': 'OI', 'FI': 'DI|OI|SI', 'M': 'DI|FI|O', 'MI': 'BI', 'O': 'D|DI|E|F|FI|O|OI|S|SI', 'OI': 'BI|MI|OI', 'S': 'D|F|OI', 'SI': 'BI|MI|OI'}, 'S': {'B': 'B', 'BI': 'BI', 'D': 'D', 'DI': 'B|DI|FI|M|O', 'E': 'S', 'F': 'D', 'FI': 'B|M|O', 'M': 'B', 'MI': 'MI', 'O': 'B|M|O', 'OI': 'D|F|OI', 'S': 'S', 'SI': 'E|S|SI'}, 'SI': {'B': 'B|DI|FI|M|O', 'BI': 'BI', 'D': 'D|F|OI', 'DI': 'DI', 'E': 'SI', 'F': 'OI', 'FI': 'DI', 'M': 'DI|FI|O', 'MI': 'MI', 'O': 'DI|FI|O', 'OI': 'OI', 'S': 'E|S|SI', 'SI': 'SI'}}}
test_allen_json_path = os.path.join(path, "Algebras/test_derived_allen_algebra.json")
test_allen_json_path
'/Users/alfredreich/Documents/Python/github/myrepos/qualreas/Algebras/test_derived_allen_algebra.json'
qr.algebra_to_json_file(test_allen_alg_dict, test_allen_json_path)
test_allen_alg = qr.Algebra(test_allen_json_path)
test_allen_alg
<qualreas.Algebra at 0x7feb4892fd60>
test_allen_alg.summary()
Algebra Name: Derived_Allen_Algebra Description: Allens algebra derived from point relations Equality Rels: E Relations: NAME (SYMBOL) CONVERSE (ABBREV) REFLEXIVE SYMMETRIC TRANSITIVE DOMAIN RANGE Before ( B) After ( BI) False False True PInt PInt After ( BI) Before ( B) False False True PInt PInt During ( D) Contains ( DI) False False True PInt PInt Contains ( DI) During ( D) False False True PInt PInt Equals ( E) Equals ( E) True True True PInt PInt Finishes ( F) Finished-by ( FI) False False True PInt PInt Finished-by ( FI) Finishes ( F) False False True PInt PInt Meets ( M) Met-By ( MI) False False False PInt PInt Met-By ( MI) Meets ( M) False False False PInt PInt Overlaps ( O) Overlapped-By ( OI) False False False PInt PInt Overlapped-By ( OI) Overlaps ( O) False False False PInt PInt Starts ( S) Started-By ( SI) False False True PInt PInt Started-By ( SI) Starts ( S) False False True PInt PInt Domain & Range Abbreviations: Pt = Point PInt = Proper Interval
test_allen_alg.check_composition_identity()
True
test_allen_alg.is_associative()
TEST SUMMARY: 2197 OK, 0 Skipped, 0 Failed (2197 Total)
True
allen_alg = qr.Algebra(os.path.join(path, "Algebras/Linear_Interval_Algebra.json"))
allen_alg
<qualreas.Algebra at 0x7feb4892f430>
allen_alg.summary()
Algebra Name: Linear_Interval_Algebra Description: Allen's algebra of proper time intervals Equality Rels: E Relations: NAME (SYMBOL) CONVERSE (ABBREV) REFLEXIVE SYMMETRIC TRANSITIVE DOMAIN RANGE Before ( B) After ( BI) False False True PInt PInt After ( BI) Before ( B) False False True PInt PInt During ( D) Contains ( DI) False False True PInt PInt Contains ( DI) During ( D) False False True PInt PInt Equals ( E) Equals ( E) True True True PInt PInt Finishes ( F) Finished-by ( FI) False False True PInt PInt Finished-by ( FI) Finishes ( F) False False True PInt PInt Meets ( M) Met-By ( MI) False False False PInt PInt Met-By ( MI) Meets ( M) False False False PInt PInt Overlaps ( O) Overlapped-By ( OI) False False False PInt PInt Overlapped-By ( OI) Overlaps ( O) False False False PInt PInt Starts ( S) Started-By ( SI) False False True PInt PInt Started-By ( SI) Starts ( S) False False True PInt PInt Domain & Range Abbreviations: Pt = Point PInt = Proper Interval
print(f"Same as original algebra? {allen_alg.equivalent_algebra(test_allen_alg)}")
Same as original algebra? True