In igraph in R: how can I remove non-branch-point vertices, while maintaining connectivity?

1
votes

I have a graph extracted from an image of several tree-like structures. The graph has a vertex for every articulation point, even if that point is not a branch or end (i.e. the node order is 2). I'd like to remove these order-2 vertices, but maintain connectivity so that the branch point or end vertices that would have been connected through these intermediates are now connected by a single edge. I can do this for small graphs by removing vertices and connecting edges one-at-a-time, but this is slow when working with 10,000+ edges.

This is an example starting graph. I'd like to remove (for example) vertices 8 and 6, while inserting an edge connecting 9 and 4. Similarly, I'd like to remove vertex 5 while inserting an edge between 7 and 4.

enter image description here

edge_matrix = cbind(
  c(1,2,3,4,4,5,6,8,9,9,10,11),
  c(2,3,4,5,6,7,8,9,10,11,12,13))
example_graph = graph.data.frame(edge_matrix, directed=F)

structure(list(13, FALSE, c(1, 2, 3, 4, 5, 10, 6, 7, 8, 9, 11, 
12), c(0, 1, 2, 3, 3, 4, 5, 6, 7, 7, 8, 9), c(0, 1, 2, 3, 4, 
6, 7, 8, 9, 5, 10, 11), c(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
), c(0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12), c(0, 1, 2, 
3, 5, 6, 7, 8, 10, 11, 12, 12, 12, 12), list(c(1, 0, 1), structure(list(), .Names = character(0)), 
    structure(list(name = c("1", "2", "3", "4", "5", "6", "8", 
    "9", "10", "11", "7", "12", "13")), .Names = "name"), list()), 
    <environment>), class = "igraph")
2
rigraph

2 Answers

3
votes

Actually, it may be better to just remove the nodes of degree 2 in the graph rather than trying to rebuild the graph with minimal information. This function doesn't bother with recursion and is probably more efficient

trim_deg2 <- function(g) {
  get_deg2 <- function(x) {
    dd <- degree(x)
    trim <- V(x)[names(dd[dd==2])]    
  }
  ng <- g
  trim <- get_deg2(ng)
  while(length(trim)) {
    tv <- trim[1]
    touch <- adjacent_vertices(ng, tv)[[1]]
    ng <- delete_edges(ng, E(ng)[tv %--% touch])
    ng <- add_edges(ng, touch$name)
    ng <- delete_vertices(ng, V(ng)[tv])
    trim <- get_deg2(ng)
  }
  ng
}

It works with your sample data

g <- trim_deg2(example_graph)
plot(g)

enter image description here

0
votes

I'm pretty sure I'm doing this the wrong way, but here's a function that basically walks the graph looking for nodes with degree != 2 and re-connects them all into a new graph.

walk_thin <- function(g, v=V(g)[[1]]) {
  dd <- degree(g)
  keep <- V(g)[names(dd[dd!=2])]
  edges <- c()
  find_next <- function(v, from, past = c()) {
    v2 <- adjacent_vertices(g, v)[[1]]
    v2 <- v2[!v2 %in% past]
    for(i in seq_along(v2)) {
      nv <- v2[i]
      if (nv %in% keep) {
        edges <<- c(c(from, nv)$name, edges)
        find_next(nv, nv, past=c(nv, past))
      } else {
        find_next(nv, from, past=c(nv, past))
      }
    }
  }
  find_next(v, v, v)  
  make_graph(edges,directed = FALSE)
}

It seems to work with your sample data

g <- walk_thin(example_graph)
plot(g)

enter image description here