Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Representation of self-loops and the calculation of degrees #17

Open
szhorvat opened this issue Mar 10, 2023 · 7 comments
Open

Representation of self-loops and the calculation of degrees #17

szhorvat opened this issue Mar 10, 2023 · 7 comments

Comments

@szhorvat
Copy link

This is a verbatim copy of the post I wrote here.


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:

image

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: igraph/rigraph#575

@vjcitn
Copy link
Contributor

vjcitn commented Sep 22, 2023

We are working on this.

@vjcitn
Copy link
Contributor

vjcitn commented Sep 22, 2023

commit a99b4f6 to devel branch of https://git.bioconductor.org/packages/graph corrects the computation of degree for graphNEL with self-loops. This is version 1.79.2 of graph package. Unit tests are added, documentation not modified yet.

@rcastelo
Copy link

rcastelo commented Oct 9, 2023

Dear @vjcitn this commit seems to be the responsible for breaking qpgraph. A minimal reproducible example of the problem is the following:

library(graph)

g <- graphBAM(data.frame(from=letters[1:10], to=letters[2:11], weight=rep(1, 10)))
degree(g, letters[1:2])
a b c d e f g h i j k 
1 2 1 2 1 2 1 2 1 2 1 
Warning message:
In deg + nself :
  longer object length is not a multiple of shorter object length

Note two things here, one is that degree(g, letters[1:2]) should be returning the degree of two nodes only and the warning message about recyling a shorter object on a longer one whose length is not multiple of the shorter object length.

I've tracked down the problem to the 216-218 lines of code in the file R/methods-graph.R:

           nself = sapply(1:length(nl),
             function(i) sum(names(nl)[i] == nl[[i]]))
           names(nself) = names(nl)
           return(deg + nself)

where the sapply() is calculating the additional degree from self-loops and adding them to the non-self-loops degrees calculated before and stored in deg. Here this calculation should be done only for the nodes in the variable Nodes, and not for all them. This is the reason why deg + nself gives the recyling warning, since deg has only values for the nodes in Nodes, while nself has values for all of the nodes. A solution would be to replace the previous code snippet by:

           nself <- sapply(Nodes, function(n) sum(n == nl[[n]]))
           return(deg + nself)

I have checked in my computer that with this update, the graph package still builds and checks cleanly and qpgraph does not break. Note that any package using graph::degree(g, n) with n different from nodes(g) may potentially also break due to this problem.

@vjcitn
Copy link
Contributor

vjcitn commented Oct 9, 2023

Thanks Robert. I will commit your fix shortly. Can you suggest a unit test possibly conditionally involving qpgraph that I could include?

@vjcitn
Copy link
Contributor

vjcitn commented Oct 9, 2023

Please try with commit 2f5f89a

@rcastelo
Copy link

rcastelo commented Oct 9, 2023

Thanks for porting the fix quickly, I've tried out and works as expected, qpgraph doesn't break anymore. I'll be happy to suggest a unit test involving qpgraph, but probably the best way to do it would be through a PR and at the moment your fix is only available at the Bioc Git server (git.bioconductor.org). Once you synchronize the Bioc Git server repo with the GitHub repo, I'll do the PR.

@vjcitn
Copy link
Contributor

vjcitn commented Oct 9, 2023

It has been synchronized. Thanks.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants