#15491 closed defect (fixed)

directed immutable graphs report twice too many edges

Reported by: ncohen Owned by:
Priority: major Milestone: sage-6.1
Component: graph theory Keywords:
Cc: SimonKing Merged in:
Authors: Nathann Cohen Reviewers: Simon King
Report Upstream: N/A Work issues:
Branch: u/ncohen/15491 (Commits) Commit: 020cc82f8f9ba8bc8295ac1e79c396a12a4a5fd8
Dependencies: Stopgaps:

Description

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

Change History (14)

comment:1 Changed 10 months ago by ncohen

  • Branch set to u/ncohen/15491
  • Status changed from new to needs_review

comment:2 Changed 10 months ago by git

  • Commit set to cd9792698e90de72e0980a315a7e76db6e38d676

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

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

comment:3 follow-up: Changed 10 months ago by SimonKing

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.

comment:4 Changed 10 months ago by SimonKing

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.

comment:5 in reply to: ↑ 3 ; follow-up: Changed 10 months ago by ncohen

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

comment:6 Changed 10 months ago by git

  • Commit changed from cd9792698e90de72e0980a315a7e76db6e38d676 to 020cc82f8f9ba8bc8295ac1e79c396a12a4a5fd8

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

020cc82trac #15491: addressing the reviewer's comments

comment:7 in reply to: ↑ 5 ; follow-up: Changed 10 months ago by SimonKing

Replying to ncohen:

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.

comment:8 in reply to: ↑ 7 ; follow-up: Changed 10 months ago by ncohen

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

comment:9 in reply to: ↑ 8 Changed 10 months ago by SimonKing

Replying to ncohen:

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

comment:10 Changed 10 months ago by SimonKing

  • Reviewers set to Simon King
  • Status changed from needs_review to positive_review

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.

Last edited 10 months ago by SimonKing (previous) (diff)

comment:11 Changed 10 months ago by ncohen

Thaaaaaaaaaaaaaaaanks !!

Nathann

comment:12 Changed 10 months ago by jdemeyer

  • Milestone changed from sage-5.13 to sage-6.0

comment:13 Changed 10 months ago by vbraun_spam

  • Milestone changed from sage-6.0 to sage-6.1

comment:14 Changed 10 months ago by vbraun

  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.