Opened 9 years ago
Closed 9 years ago
#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, GitHub, GitLab) | 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 9 years ago by
- Branch set to u/ncohen/15491
- Status changed from new to needs_review
comment:2 Changed 9 years ago by
- Commit set to cd9792698e90de72e0980a315a7e76db6e38d676
comment:3 follow-up: ↓ 5 Changed 9 years ago by
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? Instatic_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 thatneighbors[n]
gives three times the number of edges minus the number of loops (so thatcg.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 vertexn-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 9 years ago by
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: ↓ 7 Changed 9 years ago by
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
bybla: 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 9 years ago by
- Commit changed from cd9792698e90de72e0980a315a7e76db6e38d676 to 020cc82f8f9ba8bc8295ac1e79c396a12a4a5fd8
comment:7 in reply to: ↑ 5 ; follow-up: ↓ 8 Changed 9 years ago by
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 theedges
array.cg.g.edges
is actually equal tocg.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: ↓ 9 Changed 9 years ago by
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 9 years ago by
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 9 years ago by
- 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.
comment:11 Changed 9 years ago by
Thaaaaaaaaaaaaaaaanks !!
Nathann
comment:12 Changed 9 years ago by
- Milestone changed from sage-5.13 to sage-6.0
comment:13 Changed 9 years ago by
- Milestone changed from sage-6.0 to sage-6.1
comment:14 Changed 9 years ago by
- Resolution set to fixed
- Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits: