I work on combinarotial optimization, so I am looking data structures storing weighed graph.
At https://juliagraphs.org/, I found SimpleWeightedGraphs, MetaGraphs, MetaGraphsNext.
However, neither of them seems to me to be reasonably fast. For a small demonstration,
consider the following comparison on Bellman-Ford algorithm.
using Graphs
using SimpleWeightedGraphs
using MetaGraphs
using MetaGraphsNext
using BenchmarkTools
struct DataGraph <: AbstractGraph{Int}
fadjlist::Vector{Vector{Tuple{Int,Int}}}
end
DataGraph(nvg::Int) = DataGraph([ Vector{Tuple{Int,Int}}() for _ in 1:nvg ])
Graphs.nv(g::DataGraph) = length(g.fadjlist)
Graphs.vertices(g::DataGraph) = 1:nv(g)
incident(g::DataGraph, u::Int) = g.fadjlist[u]
function Graphs.add_edge!(g::DataGraph, u::Int, v::Int, w::Int)
push!(g.fadjlist[u], (v,w))
push!(g.fadjlist[v], (u,w))
end
# Source: https://github.com/JuliaGraphs/Graphs.jl/blob/master/src/shortestpaths/bellman-ford.jl
function Graphs.bellman_ford_shortest_paths(graph::DataGraph, sources::AbstractVector{<:Integer})
nvg = nv(graph)
active = falses(nvg)
active[sources] .= true
dists = fill(typemax(Int), nvg)
parents = zeros(Int, nvg)
dists[sources] .= 0
no_changes = false
new_active = falses(nvg)
for i in vertices(graph)
no_changes = true
new_active .= false
for u in vertices(graph)[active]
for (v,w) in incident(graph, u) # Changed
relax_dist = w + dists[u] # Changed
if dists[v] > relax_dist
dists[v] = relax_dist
parents[v] = u
no_changes = false
new_active[v] = true
end
end
end
if no_changes
break
end
active, new_active = new_active, active
end
no_changes || throw(NegativeCycleError())
return Graphs.BellmanFordState(parents, dists)
end
function main()
println("Loading data")
# https://data.4tu.nl/articles/dataset/Network_instance_Chordal_fixed_treewidth_edition_1/12697523/1
filename = "4tu_chordal/chordal-varNodes-3125,211,1.dimacs"; srcs = [3125] # 3125 & 637009
all_edges = [tuple(parse.(Int, split(line)[2:4])...) for line in eachline(filename) if line[1] == 'a' ]
println("Creating graphs")
swg = SimpleWeightedGraph([ x[1] for x in all_edges ], [ x[2] for x in all_edges ], [ x[3] for x in all_edges ]; combine = max)
println("Vertices $(nv(swg)), original edges $(length(all_edges)), half $(length(all_edges)/2), unique $(ne(swg))")
empty!(all_edges)
dg = DataGraph(nv(swg))
mg = MetaGraphs.MetaGraph(nv(swg))
mgn = MetaGraphsNext.MetaGraph(Graph(), Label = Int64, VertexData = Int64, EdgeData = Int64, weight_function = identity)
for i in 1:nv(swg)
add_vertex!(mgn, i, i)
end
for e in edges(swg)
u,v = src(e),dst(e)
w = get_weight(swg, u, v)
add_edge!(dg, u, v, w)
add_edge!(mg, u, v, :weight, w)
add_edge!(mgn, u, v, w)
end
println("Precompiling")
state1 = bellman_ford_shortest_paths(dg, srcs)
state2 = bellman_ford_shortest_paths(swg, srcs)
@assert all(state1.dists .== state2.dists)
state2 = bellman_ford_shortest_paths(mg, srcs)
@assert all(state1.dists .== state2.dists)
state2 = bellman_ford_shortest_paths(mgn, srcs)
@assert all(state1.dists .== state2.dists)
state1 = state2 = nothing
println("SimpleWeightedGraph")
display(@benchmark bellman_ford_shortest_paths($swg, $srcs))
println()
println("MetaGraph")
display(@benchmark bellman_ford_shortest_paths($mg, $srcs))
println()
println("MetaGraphNext")
display(@benchmark bellman_ford_shortest_paths($mgn, $srcs))
println()
println("DataGraph")
display(@benchmark bellman_ford_shortest_paths($dg, $srcs))
println()
println("SimpleWeightedGraph")
display(@benchmark bellman_ford_shortest_paths($swg, $srcs))
println()
end
main()
The tested graph contains 3125 vertices and 637009 edges. Median running times are
MetaGraph: 1.720 s
MetaGraphNext: 1.097 s
SimpleWeightedGraph: 128.038 ms
My DataGraph: 4.403 ms
The diffence is caused by the way weights are stored: MetaGraph and MetaGraphNext
uses hash tables and SimpleWeightedGraph uses binary search in a sparse matrix.
I know that my graph representation may not be ideal in all situations.
This is just a simple demonstration of the potential for significant improvements.
There are many algorithms accessing all edges incident to a vertex together with its weight or other data.
In order to access the weight of a given edge, this example can be extended e.g. by sorting the list of neighbors or adding a hash table.
Are there some other packages for weighed graphs? Do I miss something?
Tested on
Julia 1.7.0
[86223c79] Graphs v1.7.1
[626554b9] MetaGraphs v0.7.1
[fa8bd995] MetaGraphsNext v0.3.0
[47aef6b3] SimpleWeightedGraphs v1.2.1