IGraph: network distance until stop node/vertex

Question

I have an igraph network that contains two types of nodes, one set that describes my points/nodes of interest (NOI) and another set that act as barriers (B) in my network. Now I'd like to measure the total length of all edges that are connected starting from a specific NOI until a barrier is approached. Here a short example using a ring-shape in igraph:

set.seed(123)
g <- make_ring(10) %>%
  set_edge_attr("weight", value = rnorm(10,100,20))%>%
  set_vertex_attr("barrier", value = c(0,0,1,0,0,1,0,0,1,0))%>%
  set_vertex_attr("color", value = c("green","green","red",
                                       "green","green","red",
                                       "green","green","red","green"))

For example when starting from my node 1 (NOI, green) all edges until the nodes 9 and 3 are reachable (the nodes 9 and 3 are barriers B and block). Thus the total connected length of edges for NOI 1 is the sum of the lengths/weights of edges 1--2,2--3,1--10 and 10--9. The same value is true for node 10 as starting node. I the end I am interested in a list/dataframe of all NOI and their total length of reachable network. How to best proceed in R using igraph? Is there a built-in function in igraph?

MrFlick MrFlick · Accepted Answer · 2018-02-09T15:33:34

Here's one possible strategy. First, I set a name for each node so I will be preserved during graph transformations

V(g)$name = seq.int(vcount(g))

Now I drop all the barriers and split the graph up into separate connected nodes of interest that will all share the same length.

gd <- g %>% induced_subgraph(V(g)[V(g)$barrier==0]) %>% decompose()

Then We can write a helper function that takes a subgraph and finds all the incident edges for the nodes in the subgraph in the the original graph, extracts the weights, and sums them up

get_connected_length <- function(x) {
  incident_edges(g, V(g)$name %in% V(x)$name) %>% do.call("c", .) %>% unique() %>% .$weight %>% sum()
}

Now we apply the function to each of the subgraphs and extract the node names

n <- gd %>% Map(function(x) V(x)$name, .)
w <- gd %>% Map(get_connected_length, .)

And we can combine that data all together in a matrix

do.call("rbind", Map(cbind, n, w))
#      [,1]     [,2]
# [1,]    1 361.5366
# [2,]    2 361.5366
# [3,]   10 361.5366
# [4,]    4 335.1701
# [5,]    5 335.1701
# [6,]    7 318.2184
# [7,]    8 318.2184

IGraph: network distance until stop node/vertex

1 Answers