Networkx "ancestor" Julia LightGraphs 中的等效项

Question

Julia 中是否有一个 LightGraph 函数等同于 Networkx 中的 ancestors 函数？

Answer 1

不是原生的，但应该很容易近似：

function ancestors(g, src)
    reverse!(g)
    a = reduce(union, enumerate_paths(dijkstra_shortest_paths(g, src))
    reverse!(g)
    return a
end

这需要验证，如果函数在第二个 reverse! 之前退出，这会有点冒险，但它比非变异 reverse().

更有效

Answer 2

可能更快的方法：

function ancestors(g::SimpleDiGraph{T}, src) where T <: Integer
    reverse!(g)
    a = Vector{T}()
    for (v, d) in enumerate(gdistances(g, src))
        if d < typemax(T)
            push!(a, v)
        end
    end
    reverse!(g)
    return a
end

Networkx "ancestor" Julia LightGraphs 中的等效项

Networkx "ancestor" equivalence in Julia LightGraphs

python

networkx

julia

lightgraphs