Reverse the direction of edges and transpose

Development
1

Regarding issue: Wishlist: Reverse the direction of edges while preserving attributes · Issue #1477 · igraph/igraph · GitHub @ Github.

Reversing the direction of edges is basically a transpose of a directed graph.

Transpose is an elementary and important concept applicable to matrices and graphs.
Therefore it would be nice to be compatible with objects like vector, list, matrix and sparse matrix.

In addition to a new function igraph_reverse_edges() , let t(g) be the transpose of graph g.

It’s “syntactic suger” but nice to have.

library(igraph)
library(Matrix)
g <- make_star(7); g 

v  <- c(1,2,3,4,5,6,7,8); t(v)
m  <- matrix(v, 4,2); t(m)
p  <- g[]; t(p)

tg <- t(g);
2

Sounds like a good idea. Can you please open a feature request on GitHub to make sure this won’t get forgotten? You can copy over the contents of this message.

3

Done.

Reverse the direction of edges and transpose, issue #547

1 Like
4

After some further research I came up with the idea to extend/overload the function t to the igraph class.

# transpose directed weighted graph, including isolates
# Note that unlike graph_from_edgelist,
# add_edges needs a vertex sequence (=transposed edgelist).

t <- function(g){
  if (class(g)[1] == "igraph") {
  tg <- add_edges( delete_edges(g, edges=E(g))
                 , matrix(get.edgelist(g, names=FALSE)[,2:1], nrow=2, byrow=TRUE)
                 )                                                   # revert edges
  edge_attr(tg) <- edge_attr(g)                                      # save edge attributes
  } else {
    UseMethod("t")
  }
return(tg)
}

The real question is to fill in the UseMethod(“t”) for graphs.

5

An interesting example of the application of the transpose is
Kosaraju’s algorithm to find strongly connected components in a graph

https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm
visit <- function(g, v){                       # DFS search
if (length(visited)>0L && !visited[v]) {
  visited[v] <<- 1L                            # mark as visited, global assign
  for (w in V(g)[.outnei(v)]) visit(g, w)      # processing forward neighbours
  subtrees <<- append(subtrees, v)             # append vertex
  }
}

Assign <- function(g, v, root){
  if (!sccs[v]){                               # no root
    sccs[v] <<- root                           # assign root vertex to represent SCC
    for ( w in V(g)[.outnei(v)] ) {            # ∀ descendants that have no root
      if (!sccs[w]) Assign(g, w, root)         # assign root
    }
  } 
}

# first pass -----------------------------------#
visited <- rep(0L, gorder(g))                   # not visited
subtrees <- c()                                 # the vertex numbers, in the order of the completion of their subtree 
for (v in V(g)) visit(g, v)                     # ∀ vertices, search forward, depth first                      
subtrees

# second pass ----------------------------------#
tg <- t.graph(g)                                # transpose graph, revert edges, assuming the vertex numbers don't change
sccs <- rep(0L, gorder(tg))                     # components represented by vertex id / number
for (v in rev(subtrees)){                       # Last In, First Out, retrieve in reverse order
  if (!sccs[v]) Assign(tg, v, v)                # assign v and its descendents to root=v
}
sccs
6

Add
list(groups=split(V(g), sccs)) # list equivalence classes in partition of g

to show the partition of g into strongly connected components.