delphin.hierarchy

Basic support for hierarchies.

This module defines the MultiHierarchy class for multiply-inheriting hierarchies. This class manages the insertion of new nodes into the hierarchy via the class constructor or the MultiHierarchy.update() method, normalizing node identifiers (if a suitable normalization function is provided at instantiation), and inserting nodes in the appropriate order. It checks for some kinds of ill-formed hierarchies, such as cycles and redundant parentage and provides methods for testing for node compatibility and subsumption. For convenience, arbitrary data may be associated with node identifiers.

While the class may be used directly, it is mainly used to support the TypeHierarchy class and the predicate, property, and variable hierarchies of SemI instances.

Classes

class delphin.hierarchy.MultiHierarchy(top, hierarchy=None, data=None, normalize_identifier=None)[source]

A Multiply-inheriting Hierarchy.

Hierarchies may be constructed when instantiating the class or via the update() method using a dictionary mapping identifiers to parents. In both cases, the parents may be a string of whitespace-separated parent identifiers or a tuple of (possibly non-string) identifiers. Also, both methods may take a data parameter which accepts a mapping from identifiers to arbitrary data. Data for identifiers may be get and set individually with dictionary key-access.

>>> h = MultiHierarchy('*top*', {'food': '*top*',
...                              'utensil': '*top*'})
>>> th.update({'fruit': 'food', 'apple': 'fruit'})
>>> th['apple'] = 'info about apples'
>>> th.update({'knife': 'utensil'},
...           data={'knife': 'info about knives'})
>>> th.update({'vegetable': 'food', 'tomato': 'fruit vegetable'})

In some ways the MultiHierarchy behaves like a dictionary, but it is not a subclass of dict and does not implement all its methods. Also note that some methods ignore the top node, which make certain actions easier:

>>> h = Hierarchy('*top*', {'a': '*top*', 'b': 'a', 'c': 'a'})
>>> len(h)
3
>>> list(h)
['a', 'b', 'c']
>>> Hierarchy('*top*', {id: h.parents(id) for id in h}) == h
True

But others do not ignore the top node, namely those where you can request it specifically:

>>> '*top*' in h
True
>>> print(h['*top*'])
None
>>> h.children('*top*')
{'a'}
Parameters
  • top – the unique top identifier

  • hierarchy – a mapping of node identifiers to parents (see description above concerning the possible parent values)

  • data – a mapping of node identifiers to arbitrary data

  • normalize_identifier – a unary function used to normalize identifiers (e.g., case normalization)

top

the hierarchy’s top node identifier

ancestors(identifier)[source]

Return the ancestors of identifier.

children(identifier)[source]

Return the immediate children of identifier.

compatible(a, b)[source]

Return True if node a is compatible with node b.

In a multiply-inheriting hierarchy, node compatibility means that two nodes share a common descendant. It is a commutative operation, so compatible(a, b) == compatible(b, a). Note that in a singly-inheriting hierarchy, two nodes are never compatible by this metric.

Parameters
  • a – a node identifier

  • b – a node identifier

Examples

>>> h = MultiHierarchy('*top*', {'a': '*top*',
...                              'b': '*top*'})
>>> h.compatible('a', 'b')
False
>>> h.update({'c': 'a b'})
>>> h.compatible('a', 'b')
True
descendants(identifier)[source]

Return the descendants of identifier.

items()[source]

Return the (identifier, data) pairs excluding the top node.

parents(identifier)[source]

Return the immediate parents of identifier.

subsumes(a, b)[source]

Return True if node a subsumes node b.

A node is subsumed by the other if it is a descendant of the other node or if it is the other node. It is not a commutative operation, so subsumes(a, b) != subsumes(b, a), except for the case where a == b.

Parameters
  • a – a node identifier

  • b – a node identifier

Examples

>>> h = MultiHierarchy('*top*', {'a': '*top*',
...                              'b': '*top*',
...                              'c': 'b'})
>>> all(h.subsumes(h.top, x) for x in h)
True
>>> h.subsumes('a', h.top)
False
>>> h.subsumes('a', 'b')
False
>>> h.subsumes('b', 'c')
True
update(subhierarchy=None, data=None)[source]

Incorporate subhierarchy and data into the hierarchy.

This method ensures that nodes are inserted in an order that does not result in an intermediate state being disconnected or cyclic, and raises an error if it cannot avoid such a state due to subhierarchy being invalid when inserted into the main hierarchy. Updates are atomic, so subhierarchy and data will not be partially applied if there is an error in the middle of the operation.

Parameters
  • subhierarchy – mapping of node identifiers to parents

  • data – mapping of node identifiers to data objects

Raises

HierarchyError – when subhierarchy or data cannot be incorporated into the hierarchy

Examples

>>> h = MultiHierarchy('*top*')
>>> h.update({'a': '*top*'})
>>> h.update({'b': '*top*'}, data={'b': 5})
>>> h.update(data={'a': 3})
>>> h['b'] - h['a']
2
validate_update(subhierarchy, data)[source]

Check if the update can apply to the current hierarchy.

This method returns (subhierarchy, data) with normalized identifiers if the update is valid, otherwise it will raise a HierarchyError.

Raises

HierarchyError – when the update is invalid

Exceptions

exception delphin.hierarchy.HierarchyError(*args, **kwargs)[source]

Bases: delphin.exceptions.PyDelphinException

Raised for invalid operations on hierarchies.