Coverage for local/lib/python2.7/site-packages/sage/combinat/posets/hasse

[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (1, 0), (1, 1), (1, 4), (2, 0), (2, 2), (2, 3), (2, 4), (3, 0), (3, 2), (3, 3), (3, 4), (4, 0), (4, 1), (4, 2), (4, 3), (4, 4)]

"""

mat = self._leq_matrix

return bool(mat[i,j]) or bool(mat[j,i])

def antichains(self, element_class = list):

"""

Returns all antichains of ``self``, organized as a

prefix tree

INPUT:

- ``element_class`` -- (default:list) an iterable type

EXAMPLES::

sage: P = posets.PentagonPoset()

sage: H = P._hasse_diagram

sage: A = H.antichains()

sage: list(A)

[[], [0], [1], [1, 2], [1, 3], [2], [3], [4]]

sage: A.cardinality()

sage: [1,3] in A

True

sage: [1,4] in A

False

TESTS::

sage: TestSuite(A).run(skip = "_test_pickling")

.. note:: It's actually the pickling of the cached method

:meth:`coxeter_transformation` that fails ...

TESTS::

sage: A = Poset()._hasse_diagram.antichains()

sage: list(A)

[[]]

sage: TestSuite(A).run()

"""

from sage.combinat.subsets_pairwise import PairwiseCompatibleSubsets

return PairwiseCompatibleSubsets(self.vertices(),

self.are_incomparable,

element_class = element_class)

def chains(self, element_class=list, exclude=None):

"""

Return all chains of ``self``, organized as a prefix tree.

INPUT:

- ``element_class`` -- (default: ``list``) an iterable type

- ``exclude`` -- elements of the poset to be excluded

(default: ``None``)

OUTPUT:

The enumerated set (with a forest structure given by prefix

ordering) consisting of all chains of ``self``, each of

which is given as an ``element_class``.

EXAMPLES::

sage: P = posets.PentagonPoset()

sage: H = P._hasse_diagram

sage: A = H.chains()

sage: list(A)

[[], [0], [0, 1], [0, 1, 4], [0, 2], [0, 2, 3], [0, 2, 3, 4], [0, 2, 4], [0, 3], [0, 3, 4], [0, 4], [1], [1, 4], [2], [2, 3], [2, 3, 4], [2, 4], [3], [3, 4], [4]]

sage: A.cardinality()

sage: [1,3] in A

False

sage: [1,4] in A

True

One can exclude some vertices::

sage: list(H.chains(exclude=[4, 3]))

[[], [0], [0, 1], [0, 2], [1], [2]]

The ``element_class`` keyword determines how the chains are

being returned:

sage: P = Poset({1: [2, 3], 2: [4]})

sage: list(P._hasse_diagram.chains(element_class=tuple))

[(), (0,), (0, 1), (0, 1, 2), (0, 2), (0, 3), (1,), (1, 2), (2,), (3,)]

sage: list(P._hasse_diagram.chains())

[[], [0], [0, 1], [0, 1, 2], [0, 2], [0, 3], [1], [1, 2], [2], [3]]

(Note that taking the Hasse diagram has renamed the vertices.)

sage: list(P._hasse_diagram.chains(element_class=tuple, exclude=[0]))

[(), (1,), (1, 2), (2,), (3,)]

.. SEEALSO:: :meth:`antichains`

"""

from sage.combinat.subsets_pairwise import PairwiseCompatibleSubsets

if not(exclude is None):

vertices = [u for u in self.vertices() if not u in exclude]

else:

vertices = self.vertices()

return PairwiseCompatibleSubsets(vertices,

self.are_comparable,

element_class = element_class)

def sublattices_iterator(self, elms, min_e):

"""

Return an iterator over sublattices of the Hasse diagram.

INPUT:

- ``elms`` -- elements already in sublattice; use set() at start

- ``min_e`` -- smallest new element to add for new sublattices

OUTPUT:

List of sublattices as sets of integers.

EXAMPLES::

sage: from sage.combinat.posets.hasse_diagram import HasseDiagram

sage: H = HasseDiagram({0: [1, 2], 1:[3], 2:[3]})

sage: it = H.sublattices_iterator(set(), 0); it

sage: next(it)

set()

sage: next(it)

{0}

"""

# Python3-note: "yield from" would be simpler.

yield elms

for e in range(min_e, self.cardinality()):

if e in elms:

continue

current_set = set(elms)

gens = set([e])

while gens:

g = gens.pop()

if g < e and g not in elms:

break

if g in current_set:

continue

for x in current_set:

gens.add(self._meet[x, g])

gens.add(self._join[x, g])

current_set.add(g)

else:

for x in self.sublattices_iterator(current_set, e+1):

yield x

def maximal_sublattices(self):

"""

Return maximal sublattices of the lattice.

EXAMPLES::

sage: L = posets.PentagonPoset()

sage: ms = L._hasse_diagram.maximal_sublattices()

sage: sorted(ms, key=sorted)

[{0, 1, 2, 4}, {0, 1, 3, 4}, {0, 2, 3, 4}]

"""

jn = self.join_matrix()

mt = self.meet_matrix()

def sublattice(elms, e):

"""

Helper function to get sublattice generated by list

of elements.

"""

gens_remaining = set([e])

current_set = set(elms)

while gens_remaining:

g = gens_remaining.pop()

if g in current_set:

continue

for x in current_set:

gens_remaining.add(jn[x, g])

gens_remaining.add(mt[x, g])

current_set.add(g)

return current_set

N = self.cardinality()

elms = [0]

sublats = [set([0])]

result = []

skip = -1

while True:

# First try to append an element

found_element_to_append = False

e = elms[-1]

while e != skip:

e += 1

if e == N:

maybe_found = sublats[-1]

if not any(maybe_found.issubset(x) for x in result):

result.append(sublats[-1])

break

if e in sublats[-1]:

continue

# Let's try to add 'e' and see what happens.

sl = sublattice(sublats[-1], e)

if len(sl) < N:

# Skip this, if it generated a back-reference.

new_elms = sl.difference(sublats[-1])

if not any(x < e for x in new_elms):

found_element_to_append = True

break

# Now sl is whole lattice, so we continue and try

# appending another element.

if found_element_to_append:

elms.append(e)

sublats.append(sl)

continue

# Can not append. Try to increment last element.

e = elms.pop()

sublats.pop()

last_element_increment = True

while True:

e += 1

if e == N:

last_element_increment = False

break

if e in sublats[-1]:

continue

sl = sublattice(sublats[-1], e)

if len(sl) == N:

continue

new_elms = sl.difference(set(sublats[-1]))

if any(x < e for x in new_elms):

continue

elms.append(e)

sublats.append(sl)

break

if not last_element_increment:

# Can not append nor increment. "Backtracking".

skip = elms[-1]

if skip == 0:

break

# Special case to handle at last.

if len(self.neighbors_out(0)) == 1:

result.append(set(range(1, N)))

return result

def frattini_sublattice(self):

"""

Return the list of elements of the Frattini sublattice of the lattice.

EXAMPLES::

sage: H = posets.PentagonPoset()._hasse_diagram

sage: H.frattini_sublattice()

[0, 4]

"""

# Just a direct computation, no optimization at all.

n = self.cardinality()

if n == 0 or n == 2: return []

if n == 1: return [0]

max_sublats = self.maximal_sublattices()

return [e for e in range(self.cardinality()) if

all(e in ms for ms in max_sublats)]

def kappa_dual(self, a):

r"""

Return the minimum element smaller than the element covering

``a`` but not smaller than ``a``.

Define `\kappa^*(a)` as the minimum element of

`(\downarrow a_*) \setminus (\downarrow a)`, where `a_*` is the element

covering `a`. It is always a join-irreducible element, if it exists.

.. NOTE::

Element ``a`` is expected to be meet-irreducible, and

this is *not* checked.

INPUT:

- ``a`` -- a join-irreducible element of the lattice

OUTPUT:

The element `\kappa^*(a)` or ``None`` if there

is not a unique smallest element with given constraints.

EXAMPLES::

sage: from sage.combinat.posets.hasse_diagram import HasseDiagram

sage: H = HasseDiagram({0: [1, 2], 1: [3, 4], 2: [4, 5], 3: [6], 4: [6], 5: [6]})

sage: H.kappa_dual(3)

sage: H.kappa_dual(4) is None

True

TESTS::

sage: H = HasseDiagram({0: [1]})

sage: H.kappa_dual(0)

"""

uc = next(self.neighbor_out_iterator(a))

if self.in_degree(uc) == 1:

return uc

lt_a = set(self.depth_first_search(a, neighbors=self.neighbors_in))

tmp = list(self.depth_first_search(uc, neighbors=lambda v: [v_ for v_ in self.neighbors_in(v) if v_ not in lt_a]))

result = None

for e in tmp:

if all(x not in tmp for x in self.neighbors_in(e)):

if result:

return None

result = e

return result

def skeleton(self):

"""

Return the skeleton of the lattice.

The lattice is expected to be pseudocomplemented and non-empty.

The skeleton of the lattice is the subposet induced by

those elements that are the pseudocomplement to at least one

element.

OUTPUT:

List of elements such that the subposet induced by them is

the skeleton of the lattice.

EXAMPLES::

sage: from sage.combinat.posets.hasse_diagram import HasseDiagram

sage: H = HasseDiagram({0: [1, 2], 1: [3, 4], 2: [4],

....: 3: [5], 4: [5]})

sage: H.skeleton()

[5, 2, 0, 3]

"""

p_atoms = []

for atom in self.neighbor_out_iterator(0):

p_atom = self.pseudocomplement(atom)

if p_atom is None:

raise ValueError("lattice is not pseudocomplemented")

p_atoms.append(p_atom)

n = len(p_atoms)

mt = self._meet

pos = [0] * n

meets = [self.order()-1] * n

result = [self.order()-1]

i = 0

while i >= 0:

new_meet = mt[meets[i-1], p_atoms[pos[i]]]

result.append(new_meet)

if pos[i] == n-1:

i -= 1

pos[i] = pos[i]+1

else:

meets[i] = new_meet

pos[i+1] = pos[i]+1

i += 1

return result

def is_convex_subset(self, S):

r"""

Return ``True`` if `S` is a convex subset of the poset,

and ``False`` otherwise.

A subset `S` is *convex* in the poset if `b \in S` whenever

`a, c \in S` and `a \le b \le c`.

EXAMPLES::

sage: from sage.combinat.posets.hasse_diagram import HasseDiagram

sage: B3 = HasseDiagram({0: [1, 2, 4], 1: [3, 5], 2: [3, 6],

....: 3: [7], 4: [5, 6], 5: [7], 6: [7]})

sage: B3.is_convex_subset([1, 3, 5, 4]) # Also connected

True

sage: B3.is_convex_subset([1, 3, 4]) # Not connected

True

sage: B3.is_convex_subset([0, 1, 2, 3, 6]) # No, 0 < 4 < 6

False

sage: B3.is_convex_subset([0, 1, 2, 7]) # No, 1 < 3 < 7.

False

TESTS::

sage: B3.is_convex_subset([])

True

sage: B3.is_convex_subset([6])

True

"""

if not S: # S is empty set

return True

s_max = max(S)

ok = set() # Already checked elements not less than any element is S.

for a in S:

for b in self.neighbor_out_iterator(a):

if b >= s_max or b in S:

continue

# Now b not in S, b > a and a in S.

neighbors = lambda v_: [v for v in self.neighbor_out_iterator(v_)

if v <= s_max and v not in ok]

for c in self.depth_first_search(b, neighbors=neighbors):

if c in S: # Now c in S, b not in S, a in S, a < b < c.

return False

ok.add(c) # Do not re-check this for being our b.

return True

def neutral_elements(self):

"""

Return the list of neutral elements of the lattice.

An element `a` in a lattice is neutral if the sublattice

generated by `a`, `x` and `y` is distributive for every

`x`, `y` in the lattice.

EXAMPLES::

sage: from sage.combinat.posets.hasse_diagram import HasseDiagram

sage: H= HasseDiagram({0: [1, 2], 1: [4], 2: [3], 3: [4, 5],

....: 4: [6], 5:[6]})

sage: sorted(H.neutral_elements())

[0, 4, 6]

ALGORITHM:

Basically we just check the distributivity against all element

pairs `x, y` to see if element `a` is neutral or not.

If we found that `a, x, y` is not a distributive triple, we add

all three to list of non-neutral elements. If we found `a` to

be neutral, we add it to list of neutral elements. When testing

we skip already found neutral elements, as they can't be our `x`

or `y`.

We skip `a, x, y` as trivial if it is a chain. We do that by

letting `x` to be a non-comparable to `a`; `y` can be any element.

We first try to found `x` and `y` from elements not yet tested,

so that we could get three birds with one stone.

And last, the top and bottom elements are always neutral and

need not be tested.

"""

n = self.order()

if n < 5:

return set(range(n))

todo = set(range(1, n-1))

neutrals = set([0, n-1])

notneutrals = set()

all_elements = set(range(n))

mt = self._meet

jn = self._join

def is_neutral(a):

noncomp = all_elements.difference(self.depth_first_search(a))

noncomp.difference_update(self.depth_first_search(a, neighbors=self.neighbors_in))

for x in noncomp.intersection(todo):

meet_ax = mt[a, x]

join_ax = jn[a, x]

for y in todo:

if (mt[mt[join_ax, jn[a, y]], jn[x, y]] !=

jn[jn[meet_ax, mt[a, y]], mt[x, y]]):

notneutrals.add(x)

notneutrals.add(y)

return False

for y in notneutrals:

if (mt[mt[join_ax, jn[a, y]], jn[x, y]] !=

jn[jn[meet_ax, mt[a, y]], mt[x, y]]):

notneutrals.add(x)

return False

for x in noncomp.difference(todo):

meet_ax = mt[a, x]

join_ax = jn[a, x]

for y in todo:

if (mt[mt[join_ax, jn[a, y]], jn[x, y]] !=

jn[jn[meet_ax, mt[a, y]], mt[x, y]]):

notneutrals.add(y)

return False

for y in notneutrals:

if (mt[mt[join_ax, jn[a, y]], jn[x, y]] !=

jn[jn[meet_ax, mt[a, y]], mt[x, y]]):

return False

return True

while todo:

e = todo.pop()

if is_neutral(e):

neutrals.add(e)

else:

notneutrals.add(e)

return neutrals

def kappa(self, a):

r"""

Return the maximum element greater than the element covered

by ``a`` but not greater than ``a``.

Define `\kappa(a)` as the maximum element of

`(\uparrow a_*) \setminus (\uparrow a)`, where `a_*` is the element

covered by `a`. It is always a meet-irreducible element, if it exists.

.. NOTE::

Element ``a`` is expected to be join-irreducible, and

this is *not* checked.

INPUT:

- ``a`` -- a join-irreducible element of the lattice

OUTPUT:

The element `\kappa(a)` or ``None`` if there

is not a unique greatest element with given constraints.

EXAMPLES::

sage: from sage.combinat.posets.hasse_diagram import HasseDiagram

sage: H = HasseDiagram({0: [1, 2, 3], 1: [4], 2: [4, 5], 3: [5], 4: [6], 5: [6]})

sage: H.kappa(1)

sage: H.kappa(2) is None

True

TESTS::

sage: H = HasseDiagram({0: [1]})

sage: H.kappa(1)

"""

lc = next(self.neighbor_in_iterator(a))

if self.out_degree(lc) == 1:

return lc

gt_a = set(self.depth_first_search(a))

tmp = list(self.depth_first_search(lc, neighbors=lambda v: [v_ for v_ in self.neighbors_out(v) if v_ not in gt_a]))

result = None

for e in tmp:

if all(x not in tmp for x in self.neighbors_out(e)):

if result:

return None

result = e

return result

def atoms_of_congruence_lattice(self):

r"""

Return atoms of the congruence lattice.

In other words, return "minimal non-trivial" congruences:

A congruence is minimal if the only finer (as a partition

of set of elements) congruence is the trivial congruence

where every block contains only one element.

.. SEEALSO:: :meth:`congruence`

OUTPUT:

List of congruences, every congruence as

:class:`sage.combinat.set_partition.SetPartition`

EXAMPLES::

sage: from sage.combinat.posets.hasse_diagram import HasseDiagram

sage: N5 = HasseDiagram({0: [1, 2], 1: [4], 2: [3], 3:[4]})

sage: N5.atoms_of_congruence_lattice()

[{{0}, {1}, {2, 3}, {4}}]

sage: Hex = HasseDiagram({0: [1, 2], 1: [3], 2: [4], 3: [5], 4: [5]})

sage: Hex.atoms_of_congruence_lattice()

[{{0}, {1}, {2, 4}, {3}, {5}}, {{0}, {1, 3}, {2}, {4}, {5}}]

ALGORITHM:

Every atom is a join-irreducible. Every join-irreducible of

`\mathrm{Con}(L)` is a principal congruence generated by a

meet-irreducible element and the only element covering it (and also

by a join-irreducible element and the only element covered by it).

Hence we check those principal congruences to find the minimal ones.

"""

# Note: A lattice L if subdirectly reducible (i.e. is a sublattice

# of a Cartesian product of two smaller lattices) iff Con(L) has

# at least two atoms. That's were this is used for.

from sage.combinat.set_partition import SetPartitions

# Get smaller set, meet- or join-irreducibles

join_irreducibles = [v for v in self if self.in_degree(v) == 1]

meet_irreducibles = [v for v in self if self.out_degree(v) == 1]

if len(join_irreducibles) < len(meet_irreducibles):

irr = [(v, next(self.neighbor_in_iterator(v))) for v in join_irreducibles]

else:

irr = [(next(self.neighbor_out_iterator(v)), v) for v in meet_irreducibles]

S = SetPartitions(range(self.order()))

min_congruences = []

already_tried = []

while irr:

next_pair = irr.pop()

cong = self.congruence([next_pair], stop_pairs=already_tried)

already_tried.append(next_pair)

if cong is not None:

cong = S(cong)

min_congruences = [c for c in min_congruences if c != cong and not S.is_less_than(cong, c)]

if not any(S.is_less_than(c, cong) for c in min_congruences):

min_congruences.append(cong)

return min_congruences

def congruence(self, parts, start=None, stop_pairs=[]):

"""

Return the congruence ``start`` "extended" by ``parts``.

``start`` is assumed to be a valid congruence of the lattice,

and this is *not* checked.

INPUT:

- ``parts`` -- a list of lists; congruences to add

- ``start`` -- a disjoint set; already computed congruence (or ``None``)

- ``stop_pairs`` -- a list of pairs; list of pairs for stopping computation

OUTPUT:

``None``, if the congruence generated by ``start`` and ``parts``

together contains a block that has elements `a, b` so that ``(a, b)``

is in the list ``stop_pairs``. Otherwise the least congruence that

contains a block whose subset is `p` for every `p` in ``parts`` or

``start``, given as :class:`sage.sets.disjoint_set.DisjointSet_class`.

ALGORITHM:

Use the quadrilateral argument from page 120 of [Dav1997]_.

Basically we take one block from todo-list, search quadrilateral

blocks up and down against the block, and then complete them to

closed intervals and add to todo-list.

EXAMPLES::

sage: from sage.combinat.posets.hasse_diagram import HasseDiagram

sage: H = HasseDiagram({0: [1, 2], 1: [3], 2: [4], 3: [4]})

sage: cong = H.congruence([[0, 1]]); cong

{{0, 1, 3}, {2, 4}}

sage: H.congruence([[0, 2]], start=cong)

sage: H.congruence([[0, 1]], stop_pairs=[(1, 3)]) is None

True

TESTS::

sage: H = HasseDiagram('HT@O?GO?OE?G@??')

sage: H.congruence([[0, 1]]).number_of_subsets()

sage: H = HasseDiagram('HW_oC?@@O@?O@??')

sage: H.congruence([[0, 1]]).number_of_subsets()

Check :trac:`21861`::

sage: H = HasseDiagram({0: [1, 2], 1: [3], 2: [4], 3: [4]})

sage: tmp = H.congruence([[1, 3]])

sage: tmp.number_of_subsets()

sage: H.congruence([[0, 1]], start=tmp).number_of_subsets()

sage: tmp.number_of_subsets()

"""

from sage.sets.disjoint_set import DisjointSet

from copy import copy

n = self.order()

mt = self._meet

jn = self._join

def fill_to_interval(S):

"""

Return the smallest interval containing elements in the set S.

"""

m = n-1

for e in S:

m = mt[m, e]

j = 0

for e in S:

j = jn[j, e]

return self.interval(m, j)

cong = copy(start) if start else DisjointSet(n)

t = -1

while t != cong.number_of_subsets():

for part in parts:

if part: # Skip empty parts

c = part[0]

for e in fill_to_interval(part):

cong.union(e, c)

t = cong.number_of_subsets()

# Following is needed for cases like

# posets.BooleanLattice(3).congruence([(0,1), (0,2), (0,4)])

for c in list(cong):

r = c[0]

for v in fill_to_interval(c):

cong.union(r, v)

todo = set(cong.find(e) for part in parts for e in part)

while todo:

# First check if we should stop now.

for a, b in stop_pairs:

if cong.find(a) == cong.find(b):

return None

# We take one block and try to find as big interval

# as possible to unify as a new block by the quadrilateral

# argument.

block = sorted(cong.root_to_elements_dict()[cong.find(todo.pop())])

b = block[-1]

for a in block: # Quadrilateral up

for c in self.neighbor_out_iterator(a):

if c not in block:

d = self._join[c, b]

if cong.find(d) != cong.find(c):

break

else:

continue

break

else: # Not found, so...

a = block[0]

for b in reversed(block): # ...quadrilateral down

for d in self.neighbor_in_iterator(b):

if d not in block:

c = self._meet[d, a]

if cong.find(c) != cong.find(d):

break

else:

continue

break

else: # Nothing found

continue

# Something was found, so we put this block back to todo

# together with just found new block.

todo.add(a)

todo.add(c)

# Now the interval [c, d] will be of the same block.

# It may "crab" other blocks within, and that can be

# recursive process. In particular it may also combine to

# [a, b] block we just used.

while c is not None:

newblock = cong.find(c)

I = self.interval(c, d)

for i in I:

cong.union(newblock, i)

C = cong.root_to_elements_dict()[cong.find(newblock)]

mins = [i for i in C if all(i_ not in C for i_ in self.neighbor_in_iterator(i))]

maxs = [i for i in C if all(i_ not in C for i_ in self.neighbor_out_iterator(i))]

c = None # To stop loop, if this is not changed below.

if len(mins) > 1 or len(maxs) > 1:

c = n-1

for m in mins:

c = self._meet[c, m]

d = 0

for m in maxs:

d = self._join[d, m]

# This removes duplicates from todo.

todo = set(cong.find(x) for x in todo)

return cong

def find_nontrivial_congruence(self):

"""

Return a pair that generates non-trivial congruence or

``None`` if there is not any.

EXAMPLES::

sage: from sage.combinat.posets.hasse_diagram import HasseDiagram

sage: H = HasseDiagram({0: [1, 2], 1: [5], 2: [3, 4], 3: [5], 4: [5]})

sage: H.find_nontrivial_congruence()

{{0, 1}, {2, 3, 4, 5}}

sage: H = HasseDiagram({0: [1, 2, 3], 1: [4], 2: [4], 3: [4]})

sage: H.find_nontrivial_congruence() is None

True

ALGORITHM:

See http://www.math.hawaii.edu/~ralph/Preprints/conlat.pdf:

If `\Theta` is a join irreducible element of a `\mathrm{Con}(L)`,

then there is at least one join-irreducible `j` and one

meet-irreducible `m` such that `\Theta` is both the principal

congruence generated by `(j^*, j)`, where `j^*` is the unique

lower cover of `j`, and the principal congruence generated by

`(m, m^*)`, where `m^*` is the unique upper cover of `m`.

So, we only check join irreducibles or meet irreducibles,

whichever is a smaller set. To optimize more we stop computation

whenever it founds a pair that we know to generate one-element

congruence.

"""

join_irreducibles = [v for v in self if self.in_degree(v) == 1]

meet_irreducibles = [v for v in self if self.out_degree(v) == 1]

if len(join_irreducibles) < len(meet_irreducibles):

irr = [(v, self.neighbors_in(v)[0]) for v in join_irreducibles]

else:

irr = [(self.neighbors_out(v)[0], v) for v in meet_irreducibles]

tried = []

for pair in irr:

cong = self.congruence([pair], stop_pairs=tried)

if cong is not None and cong.number_of_subsets() > 1:

return cong

tried.append(pair)

return None

def principal_congruences_poset(self):

r"""

Return the poset of join-irreducibles of the congruence lattice.

OUTPUT:

A pair `(P, D)` where `P` is a poset and `D` is a dictionary.

Elements of `P` are pairs `(x, y)` such that `x` is an element

of the lattice and `y` is an element covering it. In the poset

`(a, b)` is less than `(c, d)` iff the principal congruence

generated by `(a, b)` is refinement of the principal congruence

generated by `(c, d)`.

`D` is a dictionary from pairs `(x, y)` to the congruence

(given as DisjointSet) generated by the pair.

EXAMPLES::

sage: from sage.combinat.posets.hasse_diagram import HasseDiagram

sage: N5 = HasseDiagram({0: [1, 2], 1: [4], 2: [3], 3: [4]})

sage: P, D = N5.principal_congruences_poset()

sage: P

Finite poset containing 3 elements

sage: P.bottom()

(2, 3)

sage: D[(2, 3)]

{{0}, {1}, {2, 3}, {4}}

"""

from sage.combinat.set_partition import SetPartition, SetPartitions

from sage.combinat.posets.posets import Poset

n = self.order()

# Select smaller set, meet- or join-irreducibles

if self.in_degree_sequence().count(1) > self.out_degree_sequence().count(1):

irr = [(e, next(self.neighbor_out_iterator(e))) for e in range(n) if self.out_degree(e) == 1]

else:

irr = [(next(self.neighbor_in_iterator(e)), e) for e in range(n) if self.in_degree(e) == 1]

D = {}

P = {}

uniq_congs = set()

for ab in irr:

cong = self.congruence([ab])

cong_ = SetPartition(cong)

if cong_ not in uniq_congs:

uniq_congs.add(cong_)

D[ab] = cong

P[ab] = cong_

# Todo: Make a function that creates the poset from a set

# by comparison function with minimal number of comparisons.

T = SetPartitions(n)

P = DiGraph([D, lambda a, b: T.is_less_than(P[a], P[b])])

return (Poset(P), D)

def congruences_iterator(self):

"""

Return an iterator over all congruences of the lattice.

EXAMPLES::

sage: from sage.combinat.posets.hasse_diagram import HasseDiagram

sage: H = HasseDiagram('GY@OQ?OW@?O?')

sage: it = H.congruences_iterator(); it

sage: sorted([cong.number_of_subsets() for cong in it])

[1, 2, 2, 2, 4, 4, 4, 8]

"""

from sage.sets.disjoint_set import DisjointSet

P, congs = self.principal_congruences_poset()

for a in P.antichains_iterator():

achain = tuple(a)

n = len(achain)

if n == 0:

yield DisjointSet(self.order())

if n == 1:

# We have congs[(x,y)], but we want congs[((x,y))].

congs[achain] = congs[a[0]]

yield congs[achain[0]]

if n > 1:

c = congs[achain[:-1]]

c = self.congruence([achain[-1]], start=c)

yield c

congs[achain] = c

def is_congruence_normal(self):

"""

Return ``True`` if the lattice can be constructed from the one-element

lattice with Day doubling constructions of convex subsets.

Subsets to double does not need to be lower nor upper pseudo-intervals.

On the other hand they must be convex, i.e. doubling a non-convex but

municipal subset will give a lattice that returns ``False`` from

this function.

EXAMPLES::

sage: from sage.combinat.posets.hasse_diagram import HasseDiagram

sage: H = HasseDiagram('IX?Q@?AG?OG?W?O@??')

sage: H.is_congruence_normal()

True

The 5-element diamond is the smallest non-example::

sage: H = HasseDiagram({0: [1, 2, 3], 1: [4], 2: [4], 3: [4]})

sage: H.is_congruence_normal()

False

This is done by doubling a non-convex subset::

sage: H = HasseDiagram('OQC?a?@CO?G_C@?GA?O??_??@?BO?A_?G??C??_?@???')

sage: H.is_congruence_normal()

False

TESTS::

sage: HasseDiagram().is_congruence_normal()

True

sage: HasseDiagram({0: []}).is_congruence_normal()

True

ALGORITHM:

See http://www.math.hawaii.edu/~jb/inflation.pdf

"""

from sage.combinat.set_partition import SetPartition

n = self.order()

congs_ji = {}

for ji in range(n):

if self.in_degree(ji) == 1:

cong = SetPartition(self.congruence([[ji, next(self.neighbor_in_iterator(ji))]]))

if cong not in congs_ji:

congs_ji[cong] = []

congs_ji[cong].append(ji)

for mi in range(n):

if self.out_degree(mi) == 1:

cong = SetPartition(self.congruence([[mi, next(self.neighbor_out_iterator(mi))]]))

if any(self.is_lequal(ji, mi) for ji in congs_ji[cong]):

return False

return True

from sage.misc.rest_index_of_methods import gen_rest_table_index

__doc__ = __doc__.format(INDEX_OF_FUNCTIONS=gen_rest_table_index(HasseDiagram))

Coverage for local/lib/python2.7/site-packages/sage/combinat/posets/hasse_diagram.py : 87%

834 statements 722 run 112 missing 0 excluded