set direction in directed graph

Question

I have the following undirected graph g, which was produced from a shapefile of a river. I want to convert g to a directed graph, where vertex 55 is the root and the "direction" of all edges are heading towards the root vertex (imagine the flow of water from all parts of the network towards the root).

Example undirected graph:

library(igraph)

g <- structure(list(From = c(48, 37, 39, 32, 38, 36, 49, 46, 31, 26, 
      33, 35, 18, 23, 45, 41, 42, 47, 52, 51, 50, 54, 16, 14, 8, 10, 
      5, 6, 17, 11, 20, 24, 2, 3, 1, 0, 44, 4, 7, 29, 30, 34, 40, 53, 
      43, 15, 9, 28, 27, 12, 13, 19, 21, 22, 25), To = c(32, 32, 31, 
        31, 33, 33, 45, 45, 23, 23, 26, 26, 16, 16, 35, 35, 41, 41, 50, 
        50, 47, 47, 6, 6, 5, 5, 2, 2, 10, 10, 11, 11, 1, 1, 0, 55, 30, 
        3, 3, 28, 28, 29, 29, 40, 40, 7, 7, 22, 22, 9, 9, 13, 13, 19, 
        19)), class = "data.frame", row.names = c(NA, -55L))

g <- graph.data.frame(g, directed = FALSE) 

l <- igraph::layout_as_tree(g, flip.y = FALSE)
plot(g,
    vertex.size = 10,
    vertex.color = "darkgray",
    layout = l)

I can do the following to create a directed graph, but some edges are directed in the right direction and others are not.

g2 <- get.adjacency(g, sparse = F)
g2[upper.tri(g2)] <- 0
g2 <- igraph::graph.adjacency(g2)

plot(g2,
      vertex.size = 10,
      vertex.color = "darkgray",
      layout = l)

I can see the issue results from how vertices in the adjacency matrix are labelled but cannot come up with a solution.

My Q: Is it possible to convert the undirected graph into a directed graph where the direction of all edges are orientated towards a chosen vertex (in this case vertex 55)?

It is fine if vertices get renamed etc.

mt1022 mt1022 · Accepted Answer · 2020-04-14T06:10:16

For each edge connecting vertex a and b, if the shortest distance of a to 55 is shorter than the shortest distance of b to 55, than b should head towards a. I am not familiar with with igraph, but I came up a way based on this rationale:

d <- distances(g)[, '55']
dd <- outer(d, d, FUN = '>')

g2 <- get.adjacency(g, sparse = F)
g2 <- g2 * dd
g2 <- igraph::graph.adjacency(g2)

plot(g2,
    vertex.size = 10,
    vertex.color = "darkgray",
    layout = l)

Note: the direction of all the arrows can be inverted by changing outer(d, d, FUN = '>') to outer(d, d, FUN = '<').

set direction in directed graph

1 Answers