Юлия: Каковы правильные структуры данных для обхода графа?

Question

Я пишу несколько алгоритмов рекурсивного графа, в которых узлы графа имеют родителей, детей и ряд других свойств.Алгоритмы также могут динамически создавать узлы и использовать рекурсивные функции.

Какие структуры данных использовать в этом случае?В C ++ я бы реализовал это с помощью указателей (т. Е. Каждый узел имеет vector<Node*> parents, vector<Node*> children), но я не уверен, что указатели Julia являются правильным инструментом для этого, или есть что-то еще ...?

Answer 1

В этой области у Джулии есть библиотека LightGraphs.jl. Он использует списки смежности для представления графа и предполагает, что данные для узлов хранятся вне графа (например, в Vector с индексами по идентификаторам узлов), а не внутри графа. Этот подход, как правило, наиболее эффективен и наиболее удобен (работает 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 .

EDIT:

Обычно, из соображений эффективности, вы хотите, чтобы поле 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