Opened 6 years ago
Closed 6 years ago
#17225 closed defect (fixed)
Degrees of looped *immutable* graphs are wrong
Reported by:  kcrisman  Owned by:  

Priority:  major  Milestone:  sage6.4 
Component:  graph theory  Keywords:  
Cc:  Merged in:  
Authors:  Nathann Cohen  Reviewers:  KarlDieter Crisman 
Report Upstream:  N/A  Work issues:  
Branch:  4ab4897 (Commits)  Commit:  4ab489733862b2d251b65ffaa864b57d3a49a528 
Dependencies:  Stopgaps: 
Description
See this SO question.
q=graphs.CompleteGraph(2) q.allow_loops(True) q.allow_multiple_edges(True) q.add_edge([1,1]) a=q.copy(immutable=True) b=q.copy(immutable=False) sage: a==b True sage: a.degree() [1, 2] sage: b.degree() [1, 3]
Basically, the problem is that the usual backend has a case for this
if self._loops and self.has_edge(v, v, None): if self._multiple_edges: d += len(self.get_edge_label(v, v)) else: d += 1
but the "static" one doesn't.
Change History (22)
comment:1 followup: ↓ 5 Changed 6 years ago by
comment:2 Changed 6 years ago by
 Branch set to u/ncohen/17225
 Status changed from new to needs_review
Not sure that I ever mentionned it, but I hate loops, I hate labels and I hate multiple edges.
Nathann
comment:3 Changed 6 years ago by
 Commit set to 2810414d7f8c74ef2a71e4ac1b4a3809f18938db
Branch pushed to git repo; I updated commit sha1. New commits:
2810414  trac #17225: Degrees of looped *immutable* graphs are wrong

comment:4 Changed 6 years ago by
 Commit changed from 2810414d7f8c74ef2a71e4ac1b4a3809f18938db to 58cf24722664d1b299ab4de934455579125e3326
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
58cf247  trac #17225: Degrees of looped *immutable* graphs are wrong

comment:5 in reply to: ↑ 1 ; followups: ↓ 6 ↓ 9 Changed 6 years ago by
HMmmmmm... Well, the thing is that it depends on what you want the degree to be. If you want the degree of a vertex to be equal to the number of edges incident to it, then it is correct.
If you want the number of edges to be twice the sum of degrees, then it is wrong.
I mostly want immutable and mutable graphs to have the same behavior.
comment:6 in reply to: ↑ 5 ; followup: ↓ 7 Changed 6 years ago by
I mostly want immutable and mutable graphs to have the same behavior.
Yesyes I understand. Well, I was rather happy to find a way to fix that without changing the internal data structure. I really did not want to add an "if" there, in a function that was just a substraction :)
The only difference will be at Python level, so it does not matter much.
Nathann
comment:7 in reply to: ↑ 6 ; followup: ↓ 8 Changed 6 years ago by
Yesyes I understand. Well, I was rather happy to find a way to fix that without changing the internal data structure. I really did not want to add an "if" there, in a function that was just a substraction
:)
The only difference will be at Python level, so it does not matter much.
Hmm, I see what you mean though, keeping track of all this extra data could be expensive when people are searching through really large sets of relatively large graphs (which is when this was implemented in the first place). I wonder if that will impact efficiency or speed.
comment:8 in reply to: ↑ 7 Changed 6 years ago by
Hello !
Hmm, I see what you mean though, keeping track of all this extra data could be expensive when people are searching through really large sets of relatively large graphs (which is when this was implemented in the first place). I wonder if that will impact efficiency or speed.
You should not worry too much about that. Performance is wasted in other places, so this probably will not become a problem anytime soon.
The additional caching is only an array of ints of size n (no Python involved, just real integers). You waste MUCH more ressources if your graph carries a layout for its vertices, for instance ! :)
Besides, it is indeed good that static graphs are MUCH lighter in memory than Sage's usual graphs, but it is not why they were implemented: the lowlevel data structure was implemented mostly for speed, because at this level you can work on the graph directly without calling any function, everything is as fast as it should be. They were later turned into an immutable Python object because the algebraists wanted graphs as dictionary keys.
The "main" problem though, is that immutable graphs are immutable, and consequently you can only build an immutable graph from a mutable graph (and the mutable graph is MUCH heavier in memory).
This, to say that this caching is not really a problem. What I wanted to avoid was to add a useless "if" in the 'degree' function of the lowlevel data structure. Fortunately, there is no such function for those graphs are implemented to actually be ... digraphs ! And there we only have an out_degree
method, which is perfectly defined and only returns a difference of pointers. In particular, no ugly 'if' there :P
Nathann
comment:9 in reply to: ↑ 5 Changed 6 years ago by
HMmmmmm... Well, the thing is that it depends on what you want the degree to be. If you want the degree of a vertex to be equal to the number of edges incident to it, then it is correct.
If you want the number of edges to be twice the sum of degrees, then it is wrong.
See here and here, which claim that this is a standard convention. I don't recall ever hearing a different convention for loops either, and for directed situations we should still be correct, right? Let me know if I'm missing a controversy on this  sometimes there are mutually incompatible definitions, most notoriously in my own classes for $\mathbb{N}$.
comment:10 Changed 6 years ago by
Hello !
I assume that what this patch implements is the convention, as it is also what is contained in Wikipedia and books. I just hate conventions that cost running time and make dirty code.
Also, I am old enough to understand that people make the conventions that are the easiest for them, so I don't like to pay the price of other person's conventions.
But well, this one was cheap in terms of running time, so let's not complain :P
Nathann
comment:11 Changed 6 years ago by
For some reason this isn't merging properly. And I was going to look at it this afternoon, too...
comment:12 Changed 6 years ago by
Hello !
That was because the line that imports bitsets changed in #17196. Now, 'for simplicity reasons', we have data structures in structures/, data_structures/ and misc/.
Rebased !
Nathann
comment:13 Changed 6 years ago by
 Commit changed from 58cf24722664d1b299ab4de934455579125e3326 to 47eb00bef23182e301612f6f7f387ee0b44714b9
Branch pushed to git repo; I updated commit sha1. New commits:
47eb00b  trac #17225: Merged with 6.4.rc1

comment:14 Changed 6 years ago by
Should
+ cdef int i, tmp
be
+ cdef int i, j, tmp
or is that not helpful?
Otherwise this seems good and behaves correctly.
However, I found #17340 while reviewing this... sigh.
comment:15 Changed 6 years ago by
 Reviewers set to KarlDieter Crisman
 Status changed from needs_review to positive_review
comment:16 Changed 6 years ago by
Hello !
Right right, this 'j' should appear too.
Could you add a commit, or fix it in #17340 ? I am backpacking in Mumbai right now :)
Nathann
comment:17 followup: ↓ 19 Changed 6 years ago by
 Status changed from positive_review to needs_work
I don't know how to fix #17340, so I can't do that. I can try to add this here, though.
Are you visiting Tata? Lucky you!
comment:18 Changed 6 years ago by
 Branch changed from u/ncohen/17225 to u/kcrisman/17225
 Commit changed from 47eb00bef23182e301612f6f7f387ee0b44714b9 to 4ab489733862b2d251b65ffaa864b57d3a49a528
 Status changed from needs_work to positive_review
comment:19 in reply to: ↑ 17 Changed 6 years ago by
Yo !
I don't know how to fix #17340, so I can't do that.
Come ooooooon. I am sure it takes something like one line to fix.
I can try to add this here, though.
Thanks !
Are you visiting Tata? Lucky you!
I visited some Tata museum, but that's all :P
Nathann
comment:20 followup: ↓ 21 Changed 6 years ago by
Actually I was wrong. Looks like #17340 has lready bee fixed in the latest release. Must be one of the 1000 oneline fixes I made about the same problem.
Nathann
comment:21 in reply to: ↑ 20 Changed 6 years ago by
Actually I was wrong. Looks like #17340 has lready bee fixed in the latest release. Must be one of the 1000 oneline fixes I made about the same problem.
No, it was a typo in the description, my bad.
comment:22 Changed 6 years ago by
 Branch changed from u/kcrisman/17225 to 4ab489733862b2d251b65ffaa864b57d3a49a528
 Resolution set to fixed
 Status changed from positive_review to closed
HMmmmmm... Well, the thing is that it depends on what you want the degree to be. If you want the degree of a vertex to be equal to the number of edges incident to it, then it is correct.
If you want the number of edges to be twice the sum of degrees, then it is wrong.
Nathann