Create tranpose (edge reversed) of graph?

Usage
1

Hi, I’m using python igraph to write an algorithm (exact algorithm not relevant), and part of it calls for reversing the direction of all edges in a directed graph.

I can’t see a simple way to do this. I would guess that it’s not an uncommon thing people might want to do, so perhaps there is a simple way of doing it which I have just missed. I’ve searched the documentation and the forum for “transpose”, “reverse edges” and just “reverse”, but nothing seems relevant.

At the moment, I’m getting the weighted adjacency matrix, transposing it, and creating a new graph from said transpose, and copying over all the vertex attributes. Since weight is the only edge attribute I’m dealing with, this works fine, but I suspect there’s a more efficient and neater way of doing it.

Does anyone know if there’s a simple built-in function for doing it, or alternatively a more efficient way of doing it without a self-contained function?

Cheers
Michal

2

At the moment, no.

The reason is that (almost?) any operation that takes edge directions into account has a mode parameter that can be set to either OUT or IN, with IN indicating that the graph should be interpreted in the reverse direction.

If you feel that you still need this feature, please do comment on this feature request and explain why using the mode parameter is insufficient or inconvenient for you. Input from users will be helpful in arriving to a decision about whether (and how) to implement this.

3

Using the adjacency matrix uses a full matrix representation, unless you specifically use get​_adjacency​_sparse. Using the sparse representation will obviously be more efficient. Alternatively, you could also use the edge list directly, as follows

el = G.get_edgelist()
el_t = (tuple(reversed(e)) for e in el)
G_t = ig.Graph(el_t, directed=True)
4

These methods do not preserve the attributes though. I think there is great value in introducing an efficient function that reverses edge directions.

5

You are constructing a completely new graph in this way. So, there simply aren’t attributes (yet). But, the edge order is identical, so you can easily copy them over: e.g G_t.es['weight'] = G.es['weight'].

Regardless, it would be convenient if this was directly implemented.

6

But, the edge order is identical, so you can easily copy them over.

Not necessarily if the graph contains isolates as I found out (see Crash in rigraph function permute() · Issue #542 · igraph/rigraph · GitHub )

The following code seems to work in R:

# transpose directed graph, including isolates
# keep edge attributes
t.graph <- function(g){
tg <- add_edges(delete_edges(g, edges=E(g))   # delete edges from original graph and
     , t(get.edgelist(g, names=FALSE)[,2:1])) # revert edges and transpose edgelist
edge_attr(tg) <- edge_attr(g)                 # save edge attributes
return(tg)
}
7

Transpose graph in Magritte style.

library(igraph)
# magritte style
# transpose directed graph, keep isolates and edge attributes
t.graph <- function(g){
  g %>% delete_edges(E(.)) %>%
  add_edges(g %>% get.edgelist(names=FALSE) %>% .[,2:1] %>% t ) -> tg
  edge_attr(g) -> edge_attr(tg) 
  tg %>% return
}

#  check if double transpose is an identical function
g <- make_graph(c(1,2,4,5)) + 1
gtt <- t.graph(t.graph(g))
isomorphic(g, gtt)
identical_graphs(g, gtt)
8

Note that unlike graph_from_edgelist, add_edges needs a transposed edgelist. Not very relevant for Python.

9

R/igraph 1.3.3 will include the reverse_edges() function when it’s released:

> g <- make_graph(~ a-+b, b+-c)
> g
IGRAPH 2472e57 DN-- 3 2 -- 
+ attr: name (v/c)
+ edges from 2472e57 (vertex names):
[1] a->b c->b
> reverse_edges(g)
IGRAPH 523cafd DN-- 3 2 -- 
+ attr: name (v/c)
+ edges from 523cafd (vertex names):
[1] b->a b->c
> reverse_edges(g, 1) # reverse only the 1st edge
IGRAPH d41e8b1 DN-- 3 2 -- 
+ attr: name (v/c)
+ edges from d41e8b1 (vertex names):
[1] b->a c->b

So will python-igraph 0.9.12.