Function to find edges which are bridges in R igraph

Usage
1

I’m looking to split my graph into multiple components by removing its bridges. This functionality appears to be available in the C igraph, but not from R. Until this function becomes available, would someone be willing to help me implement a function to do this from R?

2

Here’s an idea: use the biconnected_components function and look at the returned edges. Any edge that forms a component alone will be a bridge.

I am not particularly experienced with R, so I’ll leave it to you to filter one length-1 edge-components.

3 
set.seed(523)
g <- erdos.renyi.game(100, 120, 'gnm')

comps <- biconnected_components(g)

bridges <- comps$component_edges[ lapply(comps$component_edges, length) == 1 ]

ecol <- rep('gray', ecount(g))
ecol[unlist(bridges)] <- 'red'

plot(g, vertex.size=6, vertex.label=NA, edge.color=ecol)

image
image838×828 97.8 KB

This comes with the warning that I am not at all fluent in R and there is probably a simpler way to implement the details of the selection and plotting.

4

Your code worked perfectly! I was spending all my time learning about Tarjan’s algorithm and depth first search spanning trees rather than thinking about my research questions. Thank you so much!

Your approach translates nicely to tidygraph:

my_tidy_graph %E>%
  mutate(cluster = group_biconnected_component()) %>%
  group_by(cluster) %>%
  mutate(nmembers = n(),
         bridge = nmembers == 1) %>%
  ggraph() +
  geom_edge_link(aes(edge_color = bridge)) +
  geom_node_point(alpha = 0.3) +
  geom_node_text(aes(label = name), nudge_y = 0.5, repel = TRUE) +
  theme(legend.position = "bottom") +
  scale_edge_color_manual(values = c("black", "red3"))
5

There is a bridges([graph]) function in igraph; it’s hidden under the documentation for articulation_points(graph).

6

Indeed, bridges() is new in igraph 1.3.

Its documentation is not hidden, merely shared with articulation_points(). You will find bridges() in the index.