directed immutable graphs report twice too many edges

[nathanncohen]

As reported on #15278 :

sage: g=digraphs.RandomDirectedGNP(10,.3)
sage: gi=DiGraph(g,data_structure="static_sparse")
sage: print gi.size(), len(gi.edges())
68 34

Simplest bug eve : Sage was taught to return the wrong thing. The sum of all arcs in the digraph, plus the sum of all arcs in the reversed digraph. That's clearly more than necessary :-P

Sorryyyyyyyyyyyyyyyyyyyy !!

Nathann

CC: @simon-king-jena

Component: graph theory

Author: Nathann Cohen

Branch/Commit: u/ncohen/15491 @ 020cc82

Reviewer: Simon King

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

[nathanncohen]

Branch: u/ncohen/15491

[sagetrac-git]

Commit: cd97926

[sagetrac-git]

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

[cd97926](https://github.com/sagemath/sagetrac-mirror/commit/cd97926)

trac #15491: directed immutable graphs report twice too many edges

[simon-king-jena]

comment:3

For a review, I need some information on num_edges(self,directed).

• In the doc string, you start to tell us something:

        INPUT:
  
        - ``directed`` (boolean) -- whether to consider the graph as directed or
          not (
  

  Should there be some explanation after the opening bracket, or should the opening bracket be removed?

• You define cdef unsigned int m but don't use it. I guess this should be removed.

• In the case of an undirected graph whose number of directed edges are requested, you do return int(cg.g.neighbors[cg.g.n]-cg.g.edges). Can you please explain why this is equal to twice the number of edges minus the number of loops? In static_sparse_graph.pyx I read

    * ``neighbors`` (``unsigned short **``) -- this array has size `n+1`, and
      describes how the data of ``edges`` should be read : the neighbors of
      vertex `i` are the elements of ``edges`` addressed by
      ``neighbors[i]...neighbors[i+1]-1``. The element ``neighbors[n]``, which
      corresponds to no vertex (they are numbered from `0` to `n-1`) is present
      so that it remains easy to enumerate the neighbors of vertex `n-1` : the
      last of them is the element addressed by ``neighbors[n]-1``.
  

  By combining both comments, I guess that neighbors[n] gives three times the number of edges minus the number of loops (so that cg.g.neighbors[cg.g.n]-cg.g.edges is two times the number of edges minus the number of loops, as requested), and thus the last neighbour of vertex n-1 is three times the number of edges minus the number of loops minus one---but if that's the case then it should be stated somewhere.

Also there is trailing whitespace in error messages:

                raise NotImplementedError("Sorry, I have no idea what is expected "
                                          "in this situation. I don't think "
                                          "that it is well-defined either, "
                                          "especially for multigraphs.")

And I think the French rules of typography shouldn't be used in an English text. Hence, replace bla : bla by bla: bla. I guess this will be part of a review commit.

[simon-king-jena]

comment:4

Sorry, I just notice that

                raise NotImplementedError("Sorry, I have no idea what is expected "
                                          "in this situation. I don't think "
                                          "that it is well-defined either, "
                                          "especially for multigraphs.")

becomes

NotImplementedError: Sorry, I have no idea what is expected in this situation. I don't think that it is well-defined either, especially for multigraphs.

So, no trailing whitespace.

[nathanncohen]

comment:5

Yo !

For a review, I need some information on num_edges(self,directed).

Okay. Just to make things clear, I don't like this function, it was just part of the sparse_graph backend and so I implemented the very same for this new backend.

• In the doc string, you start to tell us something:

I removed the ).

• You define cdef unsigned int m but don't use it. I guess this should be removed.

Done.

• In the case of an undirected graph whose number of directed edges are requested, you do return int(cg.g.neighbors[cg.g.n]-cg.g.edges). Can you please explain why this is equal to twice the number of edges minus the number of loops?

cg.g.edges is not equal to the number of edges. It is a pointer toward the beginning of the edges array. cg.g.edges is actually equal to cg.g.neighbors[0]. I added a line of doc to emphasize it. I'm substracting pointers there, not integers.

Also there is trailing whitespace in error messages:

                raise NotImplementedError("Sorry, I have no idea what is expected "
                                          "in this situation. I don't think "
                                          "that it is well-defined either, "
                                          "especially for multigraphs.")

Which trailing whitespace ? O_o
You mean the spaces just before the " ? If I remove them you will see "expectedin" and "thinkthat" when the message is displayed. I added a doctest to make this clear.

And I think the French rules of typography shouldn't be used in an English text. Hence, replace bla : bla by bla: bla. I guess this will be part of a review commit.

There is no occurrence of " : " in this file, and to be honest I could not care less about the spaces between and after the ":". I am french, and most of the books I read are english. I don't care whether there is a " : " or ": ", I don't even notice the difference. My problem with spaces before/after ":" is that there are grammar nazis on both sides : the english complain when I put spaces, the french when I don't. Honestly do whatever you want with that. Though there again, I couldn't find any occurrence of " : " in that file.

Nathann

[sagetrac-git]

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

[020cc82](https://github.com/sagemath/sagetrac-mirror/commit/020cc82)

trac #15491: addressing the reviewer's comments

[sagetrac-git]

Changed commit from cd97926 to 020cc82

[simon-king-jena]

comment:7

Replying to @nathanncohen:

Okay. Just to make things clear, I don't like this function, ...

I don't like it either, but I do like if equal graphs evaluate equal.

cg.g.edges is not equal to the number of edges. It is a pointer toward the beginning of the edges array. cg.g.edges is actually equal to cg.g.neighbors[0]. I added a line of doc to emphasize it. I'm substracting pointers there, not integers.

Aha, I see. Pointers are mind bending.

Which trailing whitespace ? O_o
You mean the spaces just before the " ? If I remove them you will see "expectedin" and "thinkthat" when the message is displayed.

Yes, I have not been aware that Python lets you do those things. I thought that

("h"
"e"
"l"
"l"
"o")

is a syntax error, but it results in 'hello'.

I added a doctest to make this clear.

Good idea.

There is no occurrence of " : " in this file,

There is one in the doc string that I cited.

the english complain when I put spaces, the french when I don't.

I don't like imposing rules of one language to another language. There are stories of Germans named, e.g., "Müller", having problems with US cops, because the cops wouldn't even notice that there are dots over the "u" in the guy's passport, and would certainly not accept that the correct way to spell this German name on a keyboard without Umlaut is "Mueller" and not "Muller". Actually I hate myself for writing "Groebner" instead of "Gröbner" in Sage doc strings (but at least I don't write "Grobner").

Of course, errors can occur, specifically when writing text in a foreign language, and an extra space certainly is not a big drama (I am not calling you an imperialist : :-P). Since the above mentioned doc string is from static_sparse_graph.pyx and thus from a file that your commits don't touch, I'd say one shouldn't try to fix it here.

[nathanncohen]

comment:8

Yooooooooooo !!

I don't like it either, but I do like if equal graphs evaluate equal.

I can't say I like that equal graphs evaluate equal, but I certainly grew used to it.

Aha, I see. Pointers are mind bending.

They are.

There is one in the doc string that I cited.

Oh. Right.

the english complain when I put spaces, the french when I don't.

I don't like imposing rules of one language to another language. There are stories of Germans named, e.g., "Müller", having problems with US cops, because the cops wouldn't even notice that there are dots over the "u" in the guy's passport, and would certainly not accept that the correct way to spell this German name on a keyboard without Umlaut is "Mueller" and not "Muller". Actually I hate myself for writing "Groebner" instead of "Gröbner" in Sage doc strings (but at least I don't write "Grobner").

Yeah. In Sage we respect freedom and everything, but accents are off limits :-P

Of course, errors can occur, specifically when writing text in a foreign language, and an extra space certainly is not a big drama

And when we will be done with the spaces before ":" the hunt for american vs english spellings will begin :-P

(I am not calling you an imperialist : :-P).

Good. Cause I just washed my hair and I have a towel on my head right now. And you can't seriously call "imperialist" somebody who has a (pink) towel on his head. Really, you can't. It would sound ridiculous.

Since the above mentioned doc string is from static_sparse_graph.pyx and thus from a file that your commits don't touch, I'd say one shouldn't try to fix it here.

Ahahahah. Okay, as you prefer !

Nathann

[simon-king-jena]

comment:9

Replying to @nathanncohen:

And when we will be done with the spaces before ":" the hunt for american vs english spellings will begin :-P

Indeed. I much prefer "neighbours" over "neighbors" and "centre" over "center"...

Good. Cause I just washed my hair and I have a towel on my head right now. And you can't seriously call "imperialist" somebody who has a (pink) towel on his head. Really, you can't. It would sound ridiculous.

:-D

[simon-king-jena]

Reviewer: Simon King

[simon-king-jena]

comment:10

The added tests show that the bug is fixed. The added comment clarifies a few things. All tests pass. And there will be "space" (or rather : "space removal") for anti-imperialism on different tickets.

[nathanncohen]

comment:11

Thaaaaaaaaaaaaaaaanks !!

Nathann