Biconnected graphs

Graphs.jl contains several algorithms to study biconnectivity.

Full docs

Graphs.articulationFunction
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
source
Graphs.biconnected_componentsFunction
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]
source
Graphs.bridgesFunction
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
source