# Reverse the direction of edges and transpose

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);
``````

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.

Done.

Reverse the direction of edges and transpose, issue #547

1 Like

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) == "igraph") {
, 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.

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
``````

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