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