2

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?

TylerH
  • 20,799
  • 66
  • 75
  • 101
Berni
  • 93
  • 10

2 Answers2

5

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.)

sbromberger
  • 1,026
  • 6
  • 12
0

This modification of the SimpleWeightedGraphs README example works for me:

using LightGraphs, SimpleWeightedGraphs

# set the size of the graph
g = SimpleWeightedDiGraph(3) 

add_edge!(g, 1, 2, 0.5)
add_edge!(g, 2, 3, 0.8)
add_edge!(g, 1, 3, 2.0)

# find the shortest path from vertex 1 to vertex 3 taking weights into account.
enumerate_paths(dijkstra_shortest_paths(g, 1), 3) # gives [1,2,3]

# reweight the edge from 1 to 3 to be "free"
add_edge!(g, 1, 3, 0.0)

enumerate_paths(dijkstra_shortest_paths(g, 1), 3) # gives [1,3]

Notice that the vertices must be in the graph (according to its size) to be able to set their weights, as stated in the docs: ?add_edge!.

Ilya Orson
  • 158
  • 1
  • 10
  • Thanks for the answer! Apparently, if the edge is first added with a non-zero weight and then reweighted to zero it works. However, if I try to add them with weight zero from the beginning it does not take it into account. Am I missing something? Is there a direct way of adding free edges? – Berni Feb 26 '18 at 08:02
  • 2
    Looking at the source code I would say that the design of `SimpleWeightedGraphs` did not take zero weight edges into account so using this trick is risky. For instance `edges(g)` will not return `0` weight edges in a list of edges. Probably an appropriate PR to this package would be needed if you want this supported. I would consider using weight equal to `5.0e-324` as a workaround (though it is a hack also). Unless you would use really small numbers it will not affect the resulting length of the shortest path due to rounding. – Bogumił Kamiński Feb 26 '18 at 10:08
  • 1
    This will have unintended side effects, because setting the weight to 0.0 effectively removes the edge. See my response. – sbromberger Feb 26 '18 at 18:15