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: |
Description (last modified by )
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
Change History (1)
comment:1 Changed 6 years ago by
- Branch set to u/ncohen/19301
- Commit set to 548b8f012647c1fae0ab8d080f2f27a382c39d51
- Description modified (diff)
- Status changed from new to needs_review
Note: See
TracTickets for help on using
tickets.
New commits:
trac #19301: Cleanup in dense_graph.pyx
trac #19301: complement()