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

user_5836951 0
Viewed 323

I'm writing a bunch of recursive graph algorithms where graph nodes have parents, children, and a number of other properties. The algorithms can also create nodes dynamically, and make use of recursive functions.

What are the right data structures to use in this case? In C++ I would've implemented this via pointers (i.e. each node has a vector<Node*> parents, vector<Node*> children), but I'm not sure if Julia pointers are the right tool for that, or if there's something else ... ?

graph-traversal julia directed-acyclic-graphs
1 Answers

In Julia state-of-the-art with this regard is the LightGraphs.jl library. It uses adjacency lists for graph representation and assumes that the data for nodes is being kept outside the graph (for example in Vectors indexed by node identifiers) rather than inside the graph. This approach is generally most efficient and most convenient (operating Array indices rather than references).

LightGraphs.jl provides implementation for several typical graph algorithms and is usually the way to go when doing computation on graphs.

However, LightGraphs.jl,'s approach might be less convenient in scenarios where you are continuously at the same time adding and destroying many nodes within the graph.

Now, regarding an equivalent of the C++ approach you have proposed it can be accomplished as

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

And this API can be used as:

node1 = MyNode(nothing)

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

Finally, since LightGraphs.jl is a Julia standard it is usually worth to provide some bridging implementation so your API is able to use LightGraphs.jl functions. For illustration how it can be done for an example have a look for SimpleHypergraphs.jl library.

EDIT:

Normally, for efficiency reasons you will want the data field to be be homogenous across the graph, in that case better is:

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
user_99577100
Related