# Reverse the direction of edges and transpose

**URL:** <https://igraph.discourse.group/t/reverse-the-direction-of-edges-and-transpose/1290>\
**Category:** Development\
**Tags:** R\
**Created:** [11 July 2022 09:12 UTC](https://igraph.discourse.group/t/reverse-the-direction-of-edges-and-transpose/1290 "2022-07-11T09:12:04Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![KeesP](https://avatars.discourse-cdn.com/v4/letter/k/2bfe46/32.png) [@KeesP](https://igraph.discourse.group/u/KeesP)\
**Post date:** [11 July 2022 09:12 UTC](https://igraph.discourse.group/t/reverse-the-direction-of-edges-and-transpose/1290/1 "2022-07-11T09:12:04Z")

</div>

Regarding issue: [Wishlist: Reverse the direction of edges while preserving attributes · Issue #1477 · igraph/igraph · GitHub](https://github.com/igraph/igraph/issues/1477#event-6964719017) @ 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.

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

```

---

<div class="post-metadata">

**Author:** ![szhorvat](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/szhorvat/32/3_2.png) [@szhorvat](https://igraph.discourse.group/u/szhorvat)\
**Post date:** [11 July 2022 12:29 UTC](https://igraph.discourse.group/t/reverse-the-direction-of-edges-and-transpose/1290/2 "2022-07-11T12:29:10Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![KeesP](https://avatars.discourse-cdn.com/v4/letter/k/2bfe46/32.png) [@KeesP](https://igraph.discourse.group/u/KeesP)\
**Post date:** [11 July 2022 13:01 UTC](https://igraph.discourse.group/t/reverse-the-direction-of-edges-and-transpose/1290/3 "2022-07-11T13:01:56Z")

</div>

Done.

> Reverse the direction of edges and transpose, issue #547

---

<div class="post-metadata">

**Author:** ![KeesP](https://avatars.discourse-cdn.com/v4/letter/k/2bfe46/32.png) [@KeesP](https://igraph.discourse.group/u/KeesP)\
**Post date:** [13 July 2022 13:43 UTC](https://igraph.discourse.group/t/reverse-the-direction-of-edges-and-transpose/1290/4 "2022-07-13T13:43:05Z")

</div>

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

```auto
# 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.

---

<div class="post-metadata">

**Author:** ![KeesP](https://avatars.discourse-cdn.com/v4/letter/k/2bfe46/32.png) [@KeesP](https://igraph.discourse.group/u/KeesP)\
**Post date:** [18 July 2022 09:12 UTC](https://igraph.discourse.group/t/reverse-the-direction-of-edges-and-transpose/1290/5 "2022-07-18T09:12:45Z")

</div>

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

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

```

---

<div class="post-metadata">

**Author:** ![KeesP](https://avatars.discourse-cdn.com/v4/letter/k/2bfe46/32.png) [@KeesP](https://igraph.discourse.group/u/KeesP)\
**Post date:** [19 July 2022 10:52 UTC](https://igraph.discourse.group/t/reverse-the-direction-of-edges-and-transpose/1290/6 "2022-07-19T10:52:23Z")

</div>

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

to show the partition of g into strongly connected components.