I am adding edges to a simple weighted directed graph (from SimpleWeightedDiGraph() that is part of LightGraphs package) in Julia. Some of the arcs are "free" (null weight). However, when specifying the weight of 0 it is not added as a new edge and a shortest path problem does not include it in the possible solution. Is there an easy way to add "free" edges/arcs to a graph in Julia?
The key issue is how zero values are represented in a sparse matrix (which is the underlying data store for SimpleWeightedGraphs. While it is true that the underlying zero value is preserved once it's explicitly set:
julia> g = SimpleWeightedGraph(6)
{6, 0} undirected simple Int64 graph with Float64 weights
julia> add_edge!(g, 1, 2, 1.0)
true
julia> add_edge!(g, 1, 3, 1.0)
true
julia> add_edge!(g, 1, 3, 0.0)
true
julia> weights(g)
6×6 SparseMatrixCSC{Float64,Int64} with 4 stored entries:
[2, 1] = 1.0
[3, 1] = 0.0
[1, 2] = 1.0
[1, 3] = 0.0
this will fail if you have to do anything with the edges:
julia> collect(edges(g))
1-element Array{SimpleWeightedGraphs.SimpleWeightedEdge{Int64,Float64},1}:
Edge 1 => 2 with weight 1.0
There's no really good solution to this. My advice is to use a sufficiently small weight as proposed above to approximate a zero value.
(PS: the reason the initial add_edge!(g, 1, 3, 0.0) doesn't work is because in Julia, setting the value of a new sparsematrix element to zero is a no-op.)