thchr
commented
1 month ago Timing-wise, is_articulation(g, v) appears to give a speed-up of about a factor of ~2 in cases I looked at, compared to v ∈ articulation(g):
julia> g = path_graph(5)
julia> articulation(g) # [2, 3, 4]
julia> @btime 2 ∈ articulation($g) # 209.656 ns (8 allocations: 704 bytes)
julia> @btime is_articulation($g, 2) # 122.850 ns (4 allocations: 464 bytes)
julia> g = path_graph(15)
julia> articulation(g) # [2:14...]
julia> @btime 9 ∈ articulation($g) # 453.853 ns (10 allocations: 2.16 KiB)
julia> @btime is_articulation($g, 9) # 245.286 ns (4 allocations: 624 bytes)
codecov[bot]
This factors out the DFS step from
articulationinto a separate functionarticulation_dfs!and then uses this new function to implementis_articulation(g, v)which checks whethervis an articulation point ofgwithout necessarily computing all the articulation points.The branching on
isnothing(is_articulation_pts)inarticulation_dfs!is a bit inelegant - as is the fact thatarticulation_dfs!doesn't mutate ifis_articulation_pts === nothing, but it seemed the simplest way to avoid code duplication.Aside from these additions, I revised the doc string of
articulation(g)a bit (e.g., it 1. previously misleadingly stated thatghad to be connected; it does not; and 2. it changed nomenclature from "articulation point" to "cut vertex" mid-sentence).