degree of loops

[etiennedeg]

I must feel stupid, but on every reference I encounter, a self-loop (undirected) counts for 2 in the degree of a node. This is the behavior on NetworkX (and I think on lots of other graph libraries).

Graphs.jl count only one for self-loops. Is it a decision that was thought of and if so, what was the rationale ?
The pros of counting one is that generally, we want to traverse a loop only once during a graph traversal, so the degree corresponds to the number of edges that can be visited from a node.
The pros of counting 2 is that it matches the literature and the other graph libraries. It keeps true the fact that the sum of degrees is even.

One way of looking at the Graphs.jl behavior could be to say that self-loops are always directed (even for undirected graphs).
Should we classify this as a bug ? Should we have somewhere (in the 2.0 API ?) a clear distinction between directed and undirected self-loops (and say that SimpleGraphs have directed loops, but other graphs type can implement if they want undirected self-loops) ? Should we introduce a distinct degree function with the second behavior ?

[simonschoelly]

I feel like I have seen this question before, but maybe it was about something else.

I am not sure if this is a bug, or a deliberate choice to just return the length of the adjacency list - as this is computationally very efficient. It also matches what the documentation states, namely

for undirected graphs, it equals the connected edges.

But as probably every textbook defines this differently we should probably change this eventually.

I would propose, that we would add the following functions

num_neighbors(g, v)  # return the number of connected neighbors (inclusive itself in case of a self-loop

num_edges(g, v)  # number of connected edges

Maybe of the difficult to wrote num_neighbors we could also write num_vertices(g, v) - not sure about that though. num_edges might also be helpful, if we ever implement multigraphs.

Of course we also would then create the directed versions of these functions for directed graphs. Btw, I am not sure, how much degree makes sense for directed graphs - it is the indegree plus the outdegree, so

julia> gd = SimpleDiGraph([Edge(1, 1)]);
julia> degree(gd, 1)
2

so in this case this seems correct.

I am not completely sure how we should proceed about degree - maybe it would make sense to deprecate the degree functions for a while altogether, and then later reintroduce them with a changed behavior?