#11736: Linear time implementation of lex_BFS()
--------------------------------+-------------------------------------------
Reporter: ddestrada | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-5.0
Component: graph theory | Resolution:
Keywords: lexbfs | Work issues:
Report Upstream: N/A | Reviewers:
Authors: | Merged in:
Dependencies: | Stopgaps:
--------------------------------+-------------------------------------------
Changes (by ncohen):
* status: needs_review => needs_work
Comment:
Helloooooo Diego !!
I'm sorry but your patch can not be applied on top of the latest release
of Sage, that is sage-5.0-beta11 (https://groups.google.com/d/topic/sage-
release/XnyN3tx4Bow/discussion). Plenty of stuff has been added in the
5.0-beta? series, and that is probably the explanation `:-)`
About your path, though : it removes the old code that computed (more
slowly) a BFS ordering for the vertices. This being said, I think this
code could still be useful to ... check that the new algorithm actually
returns a correct BFS ordering ! Of course, as it is slower, this ordering
should not be checked by default, but it would be nice to be able to run
doctests which check for each computation of BFS ordering whether this
ordering is indeed correct. This can be done by actually checking in turn
that each vertex of the ordering is maximal at the moment when it is
removed.
Do you think it could be possible to comment your code a bit more ? As it
is, reading the paper to understand what happens seems to be the only
alternative `:-)`
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11736#comment:15>
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.
