#19659: Poset: inverse function of ordinal_sum()
-------------------------------------+-------------------------------------
Reporter: jmantysalo | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.10
Component: combinatorics | Resolution:
Keywords: poset | Merged in:
Authors: Jori Mäntysalo | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/jmantysalo/develop | fcd68b964edd9abc071b32d49e90818f86073f01
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Changes (by jmantysalo):
* status: new => needs_review
* commit: => fcd68b964edd9abc071b32d49e90818f86073f01
Old description:
> 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
> }}}
New description:
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()`. This ticket contains code for the "backend", i.e. to
`hasse_diagram.py`.
I am not sure about the name. Maybe `ordinal_decomposition`. Or maybe it
could be `ordinal_components` or `vertical_components`.
Bonus question: What should be the name for inverse function of
`ordinal_product()`?
--
Comment:
New commits:
||[http://git.sagemath.org/sage.git/commit/?id=d1d6f4baf5430150855d1ba5630aa181d9cba421
d1d6f4b]||{{{Added ordinal_sum_decomposition().}}}||
||[http://git.sagemath.org/sage.git/commit/?id=fcd68b964edd9abc071b32d49e90818f86073f01
fcd68b9]||{{{Spaces removed.}}}||
--
Ticket URL: <http://trac.sagemath.org/ticket/19659#comment:2>
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.
