R Interface: slow creation of weighted graphs from adjacency matrices

[gaborcsardi]

Setup:
The C library has functions for creation of weighted and unweighted graphs from dense adjacency matrices.

Problem:
The R function "graph.adjacency.dense" in structure.generators.R does not use the much faster C version when provided a weighted graph, instead using a very slow double loop in R. (an unweighted graph is created very quickly)

In addition, in rinterface.c, while igraph_adjacency() is exported to R, the igraph_weighted_adjacency(...) function is not exported to R.

Supporting data point:average timings
On my machine, for a complete graph of 900 vertices:
Unweighted graph: ~ 0.9 seconds
Weighted graph: ~ 23.9 seconds
With fix # 2 below: ~ 1.4 seconds

Proposed fixes:

1. modify rinterface.c to export the weighted adjacency function, then modify graph.adjacency.dense to use that function. Both cases are a matter of copying and slightly modifying what already exists for unweighted graphs.
2. change the graph.adjacency.dense R function to use vector operations instead of a loop. I wrote some code to do this at the cost of changing the edge order.
   ######################
   edges <- as.vector(t(matrix(c((which(adjmatrix != 0) - 1) %% nrow(adjmatrix) + 1,(which(adjmatrix != 0) - 1) %/%nrow(adjmatrix) + 1),ncol = 2)) - 1)
   weight <- as.vector(adjmatrix[adjmatrix!=0])
   ######################

Fix # 1 is preferred, and I'd submit a patch, but I don't have an appropriate compilation environment now. I am using # 2 instead, for now.

Richard Bowman
Doctoral Fellow
Pardee RAND Graduate School

---

Imported from Launchpad using lp2gh.

• date created: 2010-05-20T17:02:52Z
• owner: richie-bowman
• assignee: gabor.csardi
• the launchpad url was https://bugs.launchpad.net/bugs/583433

[gaborcsardi]

(by gabor.csardi)
Richard,

thanks for the excellent bug report, I'll fix this asap.

[gaborcsardi]

(by gabor.csardi)
OK, this was fixed in revision 1946 (0.6-main branch). We call back to C now.

[gaborcsardi]

(by richie-bowman)
Thank you for the quick fix!

On Tue, May 25, 2010 at 5:32 AM, Gábor Csárdi wrote:

OK, this was fixed in revision 1946 (0.6-main branch). We call back to C
now.

** Changed in: igraph
      Status: Confirmed => Fix Released

R Interface: slow creation of weighted graphs from adjacency matrices
https://bugs.launchpad.net/bugs/583433
You received this bug notification because you are a direct subscriber
of the bug.

Status in The igraph library: Fix Released

Bug description:
Setup:
The C library has functions for creation of weighted and unweighted graphs from dense adjacency matrices.

Problem:
The R function "graph.adjacency.dense" in structure.generators.R does not use the much faster C version when provided a weighted graph, instead using a very slow double loop in R. (an unweighted graph is created very quickly)

In addition, in rinterface.c, while igraph_adjacency() is exported to R, the igraph_weighted_adjacency(...) function is not exported to R.

Supporting data point:average timings
On my machine, for a complete graph of 900 vertices:
Unweighted graph: ~ 0.9 seconds
Weighted graph: ~ 23.9 seconds
With fix # 2 below: ~ 1.4 seconds

Proposed fixes:

1. modify rinterface.c to export the weighted adjacency function, then modify graph.adjacency.dense to use that function. Both cases are a matter of copying and slightly modifying what already exists for unweighted graphs.
2. change the graph.adjacency.dense R function to use vector operations instead of a loop. I wrote some code to do this at the cost of changing the edge order.
   ######################
        edges <- as.vector(t(matrix(c((which(adjmatrix != 0) - 1) %% nrow(adjmatrix) + 1,(which(adjmatrix != 0) - 1) %/%nrow(adjmatrix) + 1),ncol = 2)) - 1)
        weight <- as.vector(adjmatrix[adjmatrix!=0])
   ######################

Fix # 1 is preferred, and I'd submit a patch, but I don't have an appropriate compilation environment now. I am using # 2 instead, for now.

Richard Bowman
Doctoral Fellow
Pardee RAND Graduate School

To unsubscribe from this bug, go to:
https://bugs.launchpad.net/igraph/+bug/583433/+subscribe