Module Components.Connectivity

Parameters

module GB : Builder.S

Signature

module S : Set.S with type elt = GB.G.vertex
val strong_articulation_points : GB.G.t -> GB.G.vertex list

Computes the strong articulation points of the given strongly connected directed graph. The result is undefined if the input graph is not directed and strongly connected.

A strong articulation point is a vertex that when removed from the original graph disconnects that graph into two or more components.

The implementation involves constructing the mirror image of the graph; for bidirectional graphs prefer BiConnectivity.

Implements the algorithm from Italiano, Laura, and Santaroni, TCS 447 (2012), "Finding strong bridges and strong articulation points in linear time". Complexity: O(V + E)

val sstrong_articulation_points : GB.G.t -> S.t

As for strong_articulation_points but returns a set.