JuliaGraphs / JuliaGraphs/Graphs.jl
degree of loops
Nobody has claimed this yet.
- Dominant language
- Julia
- Stars
- 538
- Forks
- 128
- Avg merge
- 10h 25m
- Merged PRs (30d)
- 2
Description
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 ?
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
The issue does not name files or tests. Start by locating the degree API and existing self-loop handling, then review how undirected and directed loops are represented. Done means the loop-degree semantics are decided, consistently implemented or exposed through the API, and clearly documented with coverage for the relevant cases.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- julia
- Domain
- data
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100