Biconnected graphs

articulation(g)

Compute the articulation points of a connected graph g and return an array containing all cut vertices.

Examples

julia> using Graphs

julia> articulation(star_graph(5))
1-element Vector{Int64}:
 1

julia> articulation(path_graph(5))
3-element Vector{Int64}:
 2
 3
 4

Biconnections

A state type for depth-first search that finds the biconnected components.

biconnected_components(g) -> Vector{Vector{Edge{eltype(g)}}}

Compute the biconnected components of an undirected graph gand return a vector of vectors containing each biconnected component.

Performance: Time complexity is $\mathcal{O}(|V|)$.

Examples

julia> using Graphs

julia> biconnected_components(star_graph(5))
4-element Vector{Vector{Graphs.SimpleGraphs.SimpleEdge{Int64}}}:
 [Edge 1 => 3]
 [Edge 1 => 4]
 [Edge 1 => 5]
 [Edge 1 => 2]

julia> biconnected_components(cycle_graph(5))
1-element Vector{Vector{Graphs.SimpleGraphs.SimpleEdge{Int64}}}:
 [Edge 1 => 5, Edge 4 => 5, Edge 3 => 4, Edge 2 => 3, Edge 1 => 2]

visit!(g, state, u, v)

Perform a DFS visit storing the depth and low-points of each vertex.

bridges(g)

Compute the bridges of a connected graph g and return an array containing all bridges, i.e edges whose deletion increases the number of connected components of the graph.

Examples

julia> using Graphs

julia> bridges(star_graph(5))
4-element Vector{Graphs.SimpleGraphs.SimpleEdge{Int64}}:
 Edge 1 => 2
 Edge 1 => 3
 Edge 1 => 4
 Edge 1 => 5

julia> bridges(path_graph(5))
4-element Vector{Graphs.SimpleGraphs.SimpleEdge{Int64}}:
 Edge 4 => 5
 Edge 3 => 4
 Edge 2 => 3
 Edge 1 => 2