#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 stumpc5):
> 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,
That is right -- I first had taken the connected components into account
as Darij and Anne did it, but in the examples I had it was always faster
to not first compute th connected components. A second thing I had was to
delete an edge after it was found to have both vertices ranked and the
rank comparison tested (since we will not get any new info back from doing
this test again). But also that seemed to take for small posets more time
than running through all edges again and again.
I guess that for larger posets, it is worth first computing the connected
components (but only because that is done in the backbone of graphs and
thus really fast), and also deleting edges that are not needed anymore.
Do you first want me to put these things in my algo, or do you wanna do
it?
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12993#comment:11>
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.
