Biconnected graphs
Graphs.jl contains several algorithms to study biconnectivity.
Index
Full docs
Graphs.articulation
— Functionarticulation(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
Graphs.Biconnections
— TypeBiconnections
A state type for depth-first search that finds the biconnected components.
Graphs.biconnected_components
— Functionbiconnected_components(g) -> Vector{Vector{Edge{eltype(g)}}}
Compute the biconnected components of an undirected graph g
and 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]
Graphs.visit!
— Methodvisit!(g, state, u, v)
Perform a DFS visit storing the depth and low-points of each vertex.
Graphs.bridges
— Functionbridges(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