JuliaGraphs / JuliaGraphs/Graphs.jl

degree of loops

Open
#303 1 comment 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

bug question
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

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.