Finding bridge of not isolated vertices

3 views (last 30 days)
I need to create a cycle that goes through the array of graph edges and finds all non isolated bridges( its vertices have to be not isolated) in between two connected components.
Any suggestions or examples would be great. Thanks in advance.

Answers (1)

Christine Tobler
Christine Tobler on 2 Dec 2020
Edited: Christine Tobler on 2 Dec 2020
There is no functionality for MATLAB's graph class that would compute the bridges / cut edges.
If performance is not a main concern, you could go by definition: For each edge, try removing that edge and check shortestpath to see if there is still a connection between those nodes. If no, that edge is a bridge. You'd need to look at rmedge and shortestpath functions for this. An alternative to calling shortestpath would be to call conncomp and check if the number of connected components has increased - this might be slightly more expensive.
One more thing you could do to limit the amount of edges that are candidates for being a bridge is to call biconncomp. The second output contains the articulation points (or cut vertices), and according to Wikipedia, "The two endpoints of a bridge are articulation vertices unless they have a degree of 1, although it may also be possible for a non-bridge edge to have two articulation vertices as endpoints." So if the two endpoints of an edge aren't articulation points, we know ahead of time that this edge cannot be a bridge.

Categories

Find more on Graph and Network Algorithms in Help Center and File Exchange

Products


Release

R2020b

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!