#19659: Poset: inverse function of ordinal_sum()
-----------------------------+----------------------------------
Reporter: jmantysalo | Owner:
Type: enhancement | Status: new
Priority: major | Milestone: sage-6.10
Component: combinatorics | Keywords: poset
Merged in: | Authors: Jori Mäntysalo
Reviewers: | Report Upstream: N/A
Work issues: | Branch:
Commit: | Dependencies:
Stopgaps: |
-----------------------------+----------------------------------
I suggest adding a function that decomposes a poset "vertically", i.e. has
same relationship to `ordinal_sum()` as `connected_components()` has to
`disjoint_union()`.
I am not sure about the name. Work name is `ordinal_decomposition`. Maybe
it could be `ordinal_components` or `vertical_components`.
Here is the code to add to `hasse_diagram.py`. I suppose not to have time
to make this a patch file for few days. Feel free to comment.
{{{
def ordinal_decomposition(self):
r"""
Return the ordinal decomposition of the poset.
This function is kind of inverse to ordinal_sum(). Ordinal
decomposition of a poset `P` is the list of posets
`P_1, \ldots, P_n` so that `P` is ordinal decomposition of them.
OUTPUT:
List of numbers `e_1, \ldots, e_n`
so that `P_1` is subposet containing `0, \ldots, e_1`,
`P_2` is subposet containing `e_1+1, \ldots, e_2` and so on.
ALGORITHM::
Suppose that poset `P` is the ordinal sum of posets `L` and
`U`. Then `P` contains maximal antichains `l` and `u` such that
every element of `u` covers exactly every element of `l` and
every element of `l` is covered by exactly every element of `u`;
they
correspond to maximal elements of `L` and minimal elements
of `U`.
We know that the Hasse diagram is a topologically sorted DAG,
starting numbering from zero. Hence, if `L` has `n` elements,
then `l` contains element `n-1` and `u` contains element
`n`.
We keep track of the maximal elements of subposet induced
by elements 0..e and minimal elements of subposet induced
by elements e+1..n, incrementing e one by one. Then we just
check if they can be `l` and `u` in previous description.
EXAMPLES::
sage: from sage.combinat.posets.hasse_diagram import HasseDiagram
sage: H = HasseDiagram({0:[2], 1:[2, 3], 2:[4, 5, 6], 3:[4, 5, 6],
....: 4:[7], 5:[7], 6:[7], 7:[8]})
sage: H.ordinal_decomposition()
[3, 6, 7, 8]
TESTS::
sage: from sage.misc.prandom import randint
sage: n = randint(1, 10)
sage: P = Posets.RandomPoset(n, 0.1)
sage: H = P.ordinal_sum(P)._hasse_diagram
sage: m = H.ordinal_decomposition()
sage: n in m
True
"""
cut_points = []
n = self.order()
in_degrees = [len(self.neighbors_in(e)) for e in range(n)]
lower = set([])
upper = set(self.sources())
for e in range(n):
lower.add(e)
for lc in self.neighbors_in(e):
lower.discard(lc)
upper.discard(e)
up_covers = self.neighbors_out(e)
for uc in up_covers:
in_degrees[uc] -= 1
if in_degrees[uc] == 0:
upper.add(uc)
if e+1 in up_covers:
for l in lower:
if set(self.neighbors_out(l)) != upper:
break
else:
cut_points.append(e)
cut_points.append(n-1)
return cut_points
}}}
--
Ticket URL: <http://trac.sagemath.org/ticket/19659>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
