rigraph

Finding out the perimeter of a graph


I have this graph in R:

library(igraph)

set.seed(123)

n <- 20
g <- sample_gnm(n, m = n * 2, directed = FALSE)

while (!is_connected(g)) {
    # Find disconnected components
    components <- components(g)
    
    
    for (i in 2:components$no) {
        from <- sample(which(components$membership == i), 1)
        to <- sample(which(components$membership == 1), 1)
        g <- add_edges(g, c(from, to))
    }
}

g <- simplify(g, remove.multiple = FALSE, remove.loops = TRUE)

V(g)$weight <- runif(vcount(g))

layout <- layout_with_fr(g)


plot(g, layout = layout, edge.arrow.size = 0.1, 
     vertex.label = V(g)$name, vertex.size = 15, 
     vertex.label.color = "black", edge.curved = 0,
     vertex.color = "white", edge.color = "black")

enter image description here

I want to find out a list of all nodes that are on the perimeter.

I tried to do it like this (I read about the eccentricity function):

library(igraph)

find_outer_nodes <- function(g) {
    eccentricities <- eccentricity(g)
    
    diameter <- max(eccentricities)
    
    outer_nodes <- which(eccentricities == diameter)
    
    return(outer_nodes)
}

outer_nodes <- find_outer_nodes(g)

print(outer_nodes)

The answer looks like this:

[1]  2  3  7 13 16 18 19 20

Is there a more direct way to do this in R?


Solution

  • If you call a "one-liner" as "a more direct way", probably you can try

    > V(g)[sort(unique(c(which(distances(g) == diameter(g), TRUE))))]
    + 8/20 vertices, from d1b927a:
    [1]  2  3  7 13 16 18 19 20
    
    > V(g)[(ec <- eccentricity(g)) == max(ec)]
    + 8/20 vertices, from b0e7de3:
    [1]  2  3  7 13 16 18 19 20