Opened 6 years ago
Closed 6 years ago
#19301 closed enhancement (fixed)
Improved Graph.complement() (and cleanup in dense_graph.pyx)
Reported by:  ncohen  Owned by:  

Priority:  major  Milestone:  sage6.9 
Component:  graph theory  Keywords:  
Cc:  vdelecroix, dimpase, dcoudert, borassi  Merged in:  
Authors:  Nathann Cohen  Reviewers:  David Coudert 
Report Upstream:  N/A  Work issues:  
Branch:  0d80648 (Commits, GitHub, GitLab)  Commit:  0d806488874034fc5d47ffd6603880256b4e79f2 
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 compiletime, 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 (9)
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
comment:2 followup: ↓ 3 Changed 6 years ago by
I like this patch ;)
However, there is a small issue:
sage t long src/sage/graphs/generic_graph.py ********************************************************************** File "src/sage/graphs/generic_graph.py", line 16320, in sage.graphs.generic_graph.GenericGraph.complement Failed example: G.complement() Expected: Traceback (most recent call last): ... TypeError: complement not well defined for (di)graphs with multiple edges Got: <BLANKLINE> Traceback (most recent call last): File "/Users/dcoudert/sage/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 496, in _run self.compile_and_execute(example, compiler, test.globs) File "/Users/dcoudert/sage/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 858, in compile_and_execute exec(compiled, globs) File "<doctest sage.graphs.generic_graph.GenericGraph.complement[9]>", line 1, in <module> G.complement() File "/Users/dcoudert/sage/local/lib/python2.7/sitepackages/sage/graphs/generic_graph.py", line 16341, in complement self._scream_if_not_simple() File "/Users/dcoudert/sage/local/lib/python2.7/sitepackages/sage/graphs/generic_graph.py", line 1257, in _scream_if_not_simple raise ValueError(msg) ValueError: This method is not known to work on graphs with multiedges. Perhaps this method can be updated to handle them, but in the meantime if you want to use it please disallow multiedges using allow_multiple_edges(). ********************************************************************** 1 item had failures: 1 of 15 in sage.graphs.generic_graph.GenericGraph.complement [2950 tests, 1 failure, 56.23 s]  sage t long src/sage/graphs/generic_graph.py # 1 doctest failed 
Sorry, I know you don't like multiple edges ;)
comment:3 in reply to: ↑ 2 Changed 6 years ago by
Yo !
I like this patch ;)
Yeah, me too. I have been giving a bad look to this complement
function for a long time now, as it was clearly wasteful. Incidentally, this will "produce" many graphs with a 'dense' backend, while they are mostly nonexistent in Sage nowadays. Perhaps new bugs related to this backend will pop out, or none if we are lucky.
However, there is a small issue:
Arg, right. There were *two* checks for multiple edges in the same function, so I removed one but the error message changed. Will be fixed in a second.
Nathann
comment:4 Changed 6 years ago by
 Commit changed from 548b8f012647c1fae0ab8d080f2f27a382c39d51 to 0d806488874034fc5d47ffd6603880256b4e79f2
Branch pushed to git repo; I updated commit sha1. New commits:
0d80648  trac #19301: Doctest

comment:5 followup: ↓ 6 Changed 6 years ago by
Passes all tests on src/sage/graphs/
.
Why don't you use check_allocarray
or MemoryAllocator
?
comment:6 in reply to: ↑ 5 Changed 6 years ago by
Why don't you use
check_allocarray
orMemoryAllocator
?
Because those pointers are sometimes reallocated (function 'resize'), and the two would not mix well.
Nathann
comment:7 Changed 6 years ago by
 Reviewers set to David Coudert
 Status changed from needs_review to positive_review
Then the patch is good to go.
comment:8 Changed 6 years ago by
Thanks !
comment:9 Changed 6 years ago by
 Branch changed from u/ncohen/19301 to 0d806488874034fc5d47ffd6603880256b4e79f2
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
trac #19301: Cleanup in dense_graph.pyx
trac #19301: complement()