#12993: Bug in computing the rank function a poset
--------------------------------------------------+-------------------------
Reporter: saliola | Owner:
sage-combinat
Type: defect | Status:
needs_review
Priority: major | Milestone: sage-5.1
Component: combinatorics | Resolution:
Keywords: poset, combinat | Work issues:
Report Upstream: N/A | Reviewers: Christian
Stump, Franco Saliola
Authors: Darij Grinberg, Anne Schilling | Merged in:
Dependencies: | Stopgaps:
--------------------------------------------------+-------------------------
Comment (by saliola):
Replying to [comment:16 stumpc5]:
> Replying to [comment:12 saliola]:
> > Here is a review patch. Apply on top of Christian's review patch
(which goes on top of Anne's).
> >
> > It looks at each edge exactly twice.
>
> your code is certainly cleaner than mine was!
>
> I don't see why, but my method seems to be twice as fast for boolean
lattices (tested with up to sets of size 8). I would still vote for
keeping yours since you have examples where it is much faster, and the
code is nicer as well.
Thanks for pushing my patch.
The algorithm starts with some vertex, and propagates the value of the
rank function along incoming ''and'' outgoing edges. If there is a unique
minimal vertex in each connected component, then we could just use
outgoing edges starting from that minimal vertex. Otherwise, we have to go
backwards along some edges.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12993#comment:17>
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 post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
