Opened 5 years ago

Closed 5 years ago

#17225 closed defect (fixed)

Degrees of looped *immutable* graphs are wrong

Reported by: kcrisman Owned by:
Priority: major Milestone: sage-6.4
Component: graph theory Keywords:
Cc: Merged in:
Authors: Nathann Cohen Reviewers: Karl-Dieter 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 follow-up: Changed 5 years ago by ncohen

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

comment:2 Changed 5 years ago by ncohen

  • Authors set to Nathann Cohen
  • 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 5 years ago by git

  • Commit set to 2810414d7f8c74ef2a71e4ac1b4a3809f18938db

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

2810414trac #17225: Degrees of looped *immutable* graphs are wrong

comment:4 Changed 5 years ago by git

  • Commit changed from 2810414d7f8c74ef2a71e4ac1b4a3809f18938db to 58cf24722664d1b299ab4de934455579125e3326

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

58cf247trac #17225: Degrees of looped *immutable* graphs are wrong

comment:5 in reply to: ↑ 1 ; follow-ups: Changed 5 years ago by kcrisman

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 ; follow-up: Changed 5 years ago by ncohen

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 ; follow-up: Changed 5 years ago by kcrisman

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 5 years ago by ncohen

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 low-level 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 low-level 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 5 years ago by kcrisman

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 5 years ago by ncohen

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 5 years ago by kcrisman

For some reason this isn't merging properly. And I was going to look at it this afternoon, too...

comment:12 Changed 5 years ago by ncohen

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 5 years ago by git

  • Commit changed from 58cf24722664d1b299ab4de934455579125e3326 to 47eb00bef23182e301612f6f7f387ee0b44714b9

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

47eb00btrac #17225: Merged with 6.4.rc1

comment:14 Changed 5 years ago by kcrisman

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 5 years ago by kcrisman

  • Reviewers set to Karl-Dieter Crisman
  • Status changed from needs_review to positive_review

comment:16 Changed 5 years ago by ncohen

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 follow-up: Changed 5 years ago by kcrisman

  • 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 5 years ago by kcrisman

  • Branch changed from u/ncohen/17225 to u/kcrisman/17225
  • Commit changed from 47eb00bef23182e301612f6f7f387ee0b44714b9 to 4ab489733862b2d251b65ffaa864b57d3a49a528
  • Status changed from needs_work to positive_review

New commits:

e5aef5cMerge branch 'u/ncohen/17225' of trac.sagemath.org:sage into loops
4ab4897Minor reviewer patch

comment:19 in reply to: ↑ 17 Changed 5 years ago by ncohen

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 follow-up: Changed 5 years ago by ncohen

Actually I was wrong. Looks like #17340 has lready bee fixed in the latest release. Must be one of the 1000 one-line fixes I made about the same problem.

Nathann

comment:21 in reply to: ↑ 20 Changed 5 years ago by kcrisman

Actually I was wrong. Looks like #17340 has lready bee fixed in the latest release. Must be one of the 1000 one-line fixes I made about the same problem.

No, it was a typo in the description, my bad.

comment:22 Changed 5 years ago by vbraun

  • Branch changed from u/kcrisman/17225 to 4ab489733862b2d251b65ffaa864b57d3a49a528
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.