Julia：图遍历的正确数据结构是什么？

Question

我正在编写一堆递归图算法，其中图节点具有父节点、子节点和许多其他属性。该算法还可以动态创建节点，并利用递归函数。

在这种情况下应该使用哪些正确的数据结构？在 C++ 中，我会通过指针实现它（即每个节点都有一个 vector<Node*> parents、vector<Node*> children），但我不确定 Julia 指针是否是正确的工具，或者是否还有其他东西...？

Answer 1

在 Julia state-of-the-art 中，LightGraphs.jl 库就是这方面的。它使用邻接表表示图，并假设节点的数据保存在图外（例如，在由节点标识符索引的 Vectors 中）而不是图内。这种方法通常是最有效和最方便的（操作 Array 索引而不是引用）。

LightGraphs.jl 提供了几种典型的图算法的实现，通常是在图上进行计算时的方法。

但是，LightGraphs.jl 的方法在您连续同时添加和销毁图中的许多节点的情况下可能不太方便。

现在，关于您提出的 C++ 方法的等价物，它可以完成为

struct MyNode{T}
       data::T
       children::Vector{MyNode}
       parents::Vector{MyNode}
       MyNode(data::T,children=MyNode[],parents=MyNode[]) where T= new{T}(data,children,parents)
end

而这个API可以用作：

node1 = MyNode(nothing)

push!(node1.parents, MyNode("hello2"))

最后，由于 LightGraphs.jl 是 Julia 标准，通常值得提供一些桥接实现，以便您的 API 能够使用 LightGraphs.jl 函数。为了说明如何完成示例，请查看 SimpleHypergraphs.jl 库。

编辑：

通常，出于效率原因，您会希望 data 字段在图表中是同质的，在这种情况下更好的是：

struct MyNode{T}
       data::T
       children::Vector{MyNode{T}}
       parents::Vector{MyNode{T}}
       MyNode(data::T,children=MyNode{T}[],parents=MyNode{T}[]) where T= new{T}(data,children,parents)
end

Julia：图遍历的正确数据结构是什么？

Julia: What are the right data structures for graph traversal?

graph-traversal

directed-acyclic-graphs

julia