4

I am analyzing an undirected graph in R. I'm trying to (eventually) write a function to get the ratio of the size (number of vertices) of the largest connected component to the size of the largest biconnected component - of any random graph. I was able to extract the size of the largest connected component, but am having trouble with the size of the largest biconnected component. I started off using the igraph function biconnected_components on graph g:

bicomponent_list <- biconnected_components(g)
bicomponent_list$components # lists all of the components, including size and vertex names
length(bicomponent_list$components[[1]]) # returns number of vertices of first bicomponent

Then my half-baked idea was to somehow order this list in decreasing number of vertices, so that I can always call length(bicomponent_list$components[[1]]) and it will be the largest biconnected component. But I don't know how to sort this correctly. Perhaps I have to convert it to a vector? But I also don't know how to specify that I want the number of vertices in the vector. Does anyone know, or have a better way to do it? Thanks so much!

library(igraph)

# generating sample graph
g1 <- barabasi.game(100, 1, 5)
V(g1)$name <- as.character(1:100)

g2 <- erdos.renyi.game(50, graph.density(g1), directed = TRUE)
V(g2)$name <- as.character(101:200)

g3 <- graph.union(g1, g2, byname = TRUE)

# analyzing the bicomponents
bicomponent_list <- biconnected_components(g3)
bi_list <- as.list(bicomponent_list$components)
bi_list <- lapply(bi_list, length) # lists the sizes of all of the components that I want to reorder

My desired outcome would be ordering bi_list such that length(bicomponent_list$components[[1]]) returns the bicomponent with the most vertices.

Audrey
  • 99
  • 7
  • It would be helpful if you provided a minimal [reproducible example](http://stackoverflow.com/questions/5963269/how-to-make-a-great-r-reproducible-example) with sample input data and the desired result for that input. Be sure to include all relevant `library()` statements. – MrFlick Nov 28 '15 at 02:01
  • OK, I did so. I hope that makes more sense. Maybe I need to figure out some way to get a list of length(biconnected_components$components[[i]])? – Audrey Nov 28 '15 at 02:12

1 Answers1

1

The components property is a list containing vertex lists. You can iterate over them and find the length of them like so

sapply(bicomponent_list$components, length)

and if you just wanted the largest, wrap that in a max()

max(sapply(bicomponent_list$components, length))
MrFlick
  • 195,160
  • 17
  • 277
  • 295