id,summary,reporter,owner,description,type,status,priority,milestone,component,resolution,keywords,cc,work_issues,upstream,reviewer,author,merged,dependencies,stopgaps
11623,small optimization to girth,rlm,"jason, ncohen, rlm","{{{
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)
}}}",enhancement,closed,major,sage-4.7.2,graph theory,fixed,,,,N/A,Nathann Cohen,Robert Miller,sage-4.7.2.alpha2,,