id,summary,reporter,owner,description,type,status,priority,milestone,component,resolution,keywords,cc,merged,author,reviewer,upstream,work_issues,branch,commit,dependencies,stopgaps
19301,Improved Graph.complement() (and cleanup in dense_graph.pyx),ncohen,,"This branch improves the algorithm behind `Graph.complement()`, which currently calls `has_edge(u,v)` for every pair of points.
With this, the computation of the complement is done on a dense graph, as it should.
Before
{{{
sage: g=graphs.PaleyGraph(1009)
sage: %time g.complement()
CPU times: user 2.14 s, sys: 64 ms, total: 2.2 s
Wall time: 2.14 s
complement(Paley graph with parameter 1009): Graph on 1009 vertices
}}}
After
{{{
sage: %time g.complement()
CPU times: user 164 ms, sys: 12 ms, total: 176 ms
Wall time: 160 ms
complement(Paley graph with parameter 1009): Graph on 1009 vertices
}}}
In dense_graph.pyx, this branch mostly does the following:
- Turn 'radix' and radix_mod_mask' into module variables (they do not depend on the instance)
- remove 'radix_div_shift'. This variable is meant to turn a division by radix into a shift. As radix is determined at compile-time, the compiler already does this simplification (for free)
- Turn multiplication/division by powers of two from 'shift' to multiplication/division. The code is easier to read, and the compiled binary is the same anyway.
- Uses calloc (instead of malloc) to initialize memory. This is slightly wasteful, and the code is much cleaner as a result.
Nathann",enhancement,closed,major,sage-6.9,graph theory,fixed,,vdelecroix dimpase dcoudert borassi,,Nathann Cohen,David Coudert,N/A,,0d806488874034fc5d47ffd6603880256b4e79f2,0d806488874034fc5d47ffd6603880256b4e79f2,,