Biconnected graphs

articulation(g)

Compute the articulation points (also known as cut or seperating vertices) of an undirected graph g and return a vector containing all the vertices of g that are articulation points.

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

is_articulation(g, v)

Determine whether v is an articulation point of an undirected graph g, returning true if so and false otherwise.

See also articulation.

Examples

julia> using Graphs

julia> g = path_graph(5)
{5, 4} undirected simple Int64 graph

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

julia> is_articulation(g, 2)
true

julia> is_articulation(g, 1)
false

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