Mutable Poset#

This module provides a class representing a finite partially ordered set (poset) for the purpose of being used as a data structure. Thus the posets introduced in this module are mutable, i.e., elements can be added and removed from a poset at any time.

To get in touch with Sage’s “usual” posets, start with the page Posets in the reference manual.

Examples#

First Steps#

We start by creating an empty poset. This is simply done by

sage: from sage.data_structures.mutable_poset import MutablePoset as MP
sage: P = MP()
sage: P
poset()

A poset should contain elements, thus let us add them with

sage: P.add(42)
sage: P.add(7)
sage: P.add(13)
sage: P.add(3)

Let us look at the poset again:

sage: P
poset(3, 7, 13, 42)

We see that they elements are sorted using \(\leq\) which exists on the integers \(\ZZ\). Since this is even a total order, we could have used a more efficient data structure. Alternatively, we can write

sage: MP([42, 7, 13, 3])
poset(3, 7, 13, 42)

to add several elements at once on construction.

A less boring Example#

Let us continue with a less boring example. We define the class

sage: class T(tuple):
....:     def __le__(left, right):
....:         return all(l <= r for l, r in zip(left, right))

It is equipped with a \(\leq\)-operation such that \(a \leq b\) if all entries of \(a\) are at most the corresponding entry of \(b\). For example, we have

sage: a = T((1,1))
sage: b = T((2,1))
sage: c = T((1,2))
sage: a <= b, a <= c, b <= c
(True, True, False)

The last comparison gives False, since the comparison of the first component checks whether \(2 \leq 1\).

Now, let us add such elements to a poset:

sage: Q = MP([T((1, 1)), T((3, 3)), T((4, 1)),
....:         T((3, 2)), T((2, 3)), T((2, 2))]); Q
poset((1, 1), (2, 2), (2, 3), (3, 2), (3, 3), (4, 1))

In the representation above, the elements are sorted topologically, smallest first. This does not (directly) show more structural information. We can overcome this and display a “wiring layout” by typing:

sage: print(Q.repr_full(reverse=True))
poset((3, 3), (2, 3), (3, 2), (2, 2), (4, 1), (1, 1))
+-- oo
|   +-- no successors
|   +-- predecessors:   (3, 3), (4, 1)
+-- (3, 3)
|   +-- successors:   oo
|   +-- predecessors:   (2, 3), (3, 2)
+-- (2, 3)
|   +-- successors:   (3, 3)
|   +-- predecessors:   (2, 2)
+-- (3, 2)
|   +-- successors:   (3, 3)
|   +-- predecessors:   (2, 2)
+-- (2, 2)
|   +-- successors:   (2, 3), (3, 2)
|   +-- predecessors:   (1, 1)
+-- (4, 1)
|   +-- successors:   oo
|   +-- predecessors:   (1, 1)
+-- (1, 1)
|   +-- successors:   (2, 2), (4, 1)
|   +-- predecessors:   null
+-- null
|   +-- successors:   (1, 1)
|   +-- no predecessors

Note that we use reverse=True to let the elements appear from largest (on the top) to smallest (on the bottom).

If you look at the output above, you’ll see two additional elements, namely oo (\(\infty\)) and null (\(\emptyset\)). So what are these strange animals? The answer is simple and maybe you can guess it already. The \(\infty\)-element is larger than every other element, therefore a successor of the maximal elements in the poset. Similarly, the \(\emptyset\)-element is smaller than any other element, therefore a predecessor of the poset’s minimal elements. Both do not have to scare us; they are just there and sometimes useful.

AUTHORS:

Daniel Krenn (2015)

ACKNOWLEDGEMENT:

Daniel Krenn is supported by the Austrian Science Fund (FWF): P 24644-N26.

Classes and their Methods#

class sage.data_structures.mutable_poset.MutablePoset(data=None, key=None, merge=None, can_merge=None)#

Bases: SageObject

A data structure that models a mutable poset (partially ordered set).

INPUT:

data – data from which to construct the poset. It can be any of the following:
1. None (default), in which case an empty poset is created,
2. a MutablePoset, which will be copied during creation,
3. an iterable, whose elements will be in the poset.
key – a function which maps elements to keys. If None (default), this is the identity, i.e., keys are equal to their elements.

Two elements with the same keys are considered as equal; so only one of these two elements can be in the poset.

This key is not used for sorting (in contrast to sorting-functions, e.g. sorted).
merge – a function which merges its second argument (an element) to its first (again an element) and returns the result (as an element). If the return value is None, the element is removed from the poset.

This hook is called by merge(). Moreover it is used during add() when an element (more precisely its key) is already in this poset.

merge is None (default) is equivalent to merge returning its first argument. Note that it is not allowed that the key of the returning element differs from the key of the first input parameter. This means merge must not change the position of the element in the poset.
can_merge – a function which checks whether its second argument can be merged to its first.

This hook is called by merge(). Moreover it is used during add() when an element (more precisely its key) is already in this poset.

can_merge is None (default) is equivalent to can_merge returning True in all cases.

OUTPUT:

A mutable poset.

You can find a short introduction and examples here.

EXAMPLES:

sage: from sage.data_structures.mutable_poset import MutablePoset as MP

We illustrate the different input formats

No input:
```
sage: A = MP(); A
poset()
```

A MutablePoset:

sage: B = MP(A); B
poset()
sage: B.add(42)
sage: C = MP(B); C
poset(42)

An iterable:

sage: C = MP([5, 3, 11]); C
poset(3, 5, 11)

See also

MutablePosetShell.

add(element)#

Add the given object as element to the poset.

INPUT:

element – an object (hashable and supporting comparison with the operator <=).

OUTPUT:

Nothing.

EXAMPLES:

sage: from sage.data_structures.mutable_poset import MutablePoset as MP
sage: class T(tuple):
....:     def __le__(left, right):
....:         return all(l <= r for l, r in zip(left, right))
sage: P = MP([T((1, 1)), T((1, 3)), T((2, 1)),
....:         T((4, 4)), T((1, 2))])
sage: print(P.repr_full(reverse=True))
poset((4, 4), (1, 3), (1, 2), (2, 1), (1, 1))
+-- oo
|   +-- no successors
|   +-- predecessors: (4, 4)
+-- (4, 4)
|   +-- successors:   oo
|   +-- predecessors: (1, 3), (2, 1)
+-- (1, 3)
|   +-- successors:   (4, 4)
|   +-- predecessors: (1, 2)
+-- (1, 2)
|   +-- successors:   (1, 3)
|   +-- predecessors: (1, 1)
+-- (2, 1)
|   +-- successors:   (4, 4)
|   +-- predecessors: (1, 1)
+-- (1, 1)
|   +-- successors:   (1, 2), (2, 1)
|   +-- predecessors: null
+-- null
|   +-- successors:   (1, 1)
|   +-- no predecessors
sage: P.add(T((2, 2)))
sage: reprP = P.repr_full(reverse=True); print(reprP)
poset((4, 4), (1, 3), (2, 2), (1, 2), (2, 1), (1, 1))
+-- oo
|   +-- no successors
|   +-- predecessors: (4, 4)
+-- (4, 4)
|   +-- successors:   oo
|   +-- predecessors: (1, 3), (2, 2)
+-- (1, 3)
|   +-- successors:   (4, 4)
|   +-- predecessors: (1, 2)
+-- (2, 2)
|   +-- successors:   (4, 4)
|   +-- predecessors: (1, 2), (2, 1)
+-- (1, 2)
|   +-- successors:   (1, 3), (2, 2)
|   +-- predecessors: (1, 1)
+-- (2, 1)
|   +-- successors:   (2, 2)
|   +-- predecessors: (1, 1)
+-- (1, 1)
|   +-- successors:   (1, 2), (2, 1)
|   +-- predecessors: null
+-- null
|   +-- successors:   (1, 1)
|   +-- no predecessors

When adding an element which is already in the poset, nothing happens:

sage: e = T((2, 2))
sage: P.add(e)
sage: P.repr_full(reverse=True) == reprP
True

We can influence the behavior when an element with existing key is to be inserted in the poset. For example, we can perform an addition on some argument of the elements:

sage: def add(left, right):
....:     return (left[0], ''.join(sorted(left[1] + right[1])))
sage: A = MP(key=lambda k: k[0], merge=add)
sage: A.add((3, 'a'))
sage: A
poset((3, 'a'))
sage: A.add((3, 'b'))
sage: A
poset((3, 'ab'))

We can also deal with cancellations. If the return value of our hook-function is None, then the element is removed out of the poset:

sage: def add_None(left, right):
....:     s = left[1] + right[1]
....:     if s == 0:
....:         return None
....:     return (left[0], s)
sage: B = MP(key=lambda k: k[0],
....:        merge=add_None)
sage: B.add((7, 42))
sage: B.add((7, -42))
sage: B
poset()

See also

discard(), pop(), remove().

clear()#

Remove all elements from this poset.

INPUT:

Nothing.

OUTPUT:

Nothing.

See also

discard(), pop(), remove().

contains(key)#

Test whether key is encapsulated by one of the poset’s elements.

INPUT:

key – an object.

OUTPUT:

True or False.

See also

shells(), elements(), keys().

copy(mapping=None)#

Create a shallow copy.

INPUT:

mapping – a function which is applied on each of the elements.

OUTPUT:

A poset with the same content as self.

See also

map(), mapped().

difference(*other)#

Return a new poset where all elements of this poset, which are contained in one of the other given posets, are removed.

INPUT:

other – a poset or an iterable. In the latter case the iterated objects are seen as elements of a poset. It is possible to specify more than one other as variadic arguments (arbitrary argument lists).

OUTPUT:

A poset.

Note

The key of an element is used for comparison. Thus elements with the same key are considered as equal.

EXAMPLES:

sage: from sage.data_structures.mutable_poset import MutablePoset as MP
sage: P = MP([3, 42, 7]); P
poset(3, 7, 42)
sage: Q = MP([4, 8, 42]); Q
poset(4, 8, 42)
sage: P.difference(Q)
poset(3, 7)

difference_update(*other)#

Remove all elements of another poset from this poset.

INPUT:

other – a poset or an iterable. In the latter case the iterated objects are seen as elements of a poset. It is possible to specify more than one other as variadic arguments (arbitrary argument lists).

OUTPUT:

Nothing.

Note

The key of an element is used for comparison. Thus elements with the same key are considered as equal.

EXAMPLES:

sage: from sage.data_structures.mutable_poset import MutablePoset as MP
sage: P = MP([3, 42, 7]); P
poset(3, 7, 42)
sage: Q = MP([4, 8, 42]); Q
poset(4, 8, 42)
sage: P.difference_update(Q)
sage: P
poset(3, 7)

discard(key, raise_key_error=False)#

Remove the given object from the poset.

INPUT:

key – the key of an object.
raise_key_error – (default: False) switch raising KeyError on and off.

OUTPUT:

Nothing.

If the element is not a member and raise_key_error is set (not default), raise a KeyError.

Note

As with Python’s set, the methods remove() and discard() only differ in their behavior when an element is not contained in the poset: remove() raises a KeyError whereas discard() does not raise any exception.

This default behavior can be overridden with the raise_key_error parameter.

EXAMPLES:

sage: from sage.data_structures.mutable_poset import MutablePoset as MP
sage: class T(tuple):
....:     def __le__(left, right):
....:         return all(l <= r for l, r in zip(left, right))
sage: P = MP([T((1, 1)), T((1, 3)), T((2, 1)),
....:         T((4, 4)), T((1, 2)), T((2, 2))])
sage: P.discard(T((1, 2)))
sage: P.remove(T((1, 2)))
Traceback (most recent call last):
...
KeyError: 'Key (1, 2) is not contained in this poset.'
sage: P.discard(T((1, 2)))

element(key)#

Return the element corresponding to key.

INPUT:

key – the key of an object.

OUTPUT:

An object.

EXAMPLES:

sage: from sage.data_structures.mutable_poset import MutablePoset as MP
sage: P = MP()
sage: P.add(42)
sage: e = P.element(42); e
42
sage: type(e)
<class 'sage.rings.integer.Integer'>

See also

shell(), get_key().

elements(**kwargs)#

Return an iterator over all elements.

INPUT:

kwargs – arguments are passed to shells().

OUTPUT:

An iterator.

EXAMPLES:

sage: from sage.data_structures.mutable_poset import MutablePoset as MP
sage: P = MP([3, 42, 7])
sage: [(v, type(v)) for v in sorted(P.elements())]
[(3, <class 'sage.rings.integer.Integer'>),
 (7, <class 'sage.rings.integer.Integer'>),
 (42, <class 'sage.rings.integer.Integer'>)]

Note that

sage: it = iter(P)
sage: sorted(it)
[3, 7, 42]

returns all elements as well.

elements_topological(**kwargs)#

Return an iterator over all elements in topological order.

INPUT:

kwargs – arguments are passed to shells_topological().

OUTPUT:

An iterator.

EXAMPLES:

sage: from sage.data_structures.mutable_poset import MutablePoset as MP
sage: class T(tuple):
....:     def __le__(left, right):
....:         return all(l <= r for l, r in zip(left, right))
sage: P = MP([T((1, 1)), T((1, 3)), T((2, 1)),
....:         T((4, 4)), T((1, 2)), T((2, 2))])
sage: [(v, type(v)) for v in P.elements_topological(key=repr)]
[((1, 1), <class '__main__.T'>),
 ((1, 2), <class '__main__.T'>),
 ((1, 3), <class '__main__.T'>),
 ((2, 1), <class '__main__.T'>),
 ((2, 2), <class '__main__.T'>),
 ((4, 4), <class '__main__.T'>)]

get_key(element)#

Return the key corresponding to the given element.

INPUT:

element – an object.

OUTPUT:

An object (the key of element).

See also

element(), shell().

intersection(*other)#

Return the intersection of the given posets as a new poset

INPUT:

other – a poset or an iterable. In the latter case the iterated objects are seen as elements of a poset. It is possible to specify more than one other as variadic arguments (arbitrary argument lists).

OUTPUT:

A poset.

Note

The key of an element is used for comparison. Thus elements with the same key are considered as equal.

EXAMPLES:

sage: from sage.data_structures.mutable_poset import MutablePoset as MP
sage: P = MP([3, 42, 7]); P
poset(3, 7, 42)
sage: Q = MP([4, 8, 42]); Q
poset(4, 8, 42)
sage: P.intersection(Q)
poset(42)

intersection_update(*other)#

Update this poset with the intersection of itself and another poset.

INPUT:

other – a poset or an iterable. In the latter case the iterated objects are seen as elements of a poset. It is possible to specify more than one other as variadic arguments (arbitrary argument lists).

OUTPUT:

Nothing.

Note

The key of an element is used for comparison. Thus elements with the same key are considered as equal; A.intersection_update(B) and B.intersection_update(A) might result in different posets.

EXAMPLES:

sage: from sage.data_structures.mutable_poset import MutablePoset as MP
sage: P = MP([3, 42, 7]); P
poset(3, 7, 42)
sage: Q = MP([4, 8, 42]); Q
poset(4, 8, 42)
sage: P.intersection_update(Q)
sage: P
poset(42)

is_disjoint(other)#

Return whether another poset is disjoint to this poset.

INPUT:

other – a poset or an iterable. In the latter case the iterated objects are seen as elements of a poset.

OUTPUT:

Nothing.

Note

If this poset uses a key-function, then all comparisons are performed on the keys of the elements (and not on the elements themselves).

EXAMPLES:

sage: from sage.data_structures.mutable_poset import MutablePoset as MP
sage: P = MP([3, 42, 7]); P
poset(3, 7, 42)
sage: Q = MP([4, 8, 42]); Q
poset(4, 8, 42)
sage: P.is_disjoint(Q)
False
sage: P.is_disjoint(Q.difference(P))
True

is_subset(other)#

Return whether another poset contains this poset, i.e., whether this poset is a subset of the other poset.

INPUT:

other – a poset or an iterable. In the latter case the iterated objects are seen as elements of a poset.

OUTPUT:

Nothing.

Note

If this poset uses a key-function, then all comparisons are performed on the keys of the elements (and not on the elements themselves).

EXAMPLES:

sage: from sage.data_structures.mutable_poset import MutablePoset as MP
sage: P = MP([3, 42, 7]); P
poset(3, 7, 42)
sage: Q = MP([4, 8, 42]); Q
poset(4, 8, 42)
sage: P.is_subset(Q)
False
sage: Q.is_subset(P)
False
sage: P.is_subset(P)
True
sage: P.is_subset(P.union(Q))
True

is_superset(other)#

Return whether this poset contains another poset, i.e., whether this poset is a superset of the other poset.

INPUT:

other – a poset or an iterable. In the latter case the iterated objects are seen as elements of a poset.

OUTPUT:

Nothing.

Note

If this poset uses a key-function, then all comparisons are performed on the keys of the elements (and not on the elements themselves).

EXAMPLES:

sage: from sage.data_structures.mutable_poset import MutablePoset as MP
sage: P = MP([3, 42, 7]); P
poset(3, 7, 42)
sage: Q = MP([4, 8, 42]); Q
poset(4, 8, 42)
sage: P.is_superset(Q)
False
sage: Q.is_superset(P)
False
sage: P.is_superset(P)
True
sage: P.union(Q).is_superset(P)
True

isdisjoint(other)#: Alias of is_disjoint().

issubset(other)#: Alias of is_subset().

issuperset(other)#: Alias of is_superset().

keys(**kwargs)#

Return an iterator over all keys of the elements.

INPUT:

kwargs – arguments are passed to shells().

OUTPUT:

An iterator.

EXAMPLES:

sage: from sage.data_structures.mutable_poset import MutablePoset as MP
sage: P = MP([3, 42, 7], key=lambda c: -c)
sage: [(v, type(v)) for v in sorted(P.keys())]
[(-42, <class 'sage.rings.integer.Integer'>),
 (-7, <class 'sage.rings.integer.Integer'>),
 (-3, <class 'sage.rings.integer.Integer'>)]

sage: [(v, type(v)) for v in sorted(P.elements())]
[(3, <class 'sage.rings.integer.Integer'>),
 (7, <class 'sage.rings.integer.Integer'>),
 (42, <class 'sage.rings.integer.Integer'>)]

sage: [(v, type(v)) for v in sorted(P.shells(),
....:                               key=lambda c: c.element)]
[(3, <class 'sage.data_structures.mutable_poset.MutablePosetShell'>),
 (7, <class 'sage.data_structures.mutable_poset.MutablePosetShell'>),
 (42, <class 'sage.data_structures.mutable_poset.MutablePosetShell'>)]

keys_topological(**kwargs)#

Return an iterator over all keys of the elements in topological order.

INPUT:

kwargs – arguments are passed to shells_topological().

OUTPUT:

An iterator.

EXAMPLES:

sage: from sage.data_structures.mutable_poset import MutablePoset as MP
sage: P = MP([(1, 1), (2, 1), (4, 4)],
....:        key=lambda c: c[0])
sage: [(v, type(v)) for v in P.keys_topological(key=repr)]
[(1, <class 'sage.rings.integer.Integer'>),
 (2, <class 'sage.rings.integer.Integer'>),
 (4, <class 'sage.rings.integer.Integer'>)]
sage: [(v, type(v)) for v in P.elements_topological(key=repr)]
[((1, 1), <... 'tuple'>),
 ((2, 1), <... 'tuple'>),
 ((4, 4), <... 'tuple'>)]
sage: [(v, type(v)) for v in P.shells_topological(key=repr)]
[((1, 1), <class 'sage.data_structures.mutable_poset.MutablePosetShell'>),
 ((2, 1), <class 'sage.data_structures.mutable_poset.MutablePosetShell'>),
 ((4, 4), <class 'sage.data_structures.mutable_poset.MutablePosetShell'>)]

map(function, topological=False, reverse=False)#

Apply the given function to each element of this poset.

INPUT:

function – a function mapping an existing element to a new element.
topological – (default: False) if set, then the mapping is done in topological order, otherwise unordered.
reverse – is passed on to topological ordering.

OUTPUT:

Nothing.

Note

Since this method works inplace, it is not allowed that function alters the key of an element.

Note

If function returns None, then the element is removed.

EXAMPLES:

sage: from sage.data_structures.mutable_poset import MutablePoset as MP
sage: class T(tuple):
....:     def __le__(left, right):
....:         return all(l <= r for l, r in zip(left, right))
sage: P = MP([T((1, 3)), T((2, 1)),
....:         T((4, 4)), T((1, 2)), T((2, 2))],
....:        key=lambda e: e[:2])
sage: P.map(lambda e: e + (sum(e),))
sage: P
poset((1, 2, 3), (1, 3, 4), (2, 1, 3), (2, 2, 4), (4, 4, 8))

See also

copy(), mapped().

mapped(function)#

Return a poset where on each element the given function was applied.

INPUT:

function – a function mapping an existing element to a new element.
topological – (default: False) if set, then the mapping is done in topological order, otherwise unordered.
reverse – is passed on to topological ordering.

OUTPUT:

A MutablePoset.

Note

function is not allowed to change the order of the keys, but changing the keys themselves is allowed (in contrast to map()).

EXAMPLES:

sage: from sage.data_structures.mutable_poset import MutablePoset as MP
sage: class T(tuple):
....:     def __le__(left, right):
....:         return all(l <= r for l, r in zip(left, right))
sage: P = MP([T((1, 3)), T((2, 1)),
....:         T((4, 4)), T((1, 2)), T((2, 2))])
sage: P.mapped(lambda e: str(e))
poset('(1, 2)', '(1, 3)', '(2, 1)', '(2, 2)', '(4, 4)')

See also

copy(), map().

maximal_elements()#

Return an iterator over the maximal elements of this poset.

INPUT:

Nothing.

OUTPUT:

An iterator.

EXAMPLES:

sage: from sage.data_structures.mutable_poset import MutablePoset as MP
sage: class T(tuple):
....:     def __le__(left, right):
....:         return all(l <= r for l, r in zip(left, right))
sage: P = MP([T((1, 1)), T((1, 3)), T((2, 1)),
....:         T((1, 2)), T((2, 2))])
sage: sorted(P.maximal_elements())
[(1, 3), (2, 2)]

See also

minimal_elements()

merge(key=None, reverse=False)#

Merge the given element with its successors/predecessors.

INPUT:

key – the key specifying an element or None (default), in which case this method is called on each element in this poset.
reverse – (default: False) specifies which direction to go first: False searches towards 'oo' and True searches towards 'null'. When key=None, then this also specifies which elements are merged first.

OUTPUT:

Nothing.

This method tests all (not necessarily direct) successors and predecessors of the given element whether they can be merged with the element itself. This is done by the can_merge-function of MutablePoset. If this merge is possible, then it is performed by calling MutablePoset’s merge-function and the corresponding successor/predecessor is removed from the poset.

Note

can_merge is applied in the sense of the condition of depth first iteration, i.e., once can_merge fails, the successors/predecessors are no longer tested.

Note

The motivation for such a merge behavior comes from asymptotic expansions: \(O(n^3)\) merges with, for example, \(3n^2\) or \(O(n)\) to \(O(n^3)\) (as \(n\) tends to \(\infty\); see Wikipedia article Big_O_notation).

EXAMPLES:

sage: from sage.data_structures.mutable_poset import MutablePoset as MP
sage: class T(tuple):
....:     def __le__(left, right):
....:         return all(l <= r for l, r in zip(left, right))
sage: key = lambda t: T(t[0:2])
sage: def add(left, right):
....:     return (left[0], left[1],
....:             ''.join(sorted(left[2] + right[2])))
sage: def can_add(left, right):
....:     return key(left) >= key(right)
sage: P = MP([(1, 1, 'a'), (1, 3, 'b'), (2, 1, 'c'),
....:         (4, 4, 'd'), (1, 2, 'e'), (2, 2, 'f')],
....:        key=key, merge=add, can_merge=can_add)
sage: Q = copy(P)
sage: Q.merge(T((1, 3)))
sage: print(Q.repr_full(reverse=True))
poset((4, 4, 'd'), (1, 3, 'abe'), (2, 2, 'f'), (2, 1, 'c'))
+-- oo
|   +-- no successors
|   +-- predecessors:   (4, 4, 'd')
+-- (4, 4, 'd')
|   +-- successors:   oo
|   +-- predecessors:   (1, 3, 'abe'), (2, 2, 'f')
+-- (1, 3, 'abe')
|   +-- successors:   (4, 4, 'd')
|   +-- predecessors:   null
+-- (2, 2, 'f')
|   +-- successors:   (4, 4, 'd')
|   +-- predecessors:   (2, 1, 'c')
+-- (2, 1, 'c')
|   +-- successors:   (2, 2, 'f')
|   +-- predecessors:   null
+-- null
|   +-- successors:   (1, 3, 'abe'), (2, 1, 'c')
|   +-- no predecessors
sage: for k in sorted(P.keys()):
....:     Q = copy(P)
....:     Q.merge(k)
....:     print('merging %s: %s' % (k, Q))
merging (1, 1): poset((1, 1, 'a'), (1, 2, 'e'), (1, 3, 'b'),
                      (2, 1, 'c'), (2, 2, 'f'), (4, 4, 'd'))
merging (1, 2): poset((1, 2, 'ae'), (1, 3, 'b'), (2, 1, 'c'),
                      (2, 2, 'f'), (4, 4, 'd'))
merging (1, 3): poset((1, 3, 'abe'), (2, 1, 'c'), (2, 2, 'f'),
                      (4, 4, 'd'))
merging (2, 1): poset((1, 2, 'e'), (1, 3, 'b'), (2, 1, 'ac'),
                      (2, 2, 'f'), (4, 4, 'd'))
merging (2, 2): poset((1, 3, 'b'), (2, 2, 'acef'), (4, 4, 'd'))
merging (4, 4): poset((4, 4, 'abcdef'))

sage: Q = copy(P)
sage: Q.merge(); Q
poset((4, 4, 'abcdef'))

See also

MutablePosetShell.merge()

minimal_elements()#

Return an iterator over the minimal elements of this poset.

INPUT:

Nothing.

OUTPUT:

An iterator.

EXAMPLES:

sage: from sage.data_structures.mutable_poset import MutablePoset as MP
sage: class T(tuple):
....:     def __le__(left, right):
....:         return all(l <= r for l, r in zip(left, right))
sage: P = MP([T((1, 3)), T((2, 1)),
....:         T((4, 4)), T((1, 2)), T((2, 2))])
sage: sorted(P.minimal_elements())
[(1, 2), (2, 1)]

See also

maximal_elements()

property null#

The shell \(\emptyset\) whose element is smaller than any other element.

EXAMPLES:

sage: from sage.data_structures.mutable_poset import MutablePoset as MP
sage: P = MP()
sage: z = P.null; z
null
sage: z.is_null()
True

property oo#

The shell \(\infty\) whose element is larger than any other element.

EXAMPLES:

sage: from sage.data_structures.mutable_poset import MutablePoset as MP
sage: P = MP()
sage: oo = P.oo; oo
oo
sage: oo.is_oo()
True

pop(**kwargs)#

Remove and return an arbitrary poset element.

INPUT:

kwargs – arguments are passed to shells_topological().

OUTPUT:

An object.

Note

The special elements 'null' and 'oo' cannot be popped.

EXAMPLES:

sage: from sage.data_structures.mutable_poset import MutablePoset as MP
sage: P = MP()
sage: P.add(3)
sage: P
poset(3)
sage: P.pop()
3
sage: P
poset()
sage: P.pop()
Traceback (most recent call last):
...
KeyError: 'pop from an empty poset'

remove(key, raise_key_error=True)#

Remove the given object from the poset.

INPUT:

key – the key of an object.
raise_key_error – (default: True) switch raising KeyError on and off.

OUTPUT:

Nothing.

If the element is not a member and raise_key_error is set (default), raise a KeyError.

Note

This default behavior can be overridden with the raise_key_error parameter.

EXAMPLES:

sage: from sage.data_structures.mutable_poset import MutablePoset as MP
sage: class T(tuple):
....:     def __le__(left, right):
....:         return all(l <= r for l, r in zip(left, right))
sage: P = MP([T((1, 1)), T((1, 3)), T((2, 1)),
....:         T((4, 4)), T((1, 2)), T((2, 2))])
sage: print(P.repr_full(reverse=True))
poset((4, 4), (1, 3), (2, 2), (1, 2), (2, 1), (1, 1))
+-- oo
|   +-- no successors
|   +-- predecessors: (4, 4)
+-- (4, 4)
|   +-- successors:   oo
|   +-- predecessors: (1, 3), (2, 2)
+-- (1, 3)
|   +-- successors:   (4, 4)
|   +-- predecessors: (1, 2)
+-- (2, 2)
|   +-- successors:   (4, 4)
|   +-- predecessors: (1, 2), (2, 1)
+-- (1, 2)
|   +-- successors:   (1, 3), (2, 2)
|   +-- predecessors: (1, 1)
+-- (2, 1)
|   +-- successors:   (2, 2)
|   +-- predecessors: (1, 1)
+-- (1, 1)
|   +-- successors:   (1, 2), (2, 1)
|   +-- predecessors: null
+-- null
|   +-- successors:   (1, 1)
|   +-- no predecessors
sage: P.remove(T((1, 2)))
sage: print(P.repr_full(reverse=True))
poset((4, 4), (1, 3), (2, 2), (2, 1), (1, 1))
+-- oo
|   +-- no successors
|   +-- predecessors: (4, 4)
+-- (4, 4)
|   +-- successors:   oo
|   +-- predecessors: (1, 3), (2, 2)
+-- (1, 3)
|   +-- successors:   (4, 4)
|   +-- predecessors: (1, 1)
+-- (2, 2)
|   +-- successors:   (4, 4)
|   +-- predecessors: (2, 1)
+-- (2, 1)
|   +-- successors:   (2, 2)
|   +-- predecessors: (1, 1)
+-- (1, 1)
|   +-- successors:   (1, 3), (2, 1)
|   +-- predecessors: null
+-- null
|   +-- successors:   (1, 1)
|   +-- no predecessors

repr(include_special=False, reverse=False)#

Return a representation of the poset.

INPUT:

include_special – (default: False) a boolean indicating whether to include the special elements 'null' and 'oo' or not.
reverse – (default: False) a boolean. If set, then largest elements are displayed first.

OUTPUT:

A string.

See also

repr_full()

repr_full(reverse=False)#

Return a representation with ordering details of the poset.

INPUT:

reverse – (default: False) a boolean. If set, then largest elements are displayed first.

OUTPUT:

A string.

See also

repr()

shell(key)#

Return the shell of the element corresponding to key.

INPUT:

key – the key of an object.

OUTPUT:

An instance of MutablePosetShell.

Note

Each element is contained/encapsulated in a shell inside the poset.

EXAMPLES:

sage: from sage.data_structures.mutable_poset import MutablePoset as MP
sage: P = MP()
sage: P.add(42)
sage: e = P.shell(42); e
42
sage: type(e)
<class 'sage.data_structures.mutable_poset.MutablePosetShell'>

See also

element(), get_key().

shells(include_special=False)#

Return an iterator over all shells.

INPUT:

include_special – (default: False) if set, then including shells containing a smallest element (\(\emptyset\)) and a largest element (\(\infty\)).

OUTPUT:

An iterator.

Note

Each element is contained/encapsulated in a shell inside the poset.

EXAMPLES:

sage: from sage.data_structures.mutable_poset import MutablePoset as MP
sage: P = MP()
sage: tuple(P.shells())
()
sage: tuple(P.shells(include_special=True))
(null, oo)

shells_topological(include_special=False, reverse=False, key=None)#

Return an iterator over all shells in topological order.

INPUT:

include_special – (default: False) if set, then including shells containing a smallest element (\(\emptyset\)) and a largest element (\(\infty\)).
reverse – (default: False) – if set, reverses the order, i.e., False gives smallest elements first, True gives largest first.
key – (default: None) a function used for sorting the direct successors of a shell (used in case of a tie). If this is None, no sorting occurs.

OUTPUT:

An iterator.

Note

Each element is contained/encapsulated in a shell inside the poset.

EXAMPLES:

sage: from sage.data_structures.mutable_poset import MutablePoset as MP
sage: class T(tuple):
....:     def __le__(left, right):
....:         return all(l <= r for l, r in zip(left, right))
sage: P = MP([T((1, 1)), T((1, 3)), T((2, 1)),
....:         T((4, 4)), T((1, 2)), T((2, 2))])
sage: list(P.shells_topological(key=repr))
[(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (4, 4)]
sage: list(P.shells_topological(reverse=True, key=repr))
[(4, 4), (1, 3), (2, 2), (1, 2), (2, 1), (1, 1)]
sage: list(P.shells_topological(include_special=True, key=repr))
[null, (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (4, 4), oo]
sage: list(P.shells_topological(
....:     include_special=True, reverse=True, key=repr))
[oo, (4, 4), (1, 3), (2, 2), (1, 2), (2, 1), (1, 1), null]

symmetric_difference(other)#

Return the symmetric difference of two posets as a new poset.

INPUT:

other – a poset.

OUTPUT:

A poset.

Note

The key of an element is used for comparison. Thus elements with the same key are considered as equal.

EXAMPLES:

sage: from sage.data_structures.mutable_poset import MutablePoset as MP
sage: P = MP([3, 42, 7]); P
poset(3, 7, 42)
sage: Q = MP([4, 8, 42]); Q
poset(4, 8, 42)
sage: P.symmetric_difference(Q)
poset(3, 4, 7, 8)

symmetric_difference_update(other)#

Update this poset with the symmetric difference of itself and another poset.

INPUT:

other – a poset.

OUTPUT:

Nothing.

Note

The key of an element is used for comparison. Thus elements with the same key are considered as equal; A.symmetric_difference_update(B) and B.symmetric_difference_update(A) might result in different posets.

EXAMPLES:

sage: from sage.data_structures.mutable_poset import MutablePoset as MP
sage: P = MP([3, 42, 7]); P
poset(3, 7, 42)
sage: Q = MP([4, 8, 42]); Q
poset(4, 8, 42)
sage: P.symmetric_difference_update(Q)
sage: P
poset(3, 4, 7, 8)

union(*other)#

Return the union of the given posets as a new poset

INPUT:

other – a poset or an iterable. In the latter case the iterated objects are seen as elements of a poset. It is possible to specify more than one other as variadic arguments (arbitrary argument lists).

OUTPUT:

A poset.

Note

The key of an element is used for comparison. Thus elements with the same key are considered as equal.

Due to keys and a merge function (see MutablePoset) this operation might not be commutative.

Todo

Use the already existing information in the other poset to speed up this function. (At the moment each element of the other poset is inserted one by one and without using this information.)

EXAMPLES:

sage: from sage.data_structures.mutable_poset import MutablePoset as MP
sage: P = MP([3, 42, 7]); P
poset(3, 7, 42)
sage: Q = MP([4, 8, 42]); Q
poset(4, 8, 42)
sage: P.union(Q)
poset(3, 4, 7, 8, 42)

union_update(*other)#

Update this poset with the union of itself and another poset.

INPUT:

other – a poset or an iterable. In the latter case the iterated objects are seen as elements of a poset. It is possible to specify more than one other as variadic arguments (arbitrary argument lists).

OUTPUT:

Nothing.

Note

The key of an element is used for comparison. Thus elements with the same key are considered as equal; A.union_update(B) and B.union_update(A) might result in different posets.

Todo

Use the already existing information in the other poset to speed up this function. (At the moment each element of the other poset is inserted one by one and without using this information.)

EXAMPLES:

sage: from sage.data_structures.mutable_poset import MutablePoset as MP
sage: P = MP([3, 42, 7]); P
poset(3, 7, 42)
sage: Q = MP([4, 8, 42]); Q
poset(4, 8, 42)
sage: P.union_update(Q)
sage: P
poset(3, 4, 7, 8, 42)

update(*other)#: Alias of union_update().

class sage.data_structures.mutable_poset.MutablePosetShell(poset, element)#

Bases: SageObject

A shell for an element of a mutable poset.

INPUT:

poset – the poset to which this shell belongs.
element – the element which should be contained/encapsulated in this shell.

OUTPUT:

A shell for the given element.

Note

If the element() of a shell is None, then this element is considered as “special” (see is_special()). There are two special elements, namely

a 'null' (an element smaller than each other element; it has no predecessors) and
an 'oo' (an element larger than each other element; it has no successors).

EXAMPLES:

sage: from sage.data_structures.mutable_poset import MutablePoset as MP
sage: P = MP()
sage: P.add(66)
sage: P
poset(66)
sage: s = P.shell(66)
sage: type(s)
<class 'sage.data_structures.mutable_poset.MutablePosetShell'>

See also

MutablePoset

property element#: The element contained in this shell.

See also

key(), MutablePoset.

eq(other)#

Return whether this shell is equal to other.

INPUT:

other – a shell.

OUTPUT:

True or False.

Note

This method compares the keys of the elements contained in the (non-special) shells. In particular, elements/shells with the same key are considered as equal.

See also

le(), MutablePoset.

is_null()#

Return whether this shell contains the null-element, i.e., the element smaller than any possible other element.

OUTPUT:

True or False.

is_oo()#

Return whether this shell contains the infinity-element, i.e., the element larger than any possible other element.

OUTPUT:

True or False.

is_special()#

Return whether this shell contains either the null-element, i.e., the element smaller than any possible other element or the infinity-element, i.e., the element larger than any possible other element.

INPUT:

Nothing.

OUTPUT:

True or False.

See also

is_null(), is_oo(), MutablePoset.

iter_depth_first(reverse=False, key=None, condition=None)#

Iterate over all shells in depth first order.

INPUT:

reverse – (default: False) if set, reverses the order, i.e., False searches towards 'oo' and True searches towards 'null'.
key – (default: None) a function used for sorting the direct successors of a shell (used in case of a tie). If this is None, no sorting occurs.
condition – (default: None) a function mapping a shell to True (include in iteration) or False (do not include). None is equivalent to a function returning always True. Note that the iteration does not go beyond a not included shell.

OUTPUT:

An iterator.

Note

The depth first search starts at this (self) shell. Thus only this shell and shells greater than (in case of reverse=False) this shell are visited.

ALGORITHM:

See Wikipedia article Depth-first_search.

EXAMPLES:

sage: from sage.data_structures.mutable_poset import MutablePoset as MP
sage: class T(tuple):
....:     def __le__(left, right):
....:         return all(l <= r for l, r in zip(left, right))
sage: P = MP([T((1, 1)), T((1, 3)), T((2, 1)),
....:         T((4, 4)), T((1, 2)), T((2, 2))])
sage: list(P.null.iter_depth_first(reverse=False, key=repr))
[null, (1, 1), (1, 2), (1, 3), (4, 4), oo, (2, 2), (2, 1)]
sage: list(P.oo.iter_depth_first(reverse=True, key=repr))
[oo, (4, 4), (1, 3), (1, 2), (1, 1), null, (2, 2), (2, 1)]
sage: list(P.null.iter_depth_first(
....:     condition=lambda s: s.element[0] == 1))
[null, (1, 1), (1, 2), (1, 3)]

See also

iter_topological(), MutablePoset.

iter_topological(reverse=False, key=None, condition=None)#

Iterate over all shells in topological order.

INPUT:

reverse – (default: False) if set, reverses the order, i.e., False searches towards 'oo' and True searches towards 'null'.
key – (default: None) a function used for sorting the direct predecessors of a shell (used in case of a tie). If this is None, no sorting occurs.
condition – (default: None) a function mapping a shell to True (include in iteration) or False (do not include). None is equivalent to a function returning always True. Note that the iteration does not go beyond a not included shell.

OUTPUT:

An iterator.

Note

The topological search will only find shells smaller than (in case of reverse=False) or equal to this (self) shell. This is in contrast to iter_depth_first().

ALGORITHM:

Here a simplified version of the algorithm found in [Tar1976] and [CLRS2001] is used. See also Wikipedia article Topological_sorting.

EXAMPLES:

sage: from sage.data_structures.mutable_poset import MutablePoset as MP
sage: class T(tuple):
....:     def __le__(left, right):
....:         return all(l <= r for l, r in zip(left, right))
sage: P = MP([T((1, 1)), T((1, 3)), T((2, 1)),
....:         T((4, 4)), T((1, 2)), T((2, 2))])

sage: for e in P.shells_topological(include_special=True,
....:                               reverse=True, key=repr):
....:     print(e)
....:     print(list(e.iter_topological(reverse=True, key=repr)))
oo
[oo]
(4, 4)
[oo, (4, 4)]
(1, 3)
[oo, (4, 4), (1, 3)]
(2, 2)
[oo, (4, 4), (2, 2)]
(1, 2)
[oo, (4, 4), (1, 3), (2, 2), (1, 2)]
(2, 1)
[oo, (4, 4), (2, 2), (2, 1)]
(1, 1)
[oo, (4, 4), (1, 3), (2, 2), (1, 2), (2, 1), (1, 1)]
null
[oo, (4, 4), (1, 3), (2, 2), (1, 2), (2, 1), (1, 1), null]

sage: for e in P.shells_topological(include_special=True,
....:                               reverse=True, key=repr):
....:     print(e)
....:     print(list(e.iter_topological(reverse=False, key=repr)))
oo
[null, (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (4, 4), oo]
(4, 4)
[null, (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (4, 4)]
(1, 3)
[null, (1, 1), (1, 2), (1, 3)]
(2, 2)
[null, (1, 1), (1, 2), (2, 1), (2, 2)]
(1, 2)
[null, (1, 1), (1, 2)]
(2, 1)
[null, (1, 1), (2, 1)]
(1, 1)
[null, (1, 1)]
null
[null]

sage: list(P.null.iter_topological(
....:     reverse=True, condition=lambda s: s.element[0] == 1,
....:     key=repr))
[(1, 3), (1, 2), (1, 1), null]

property key#

The key of the element contained in this shell.

The key of an element is determined by the mutable poset (the parent) via the key-function (see construction of a MutablePoset).

See also

element(), MutablePoset.

le(other, reverse=False)#

Return whether this shell is less than or equal to other.

INPUT:

other – a shell.
reverse – (default: False) if set, then return whether this shell is greater than or equal to other.

OUTPUT:

True or False.

Note

The comparison of the shells is based on the comparison of the keys of the elements contained in the shells, except for special shells (see MutablePosetShell).

See also

eq(), MutablePoset.

lower_covers(shell, reverse=False)#

Return the lower covers of the specified shell; the search is started at this (self) shell.

A lower cover of \(x\) is an element \(y\) of the poset such that \(y < x\) and there is no element \(z\) of the poset so that \(y < z < x\).

INPUT:

shell – the shell for which to find the covering shells. There is no restriction of shell being contained in the poset. If shell is contained in the poset, then use the more efficient methods predecessors() and successors().
reverse – (default: False) if set, then find the upper covers (see also upper_covers()) instead of the lower covers.

OUTPUT:

A set of shells.

Note

Suppose reverse is False. This method starts at the calling shell (self) and searches towards 'oo'. Thus, only shells which are (not necessarily direct) successors of this shell are considered.

If reverse is True, then the reverse direction is taken.

EXAMPLES:

sage: from sage.data_structures.mutable_poset import MutablePoset as MP
sage: class T(tuple):
....:     def __le__(left, right):
....:         return all(l <= r for l, r in zip(left, right))
sage: P = MP([T((1, 1)), T((1, 3)), T((2, 1)),
....:         T((4, 4)), T((1, 2)), T((2, 2))])
sage: e = P.shell(T((2, 2))); e
(2, 2)
sage: sorted(P.null.lower_covers(e),
....:        key=lambda c: repr(c.element))
[(1, 2), (2, 1)]
sage: set(_) == e.predecessors()
True
sage: sorted(P.oo.upper_covers(e),
....:        key=lambda c: repr(c.element))
[(4, 4)]
sage: set(_) == e.successors()
True

sage: Q = MP([T((3, 2))])
sage: f = next(Q.shells())
sage: sorted(P.null.lower_covers(f),
....:        key=lambda c: repr(c.element))
[(2, 2)]
sage: sorted(P.oo.upper_covers(f),
....:        key=lambda c: repr(c.element))
[(4, 4)]

merge(element, check=True, delete=True)#

Merge the given element with the element contained in this shell.

INPUT:

element – an element (of the poset).
check – (default: True) if set, then the can_merge-function of MutablePoset determines whether the merge is possible. can_merge is None means that this check is always passed.
delete – (default: True) if set, then element is removed from the poset after the merge.

OUTPUT:

Nothing.

Note

This operation depends on the parameters merge and can_merge of the MutablePoset this shell is contained in. These parameters are defined when the poset is constructed.

Note

If the merge function returns None, then this shell is removed from the poset.

EXAMPLES:

sage: from sage.data_structures.mutable_poset import MutablePoset as MP
sage: def add(left, right):
....:     return (left[0], ''.join(sorted(left[1] + right[1])))
sage: def can_add(left, right):
....:     return left[0] <= right[0]
sage: P = MP([(1, 'a'), (3, 'b'), (2, 'c'), (4, 'd')],
....:        key=lambda c: c[0], merge=add, can_merge=can_add)
sage: P
poset((1, 'a'), (2, 'c'), (3, 'b'), (4, 'd'))
sage: P.shell(2).merge((3, 'b'))
sage: P
poset((1, 'a'), (2, 'bc'), (4, 'd'))

See also

MutablePoset.merge(), MutablePoset.

property poset#: The poset to which this shell belongs.

See also

MutablePoset

predecessors(reverse=False)#

Return the predecessors of this shell.

INPUT:

reverse – (default: False) if set, then return successors instead.

OUTPUT:

A set.

See also

successors(), MutablePoset.

successors(reverse=False)#

Return the successors of this shell.

INPUT:

reverse – (default: False) if set, then return predecessors instead.

OUTPUT:

A set.

See also

predecessors(), MutablePoset.

upper_covers(shell, reverse=False)#

Return the upper covers of the specified shell; the search is started at this (self) shell.

An upper cover of \(x\) is an element \(y\) of the poset such that \(x < y\) and there is no element \(z\) of the poset so that \(x < z < y\).

INPUT:

shell – the shell for which to find the covering shells. There is no restriction of shell being contained in the poset. If shell is contained in the poset, then use the more efficient methods predecessors() and successors().
reverse – (default: False) if set, then find the lower covers (see also lower_covers()) instead of the upper covers.

OUTPUT:

A set of shells.

Note

Suppose reverse is False. This method starts at the calling shell (self) and searches towards 'null'. Thus, only shells which are (not necessarily direct) predecessors of this shell are considered.

If reverse is True, then the reverse direction is taken.

EXAMPLES:

sage: from sage.data_structures.mutable_poset import MutablePoset as MP
sage: class T(tuple):
....:     def __le__(left, right):
....:         return all(l <= r for l, r in zip(left, right))
sage: P = MP([T((1, 1)), T((1, 3)), T((2, 1)),
....:         T((4, 4)), T((1, 2)), T((2, 2))])
sage: e = P.shell(T((2, 2))); e
(2, 2)
sage: sorted(P.null.lower_covers(e),
....:        key=lambda c: repr(c.element))
[(1, 2), (2, 1)]
sage: set(_) == e.predecessors()
True
sage: sorted(P.oo.upper_covers(e),
....:        key=lambda c: repr(c.element))
[(4, 4)]
sage: set(_) == e.successors()
True

sage: Q = MP([T((3, 2))])
sage: f = next(Q.shells())
sage: sorted(P.null.lower_covers(f),
....:        key=lambda c: repr(c.element))
[(2, 2)]
sage: sorted(P.oo.upper_covers(f),
....:        key=lambda c: repr(c.element))
[(4, 4)]

sage.data_structures.mutable_poset.is_MutablePoset(P)#: Test whether P inherits from MutablePoset.

See also

MutablePoset