Finding Bridges in a graph C++ (BOOST)?

Question

I was reading through the BOOST library and noticed that they dint have an algorithm to find bridges in a graph, they do have one to find articulation points. Is there anyway this could be done efficiently?

I have an idea:

1. Use the BOOST to find articulation points

2. Using out_edges,find all edges attached the each articulation point

3. remove them and calculate the number on connected components,( I assume my graph is originally fully connected), if its more than 1,i add this edge to the bridges.

QUESTION: Is it necessary for bridges to be attached to articulation points? I just assumed they are,couldn't find anything no the net.

I would also like an idea how to approach this.

My other approach would be more naive and take O(v*(V+E)), which is very bad.

Answer 1

Sounds a bit slow with the whole graph rewriting. You'd have to check if Boost counts a single-connected vertex as an articulation point. (If not, this slightly complicates things).

Now it is fairly obvious that a bridge must be an edge between two articulation points, but not all edges between articulation points are necessarily bridges. Consider a chain of 4 articulation points connected by 3 edges: A-b-c-D. Now add a node e connected to both b and c. The outer two bridges remain bridges, and so all 4 original nodes remain articulation points, but the middle node is no longer a bridge.

This means we have a necessary but insufficient extra condition: both nodes of the edge must be articulation points. Here's where the slight complication steps in; if Boost doesn't count single-connected nodes as articulation points, you have to treat them specially. But that's still simple; that one edge is necessarily a bridge.

This extra condition is quite efficient in dense graphs, as most nodes will not be articulation points. As a result, you cull most candidate edges before trying to alter the graph. Secondly, you don't need to test the component count of the resulting altered graph. You just need to check if the two articulation points are still connected after you cut the edge linking them directly.

Answer 2

There is a much easier way when you realize if a biconnected component only contains one edge this edge is a bridge. It is very easy to implement using boost (http://www.boost.org/doc/libs/1_58_0/libs/graph/example/biconnected_components.cpp):

1. Calculate the biconnected components
2. Create a edge counter for each component. Iteratate over all edge and increase the coresponding edge counter of the respective component
3. Iterate again over all edges and check if the edge counter of the corresponding component is 1, if so this edge is a bridge