#17023: Adding width() function to poset
-------------------------------------+-------------------------------------
Reporter: jmantysalo | Owner:
Type: enhancement | Status: needs_review
Priority: minor | Milestone: sage-wishlist
Component: combinatorics | Resolution:
Keywords: | Merged in:
Authors: Nathann Cohen | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
public/ticket/17023 | 99f8ed04511d4422eb0874a5332132b4058d8e34
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by ncohen):
Hello !
> How fast is `connected_components()` on graphs? Because this can be done
simply by summing widths of connected subposets.
What do you mean ? If the poset is not connected you can indeed split it
and compute the result on each connected components but I don't think the
code I implemented will run any faster because of that. It would decrease
the number of antichains though. But add an element superior to all others
in your posets and you lost connectivity for the very same width.
> If posets are more "chain-like", then simply looking antichains seems to
be faster. For posets more "antichain-like" it is much faster to use this
new `.width()` method. Where is the turning point? Can there be some
heuristic based on ratio of number of edges to number of vertices?
Well, maybe there is some algorithm to recognize posets with width <=2.
And we already have a `is_chain` for width 1. Also, I think that something
like
{{{
len(Graph(posets.ChainPoset(6).hasse_diagram().transitive_closure()).independent_set())
}}}
should be a bit faster than enumerating the antichains. Even though
enumerating the antichains may be faster for very very line-looking
posets, for you don't have any graphs to copy around, ...
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/17023#comment:18>
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.
