Opened 6 years ago

Last modified 6 years ago

#19301 closed enhancement

Improved Graph.complement() (and cleanup in dense_graph.pyx) — at Version 1

Reported by: ncohen Owned by:
Priority: major Milestone: sage-6.9
Component: graph theory Keywords:
Cc: vdelecroix, dimpase, dcoudert, borassi Merged in:
Authors: Nathann Cohen Reviewers:
Report Upstream: N/A Work issues:
Branch: u/ncohen/19301 (Commits, GitHub, GitLab) Commit: 548b8f012647c1fae0ab8d080f2f27a382c39d51
Dependencies: Stopgaps:

Status badges

Description (last modified by 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.


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


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.


Change History (1)

comment:1 Changed 6 years ago by ncohen

  • Branch set to u/ncohen/19301
  • Commit set to 548b8f012647c1fae0ab8d080f2f27a382c39d51
  • Description modified (diff)
  • Status changed from new to needs_review

New commits:

f6b88edtrac #19301: Cleanup in dense_graph.pyx
548b8f0trac #19301: complement()
Note: See TracTickets for help on using tickets.