Representation of self-loops and the calculation of degrees
0
0
Entering edit mode
Szabolcs • 0
@9ce1e6a8
Last seen 10 months ago
Germany

I am writing to ask whether the graphNEL class of the graph package supports self-loops. If yes, how should self-loops in undirected graphs be represented? Should they appear once or twice in the adjacency list?

As an example, consider the following way to construct a graph:

gn <- graphNEL(nodes=c('A','B'), edgeL=list(A=c('A','B'), B=c('A')), edgemode='undirected')

The undirected graph I intend to represent is the following:

enter image description here

I.e., there are two connected vertices, and one of them has a single-self loop.

B has degree 1 and A has degree 3. However, the degree function indicates a degree of 2 for A:

> degree(gn)
A B 
2 1

Is this intentional or is it a bug? If intentional, this would be a highly unusual definition for the idea of "degree" that does not possess many of the usual properties of the more commonly known degree concept. For example, the degrees no longer sum up to twice the number of edges. Such a definition is not invalid, but it is unusual enough that it should be pointed out explicitly in the documentation.

Or is it perhaps the case that self-loops are supposed to be included twice in the adjacency list when creating undirected graphs?

gn <- graphNEL(nodes=c('A','B'), edgeL=list(A=c('A', 'A', 'B'), B=c('A')), edgemode='undirected')

It would be great if these issues could be clarified in the documentation.

This issue came up while investigating a bug report for igraph's as_graphnel() function: https://github.com/igraph/rigraph/issues/575

graph • 1.1k views
ADD COMMENT
0
Entering edit mode

Thanks for this. I think the package and this condition should be made consistent with igraph. Can you provide a PR?

ADD REPLY
0
Entering edit mode

This is not a minor bug that can be fixed with a brief PR. It's a major design issue that should be decided by the package's authors, and which will impact just about every piece of functionality in the package.

ADD REPLY
0
Entering edit mode
> packageVersion("graph")
[1] '1.79.2'
> gn <- graphNEL(nodes=c('A','B'), edgeL=list(A=c('A','B'), B=c('A')), edgemode='undirected')
> degree(gn)
A B 
3 1 

At present there is only limited testing for graphs with self-loops. With the modifications to the degree method, all tests in the package are passing. If you have additional examples of misbehavior please let us know. Thanks.

ADD REPLY

Login before adding your answer.

Traffic: 585 users visited in the last hour
Help About
FAQ
Access RSS
API
Stats

Use of this site constitutes acceptance of our User Agreement and Privacy Policy.

Powered by the version 2.3.6