Invert edges in a directed graph (transpose graph) in igraph (R packages)

Viewed 602

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?

4 Answers

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 

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").

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.

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)

Related