#19301: Improved Graph.complement() (and cleanup in dense_graph.pyx)
-------------------------+-------------------------------------------------
Reporter: | Owner:
ncohen | Status: needs_review
Type: | Milestone: sage-6.9
enhancement | Resolution:
Priority: major | Merged in:
Component: graph | Reviewers:
theory | Work issues:
Keywords: | Commit:
Authors: | 548b8f012647c1fae0ab8d080f2f27a382c39d51
Nathann Cohen | Stopgaps:
Report Upstream: N/A |
Branch: |
u/ncohen/19301 |
Dependencies: |
-------------------------+-------------------------------------------------
Changes (by ncohen):
* status: new => needs_review
* commit: => 548b8f012647c1fae0ab8d080f2f27a382c39d51
* branch: => u/ncohen/19301
Old description:
> 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.
>
> Nathann
New description:
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
--
Comment:
New commits:
||[http://git.sagemath.org/sage.git/commit/?id=f6b88ed88f106904bd548e1d2cafbaca75b75d1e
f6b88ed]||{{{trac #19301: Cleanup in dense_graph.pyx}}}||
||[http://git.sagemath.org/sage.git/commit/?id=548b8f012647c1fae0ab8d080f2f27a382c39d51
548b8f0]||{{{trac #19301: complement()}}}||
--
Ticket URL: <http://trac.sagemath.org/ticket/19301#comment:1>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
