R: performance of getting adjacent edges

[Artem Tarasov]

R bindings are unusable on large graphs.
Getting edges adjacent to a given vertex should be O(#adj. edges) operation.

e.g.:
g <- graph.lattice (c(1000, 1000))
E(g)[adj(0)]

As far as I see from reading rinterface.c, this operation uses a logical vector of length |E|, and that takes inappropriate amount of time. Shouldn't something like hashset be used instead?

[Gábor Csárdi (gabor.csardi)]

Indeed, the E() and V() functions are bad for large graphs. You can use the incident() (from 0.6) and neighbors() (and other) igraph functions, those are way faster:
> system.time(incident(g, 1))
   user system elapsed
  0.000 0.000 0.001
> system.time(E(g)[adj(1)])
   user system elapsed
  0.441 0.261 0.897

I agree, though, that this should be at least documented.

[Artem Tarasov (lomereiter)]

Thanks, it's a bit better. Although, 'incident' function can be made faster for undirected graphs by not parsing 'mode' parameter. At least for me, enclosing this piece of code with if (is.directed(graph)) { ... } sped up my program by about 1/3.

[Gábor Csárdi (gabor.csardi)]

OK, I have added this modification. Btw. if you call incident() many times on the same graph, maybe it is better to create an edge-adjacency list via get.adjedgelist().

[Gábor Csárdi (gabor.csardi)]

Comment to myself: document that E() (or V()) & logical indexing is slow, and that adj() uses logical indexing.

[Gábor Csárdi (gabor.csardi)]

OK, this is now documented in #2711 (0.6-main).

[Gábor Csárdi (gabor.csardi)]

The development of igraph has moved to github, so please do not comment on this bug here. You are of course welcome to comment on github, here:
https://github.com/igraph/igraph/issues/100