Source code for msinvar.posets

r"""
Posets

EXAMPLES::

    sage: from msinvar.posets import Poset
    sage: P=Poset([[1,2],[1,3]]); P
    Poset with vertices
    {1, 2, 3}
    and relations
    [[1, 2], [1, 3]]
    sage: list(P.succ(1))
    [1, 2, 3]
    sage: list(P.ideals())
    [{1, 2, 3}, {1, 2}, {1, 3}, {1}, set()]
"""

# *****************************************************************************
#  Copyright (C) 2021 Sergey Mozgovoy <mozhov@gmail.com>
#
#  Distributed under the terms of the GNU General Public License (GPL)
#                  http://www.gnu.org/licenses/
# *****************************************************************************


[docs]class Poset(): """ Poset class. EXAMPLES:: sage: from msinvar.posets import Poset sage: P=Poset([[1,2],[1,3]]); P Poset with vertices {1, 2, 3} and relations [[1, 2], [1, 3]] sage: list(P.succ(1)) [1, 2, 3] sage: list(P.ideals()) [{1, 2, 3}, {1, 2}, {1, 3}, {1}, set()] """ def __init__(self, rel, vert=None): if vert is None: vert = set() for r in rel: vert.update(r) self.vert = vert self.rel = rel
[docs] def upper_closure(self, vert): vert = set(vert) new = vert while len(new) > 0: for i in new: yield i new = set(r[1] for r in self.rel if r[0] in new)-vert vert.update(new)
[docs] def lower_closure(self, vert): vert = set(vert) new = vert while len(new) > 0: for i in new: yield i new = set(r[0] for r in self.rel if r[1] in new)-vert vert.update(new)
[docs] def succ(self, i): return self.upper_closure({i})
[docs] def pred(self, i): return self.lower_closure({i})
[docs] def ideals(self, size=100): """ List if ideals in a poset having <=``size`` elements. """ if size<0: return if len(self.vert) == 0 or size == 0: yield set() return nonmin = set(r[1] for r in self.rel) for i in self.vert-nonmin: break # choose a minimal element # yield {i} rel = list(r for r in self.rel if r[0] != i) # relations without i P = Poset(rel, self.vert-{i}) # for ideals with i for I in P.ideals(size-1): yield I | {i} vert = self.vert-set(self.succ(i)) rel = list(r for r in self.rel if r[1] in vert) # relations on vert P = Poset(rel, vert) # for ideals without i for I in P.ideals(size): yield I
def __repr__(self): return "Poset with vertices\n"+str(self.vert)\ +"\nand relations\n"+str(self.rel)