Easier handling of vertex labels in graph backends

[nathanncohen]

This ticket addresses the following problem:

In the `CGraph` backends, three `cdef` functions are used all the time to
deal with vertex labels, i.e. `get_vertex`, `vertex_label`,

check_vertex. They are always called with the same arguments, which are
all attributes of the backend that calls it. They should be method, so that
the arguments are not needlessly repeated.

What this branch does:

• The CGraph backends (i.e. SparseBackend, DenseBackend and
  StaticSparseGraph) and GenericGraphBackend are turned into cdef classes.

• The three functions get_vertex, vertex_label, check_vertex become
  methods of CGraphBackend

• It adds a method CGraphBackend.c_graph() to get the two cdef attributes
  _cg and _cg_rev. Turns out that some code in Sage accesses directly
  G._backend._cg.

This should have been sufficient, but there were (unexpected) consequences:

• There is no automatic pickling for cdef classes (as instrospection does not
  work), and the doctests do not pass if that does not work. Consequently, I
  implemented a unique __reduce__ function in GenericGraphBackend which
  handles the pickling for all backends (sparse/dense/static/networkx). It also
  removes some duplicated code as a result.

This makes the code a bit clearer (and it is needed). Also, moving this pickling
function above is good for the future, for there will be many modifications in
the future to the data structures in Sage: I plan to merge CGraph and
GenericBackend into only one class (but that's for later).

Nathann

P.S.: The branch is built to be reviewed commit by commit. In particular, the renamed file appears as trivial when looking at the first commit, but as a lot of + and - when looking at the branch's diff

Depends on #18317

CC: @sagetrac-borassi @dcoudert @darijgr @videlec

Component: graph theory

Author: Nathann Cohen

Branch/Commit: 6ffbb05

Reviewer: Vincent Delecroix

Issue created by migration from https://trac.sagemath.org/ticket/18346

[nathanncohen]

New commits:

9e60492	trac #18346: Make graph_backends.py into a .pyx
da8479e	trac #18346: Move and indent three functions (nothing else is changed)
5b765e1	trac #18346: Rename calls to [get_vertex, vertex_label, check_vertex] into self.method calls
2704dda	trac #18346: Turn the backends into cdef classes
e11d4d8	trac #18346: New pickling function for GraphBackend
bd8d988	trac #18346: Remove old `__reduce__` functions and move useful doctests
30eb626	trac #18346: Some python code accesses G._backend._cg directly
25765bb	trac #18346: A 'cdef class' is a 'type', not a 'class'

[nathanncohen]

Branch: public/18346

[nathanncohen]

Commit: 25765bb

[videlec]

comment:3

Hello,

1. Would it be bad to access directly the ._cg or ._cg_rev attributes? (ok it seems to be for python code)

2. Is there a description somewhere of the attributes vertex_ints and vertex_labels?

3. In a cython file, there is no need to declare cdef object x or object x, just do x.

Vincent

[nathanncohen]

comment:5

Hello,

1. Would it be bad to access directly the ._cg or ._cg_rev attributes? (ok it seems to be for python code)

I do not think that it is if you do not modify them. Some functions (like isomorphism test) use it directly. The guy who wrote the code that does that knew what he was doing, unfortunately he is the only one :-P

2. Is there a description somewhere of the attributes vertex_ints and vertex_labels?

Not that I know. I am not sure that I remember exactly what they do either. What I remember is that not all vertices have an associated label, so that you don't spend your time playing with a dictionary when your graph is defined over integers.

This being said, I plan to rewrite all this (and of course the new code will have a proper documentation). I spent several hours thinking of how this should all be done, and my hardest constraint was that the changes should be "reviewable". Which is not very easily achieved when you plan to merge two classes together :-P

The 'first step' was #18185, the second is this one (or #18317, but that's only doc). Then I will turn NetworkX backend into a CGraph, and deprecate a lot of things in there. And then... Merge the classes O_O;;

3. In a cython file, there is no need to declare cdef object x or object x, just do x.

Okay. Well, I don't think I did anything like that but I may have met such a line somewhere. Really, this does not matter for the moment: this code will be heavily rewritten.

Nathann

[videlec]

comment:6

Hello,

Replying to @nathanncohen:

2. Is there a description somewhere of the attributes vertex_ints and vertex_labels?

Not that I know. I am not sure that I remember exactly what they do either. What I remember is that not all vertices have an associated label, so that you don't spend your time playing with a dictionary when your graph is defined over integers.

Actually you do since get_vertex or vertex_label are intensively used everywhere. And those methods do check if their argument belongs to some dictionary as a first step! But if I understand well, the aim of the ticket is precisely not to upgrade these two methods but just to move them.

3. In a cython file, there is no need to declare cdef object x or object x, just do x.

Okay. Well, I don't think I did anything like that but I may have met such a line somewhere. Really, this does not matter for the moment: this code will be heavily rewritten.

Hum

+ cdef int get_vertex(self, object u) except ? -2
+ cdef object vertex_label(self, int u_int)

this would better be

cdef int get_vertex(self, u) except ? -2
cdef vertex_label(self, int u_int)

Vincent

[sagetrac-git]

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

c626eec

trac #18346: Without useless 'objects'

[sagetrac-git]

Changed commit from 25765bb to c626eec

[nathanncohen]

comment:8

Yo !

Actually you do since get_vertex or vertex_label are intensively used everywhere. And those methods do check if their argument belongs to some dictionary as a first step!

Oh really? But perhaps the dictionary does not contain the integers then? Anyway, does not matter much.

But if I understand well, the aim of the ticket is precisely not to upgrade these two methods but just to move them.

The aim of this ticket is to merge CGraph and Backend together. All that "backend" does is forward everything to CGraph. But I certainly cannot do all of this at once, it would be impossible to review. Plus because of the problems I met when writing this branch, I know that I should be wary of the isomorphism test code which works at a lower level than I expected.

Hum

+ cdef int get_vertex(self, object u) except ? -2
+ cdef object vertex_label(self, int u_int)

Fixed. Actually, those are the lines that I moved from functions to methods. You will find (almost) the same lines with a '-' in front of them, a couple of lines above.

Nathann

[videlec]

comment:9

Replying to @nathanncohen:

The aim of this ticket is to merge CGraph and Backend together. All that "backend" does is forward everything to CGraph. But I certainly cannot do all of this at once, it would be impossible to review. Plus because of the problems I met when writing this branch, I know that I should be wary of the isomorphism test code which works at a lower level than I expected.

Will you keep these get_vertex and vertex_label forever? If you do so I will had a commit to optimize them. They are basically used everywhere.

Vincent

[nathanncohen]

comment:10

Will you keep these get_vertex and vertex_label forever? If you do so I will had a commit to optimize them. They are basically used everywhere.

I have no idea for the moment. If there is something you want to change, it really cannot hurt.

Nathann

[sagetrac-git]

Changed commit from c626eec to d921cd9

[sagetrac-git]

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

d921cd9

Trac 18346: tiny cleanup and optimization

[videlec]

comment:12

I win some very precious nano seconds and add a tiny bit of documentation for vertex_labels and vertex_ints. I will start reviewing your other commits.

Vincent

[nathanncohen]

comment:13

Heuuuuuuu... Sorry Vincent but I am not really sure that what this code needs is 10 more lines to convert integer types from one to another....

And if you remove some 'object', please remove them from the .pxd file too.

[nathanncohen]

comment:14

If this kind of cast from !Python/!Sage integer is really costly, perhaps we should have a cdef function that does it somewhere? Do I make a mistake if I say that you wrote this code in order to avoid having to raise an exception in many cases ?

Nathann

[videlec]

comment:15

Replying to @nathanncohen:

If this kind of cast from !Python/!Sage integer is really costly, perhaps we should have a cdef function that does it somewhere?

That's a possibility, but it is not clear what should be the signature of the function. What if it fails?

Do I make a mistake if I say that you wrote this code in order to avoid having to raise an exception in many cases?

It is not only that: calling directyl mpz_get_si or PyInt_AS_LONG is faster than the cast which does call PyInt_AsLong. But that's true that I do not like this try/except.

[nathanncohen]

comment:16

Yo !

That's a possibility, but it is not clear what should be the signature of the function. What if it fails?

LONG_MAX ?

It is not only that: calling directyl mpz_get_si or PyInt_AS_LONG is faster than the cast which does call PyInt_AsLong. But that's true that I do not like this try/except.

Well, if you can turn it into an independent function in some other module (something integer-related) then no problem. This code is much more in need of clarity than nanoseconds at the moment :-P

Nathann

[sagetrac-git]

Changed commit from d921cd9 to 6318944

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

efd07b7	Trac 18346: optimization of get_vertex
6318944	Trac 18346: some cleanup

[videlec]

comment:18

Hello,

Do whatever you want with efd07b7. The rest of the cleanup is isolated in 6318944.

Vincent

[nathanncohen]

comment:19

Do whatever you want with efd07b7. The rest of the cleanup is isolated in 6318944.

If you do not plan to turn the integer tests into a an independent function, then can you discard it?

[videlec]

comment:20

Replying to @nathanncohen:

Do whatever you want with efd07b7. The rest of the cleanup is isolated in 6318944.

If you do not plan to turn the integer tests into a an independent function, then can you discard it?

yes

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

e8df618

Trac 18346: some cleanup

[sagetrac-git]

Changed commit from 6318944 to e8df618

[videlec]

comment:22

I am done with reviewing your commits and they are fine.

So if e8df618 is fine for you, then it can go.

[videlec]

Reviewer: Vincent Delecroix

[nathanncohen]

comment:23

Yoooooooooo !

I am done with reviewing your commits and they are fine.

So if e8df618 is fine for you, then it can go.

Oh. Great, thanks !! I was reviewing that commit. I should be done in 10 minutes.

Nathann

[nathanncohen]

comment:24

If you feel like messing with a new subfolder of src/, I cleaned a couple of things from finance/ in #18355 ;-)

[nathanncohen]

comment:25

Okayokay, it's all good. Thank you very much for your help with these painful patches ^^;

Nathann

[vbraun]

comment:26

sage -t --long src/sage/graphs/base/overview.py
**********************************************************************
File "src/sage/graphs/base/overview.py", line 50, in sage.graphs.base.overview
Failed example:
    Graph()._backend
Expected:
    <class 'sage.graphs.base.sparse_graph.SparseGraphBackend'>
Got:
    <type 'sage.graphs.base.sparse_graph.SparseGraphBackend'>
**********************************************************************
1 item had failures:
   1 of   2 in sage.graphs.base.overview
    [1 test, 1 failure, 0.01 s]

[videlec]

comment:27

Replying to @nathanncohen:

If this kind of cast from !Python/!Sage integer is really costly, perhaps we should have a cdef function that does it somewhere? Do I make a mistake if I say that you wrote this code in order to avoid having to raise an exception in many cases ?

The proper solution to "convert" a Python object u into a long is

cdef long u_long = PyNumber_Index(u)

see

https://groups.google.com/forum/#!topic/sage-support/0ATjCgQlq4c

Vincent

[sagetrac-git]

Changed commit from e8df618 to 6ffbb05

[sagetrac-git]

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

8d61e56	trac #18317: General documentation about graph data structures
b7d9036	trac #18317: Reviewer's comments
2c02e23	trac #18317: Merged with 6.7.beta3
c6678ce	trac #18317: Review
4378790	trac #18317: Delete(s)
2caff2f	trac #18346: Merge with #18317
6ffbb05	trac #18346; Broken doctest

[nathanncohen]

Dependencies: #18317

[vbraun]

Changed branch from public/18346 to 6ffbb05