3

suppose I have given an igraph graph in R and want to invert all edges:

Transpose_graph

see Transpose graph

library(igraph)
library(tidyverse)
g <- make_star(n=6)
plot(g)
gt <- transposeGraph(g) # hypothetical function
plot(gt)

One way seems to be to rebuild the graph, but I am concerned about the performance and the loss of vertex attributes:

gt <- graph_from_data_frame(as_data_frame(g) %>% select(to, from))

Any other ideas?

c0bra
  • 1,031
  • 5
  • 22

4 Answers4

2

A possible answer can be found here, however it doesn't keep the vertices attributes.
It should be possible to restore attributes using get.vertex.attribute and set.vertex.attribute

Try:

library(igraph)
library(tidyverse)

g <- make_star(n=6)
plot(g)


transposeGraph <- function(g) {
  g %>% get.edgelist %>%
    {cbind(.[, 2], .[, 1])} %>%
    graph.edgelist
}

gt <- transposeGraph(g)
plot(gt)

Created on 2020-09-10 by the reprex package (v0.3.0)

Performance comparison shows that it's about 10x faster on a 100 vertices star:

Unit: microseconds
                                                         expr      min        lq     mean   median
 graph_from_data_frame(as_data_frame(g) %>% select(to, from)) 4300.308 4495.1795 4844.328 4654.769
                                            transposeGraph(g)  315.487  350.5645  457.711  404.308
       uq       max neval cld
 4806.770 13324.719   100   b
  437.539  4488.205   100  a
Waldi
  • 39,242
  • 6
  • 30
  • 78
  • Can you explain, why you think this would have a better performance? – c0bra Sep 10 '20 at 21:26
  • I'm not sure this has a better performance but it seems difficult to make leaner. Best way to know is to create a bigger random graph and to test both solutions with `microbenchmark::microbenchmark(transposeGraph_dataframe_solution(g),transposeGraph_igraph_solution(g))`. – Waldi Sep 10 '20 at 21:31
  • A related answer : https://stackoverflow.com/a/63016581/13513328 – Waldi Sep 10 '20 at 21:48
  • @c0bra, did you have the opportunity to make a performance comparison on your dataset? – Waldi Sep 11 '20 at 21:09
1

With R/igraph 1.3.3 or later, you can use the reverse_edges() function. This function preserves all attributes, and alows allows for reversing only some edges.

An alias for reversing all edges is t() (for "transpose").

Szabolcs
  • 24,728
  • 9
  • 85
  • 174
0

Solution discussed here are failing if the graph contains isolates.

library(igraph)
tGraph <- function(g)
          { g %>% get.edgelist %>% {cbind(.[, 2], .[, 1])} %>% graph.edgelist}
g <- make_graph(c(1,2,4,5)) + 1
gt <- tGraph(g)
gtt <- tGraph(gt)

isomorphic(g, gtt)
[1] FALSE
identical_graphs(g, gtt)
[1] FALSE

The code below preserves isolates and graph attributes.

t.graph <- function(g){
tg <- add_edges(delete_edges(g, edges=E(g))
     , t(get.edgelist(g, names=FALSE)[,2:1])) # revert edges
edge_attr(tg) <- edge_attr(g)                 # save edge attributes                                               
return(tg)
}

g <- make_graph(c(1,2,4,5)) + 1
gtt <- t.graph(t.graph(g))

isomorphic(g, gtt)
[1] TRUE
identical_graphs(g, gtt)
[1] TRUE

Note that unlike graph_from_edgelist, add_edges needs a vertex sequence which is a transposed edgelist.

clp
  • 1,098
  • 5
  • 11
-2

I am currently running the following code as it preserves all node and edge attributes.


library(igraph)
#> 
#> Attache Paket: 'igraph'
#> The following objects are masked from 'package:stats':
#> 
#>     decompose, spectrum
#> The following object is masked from 'package:base':
#> 
#>     union

g <- make_star(n=6)
V(g)$name <- LETTERS[1:6]
E(g)$weight <- 1:5
plot(g)



transposeGraph <- function(g){
  gDf <- as_data_frame(g, what = "both")
  graph_from_data_frame(gDf$edges[,c(2:1, 3:ncol(gDf$edges))], directed = T, gDf$vertices)
}

gt <- transposeGraph(g)

plot(gt)

Created on 2020-09-28 by the reprex package (v0.3.0)

c0bra
  • 1,031
  • 5
  • 22