Skip to main content

Bridge Detection

Description​

As in the real world, the definition of a bridge in graph theory denotes something that divides an entity into multiple components. Thus, more precisely, the bridge in graph theory denotes an edge that, when removed, divides the graph into two separate components.

drawing

Example of bridges on the graph. Bold edges represent bridges.

This algorithm is frequent as part of the initial graph analysis. It talks a lot about the connection itself and reveals, depending on the domain, the points of the graph that connect the different components. The first linear algorithm for finding bridges within a graph was written in 1974 by Robert Tarjan.

Materials​

Implementation​

Bridges

Bridges

Bridges Detection is implemented as part of the MAGE project. Be sure to check it out in the link above. ☝️

Use cases​

Transport industry

In the transport industry, the application of the bridge recognition algorithm is intuitive. By analogy with the real world, bridges are key points of traffic, and their functioning is essential to the functioning of any city.

Traffic planning will always involve looking for bottleneck points that will connect more components and thus help build better infrastructure.

Internet Networks

Just like the previous example, Internet networks are organized similarly to a transport network, and as such, contain bottlenecks that are bridges to that big graph. Such points need to be strengthened with excellent infrastructure, which will prevent the possibility of unexpected system crashes.