Posets

Generalizes the LinearOrderedCell to include represent po-sets. Instead of being initialized with a list, this requires an instance of nx.DiGraph: a directed graph.

A linear order has these properties:

1. Reflexive a <= a
2. Antisymmetric: a <= b and b <=a implies a == b
3. Transitivity: a <= b and b <=c implies a <= c
4. Linearity: a <= b or b <= a

A partial order does not require the linearity property (4). Namely, some elements are incomparable, represented as a || b. This corresponds to two nodes that are not linked by a directed path.

Generalization domain is a rooted directed graph with one component. The (set of) root node(s) is the Upper generalization boundary, the set of Leaf nodes is the lower generalization boundary.

A Contradiction for a partial ordered set means that there is a directed path between one of the lower boundaries and the root.

Note

All of the following code examples in this module will be based on the following code block:

class POC_A(PartialOrderedCell):
    # partial ordered test
    def __init__(self):
        dag = None
        if not self.has_domain():
            # only initialize once
            dag = nx.DiGraph()
            dag.add_edge("thing", "vehicle")
            dag.add_edge("vehicle", "car")
            dag.add_edge("vehicle", "truck")
        PartialOrderedCell.__init__(self, dag)
        
class POC_B(PartialOrderedCell):
    # partial ordered test
    def __init__(self):
        dag = None
        if not self.has_domain():
            # only initialize once
            dag = nx.DiGraph()
            dag.add_edge("thing", "person")
            dag.add_edge("person", "actress")
            dag.add_edge("person", "writer")
            dag.add_edge("person", "producer")
        PartialOrderedCell.__init__(self, dag)

class POC_C(PartialOrderedCell):
    # partial ordered test
    def __init__(self):
        dag = None
        if not self.has_domain():
            # only initialize once
            dag = nx.DiGraph()
            dag.add_edge("thing", "person")
            dag.add_edge("person", "actress")
            dag.add_edge("person", "director")
            dag.add_edge("director", "good-director")
            dag.add_edge("director", "bad-director")
            dag.add_edge("person", "writer")
            dag.add_edge("person", "producer")
            dag.add_edge("thing", "vehicle")
            dag.add_edge("vehicle", "car")
            dag.add_edge("vehicle", "truck")
    
        PartialOrderedCell.__init__(self, dag)

class PartialOrderedCell(dag, lower=None, upper=None)

Note

This class should not be instantiated directly, but rather it should be subclassed.

Parameters:

• dag (nx.DiGraph) – Represents the generalization structure
• lower (set) – Optional parameter. Defaults to the empty set
• upper (set) – Optional parameter. Defaults to the empty set

classmethod set_domain(clz, dag)

Sets the domain. Should only be called once per class instantiation.

Paramater dag: Raises:CellConstructionFailure – Raised if dag is empty, not directed, not acyclic, or not connected

classmethod get_domain(clz)

Returns the class domain.

classmethod has_domain(clz)

Returns True iff the class’ domain is specified

Returns:bool

get_values()

Returns positive members of the poset

Returns:set

>>> examplePOC = TestPOC()
>>> examplePOC.get_values()
set(['producer', 'thing', 'car', 'writer', 'actress', 'director', 'person', 'bad-director', 'truck', 'vehicle', 'good-director'])

get_boundaries()

Returns just the upper and lower boundaries [upper, lower] representing the most general positive boundaries and the most specific lower boundaries

Returns:tuple – The first item in the tuple is a set representing the upper boundary, and the second item is a set representing the lower boundary

>>> examplePOC = TestPOC()
>>> examplePOC.get_boundaries()
(set([]), set([]))     

compute_upper_bound()

We have to compute the new upper boundary (nub) starting from the root nodes. If a path exists between a root node and another entry in self.upper we can ignore the root node because it has been specialized by one of its successors.

Returns:set – represents the new upper boundary

>>> examplePOC = TestPOC()
>>> examplePOC.compute_upper_bound()
set(['thing'])

is_domain_equal(other)

Computes whether two Partial Orderings have the same generalization structure.

Parameters:other (PartialOrderedCell) – The other partial ordering to compare with Returns:bool

is_equal(other)

Computes whether two Partial Orderings contain the same information

Parameters:other (PartialOrderedCell) – The other partial ordering to compare with Returns:bool

is_entailed_by(other)

Returns True iff Other (a) has the same domain, (b) the same or more specific ‘upper’ bound; and (c) the same or more general ‘lower’ bound.

Approach: Looks for ways to rule out entailment. If none are found, returns True

Parameters:other (PartialOrderedCell) – The other partial ordering to compare with Returns:bool

is_contradictory(other)

Does the merge yield the empty set?

Parameters:other (PartialOrderedCell) – The other partial ordering to compare with Returns:bool

coerce(other, is_positive=True)

Only copies a pointer to the new domain’s cell

Parameters:

• other – A compatible cell, or value in self‘s domain
• is_positive (bool) – Optional parameter. Specifies whether other is positive, in which case it becomes an upper bound, or negative, in which case it becomes a lower bound

Returns:

PartialOrderedCell

Raises:

CellConstructionFailure

merge(other, is_positive=True)

Combines the partial order with either (1) a value in the partial order’s domain, or (2) another partial order with the same domain.

When combining with a value, an optional is_positive parameter can be set to False, meaning that the merged value should be excluded.

Parameters:

• other – Another partial ordering or a value in self‘s domain
• is_positive (bool) – Optional parameter. Specifies whether other is positive, in which case it becomes an upper bound, or negative, in which case it becomes a lower bound

Returns:

PartialOrderedCell

Raises:

• CellConstructionFailure – raised if other is not coercible
• Contradiction – raised if self and other cannot be merged

size()

Return the number of members in the partial ordering (between and including the boundaries)

Returns:int – greater than or equal to zero

to_dot()

Outputs a version that can be displayed or seralized

Returns:dict – keys are ‘upper’ and ‘lower’, values are the corresponding lists

get_refinement_options()

Returns possible specializations for the upper values in the taxonomy

Returns:generator

get_relaxation_options()

Returns possible generalizations for the upper values in the taxonomy

Returns:generator

most_specific_members()

Returns the upper nodes or, if they are empty, the root nodes

Returns:set

to_dotfile()

Writes a DOT graphviz file of the domain structure, and returns the filename

Returns:str