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

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

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


directed-acyclic-graphs julia graph-traversal
person Gabi    schedule 21.06.2019    source источник
comment
Стандартный пакет графиков Julia: github.com/JuliaGraphs/LightGraphs.jl. Он может соответствовать вашим требованиям. .   -  person Cameron Bieganek    schedule 21.06.2019

Ответы (1)


arrow_upward
4
arrow_downward

В Джулии ультрасовременной в этом плане является библиотека LightGraphs.jl. Он использует списки смежности для представления графа и предполагает, что данные для узлов хранятся вне графа (например, в Vectors, проиндексированных идентификаторами узлов), а не внутри графа. Этот подход, как правило, наиболее эффективен и наиболее удобен (работа с Array индексами, а не со ссылками).

LightGraphs.jl обеспечивает реализацию нескольких типичных графовых алгоритмов и обычно используется при выполнении вычислений на графах.

Однако подход LightGraphs.jl может быть менее удобным в сценариях, когда вы постоянно одновременно добавляете и удаляете множество узлов в графе.

Теперь, что касается эквивалента предложенного вами подхода С++, его можно выполнить как

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
person Przemyslaw Szufel    schedule 21.06.2019