#11623: small optimization to girth
----------------------------+-----------------------------------------------
Reporter: rlm | Owner: jason, ncohen, rlm
Type: enhancement | Status: new
Priority: major | Milestone: sage-4.7.2
Component: graph theory | Keywords:
Work_issues: | Upstream: N/A
Reviewer: | Author: Robert Miller
Merged: | Dependencies:
----------------------------+-----------------------------------------------
{{{
Dear Robert,
I am currently studying parallel girth graph implementations (e.g. openmp,
cuda).
While comparing our parallel algorithm against various known girth
algorithms I found
your sage patch.
http://trac.sagemath.org/sage_trac/attachment/ticket/2685/2685-girth.patch
I note that your code is almost identical to my sequential algorithm
except there
is one small optimization you can add to your function to slightly improve
its performance.
WLOG, when searching from start node index 'i' you can safely ignore nodes
with smaller index u<i
and they don't need to be added to your nextList.
E.g. in your code replace:
...
for u in G.neighbors(v):
if not span[u]:
...
with
...
for u in G.neighbors(v):
if u<i: continue
if not span[u]:
...
Regards, Michael
--
Dr. Michael J. Dinneen (Computer Science/University of Auckland)
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11623>
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.
