Opened 3 years ago

Closed 3 years ago

#19301 closed enhancement (fixed)

Improved Graph.complement() (and cleanup in dense_graph.pyx)

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: David Coudert
Report Upstream: N/A Work issues:
Branch: 0d80648 (Commits) Commit: 0d806488874034fc5d47ffd6603880256b4e79f2
Dependencies: Stopgaps:

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.

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 (9)

comment:1 Changed 3 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()

comment:2 follow-up: Changed 3 years ago by dcoudert

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/site-packages/sage/doctest/forker.py", line 496, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/Users/dcoudert/sage/local/lib/python2.7/site-packages/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/site-packages/sage/graphs/generic_graph.py", line 16341, in complement
        self._scream_if_not_simple()
      File "/Users/dcoudert/sage/local/lib/python2.7/site-packages/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 3 years ago by ncohen

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 non-existent 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 3 years ago by git

  • Commit changed from 548b8f012647c1fae0ab8d080f2f27a382c39d51 to 0d806488874034fc5d47ffd6603880256b4e79f2

Branch pushed to git repo; I updated commit sha1. New commits:

0d80648trac #19301: Doctest

comment:5 follow-up: Changed 3 years ago by dcoudert

Passes all tests on src/sage/graphs/.

Why don't you use check_allocarray or MemoryAllocator?

comment:6 in reply to: ↑ 5 Changed 3 years ago by ncohen

Why don't you use check_allocarray or MemoryAllocator?

Because those pointers are sometimes reallocated (function 'resize'), and the two would not mix well.

Nathann

comment:7 Changed 3 years ago by dcoudert

  • Reviewers set to David Coudert
  • Status changed from needs_review to positive_review

Then the patch is good to go.

comment:8 Changed 3 years ago by ncohen

Thanks !

comment:9 Changed 3 years ago by vbraun

  • Branch changed from u/ncohen/19301 to 0d806488874034fc5d47ffd6603880256b4e79f2
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.