#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:
Authors: Darij Grinberg, Anne Schilling | Merged in:
Dependencies: | Stopgaps:
--------------------------------------------------+-------------------------
Comment (by saliola):
Christian,
Nice idea to use the {{{rank_function}}} for the plot method!
I don't like this loop:
{{{
579 for i,j in edges: # to find new
elements, we run through all edges of the Hasse diagram
580 if i in rank_fcn:
...
589 else:
590 if j in rank_fcn: # as above
}}}
This means that you will be looking at edges multiple times until one of
them has been assigned a rank. You are also looking at edges in other
connected components. If there are several connected components, then this
will take too long. For example,
{{{
sage: P = lambda n : Poset([range(n), [(i,i+1) for i in range(0,n,2)]])
sage: time p = P(10000); p
Time: CPU 2.32 s, Wall: 2.32 s
Finite poset containing 10000 elements
sage: time p.is_ranked()
True
Time: CPU 13.35 s, Wall: 13.36 s
}}}
With Darij and Anne's patch, this only takes 0.99s.
I'm preparing a patch right now to address this.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12993#comment:10>
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.
