如何在 LightGraphs (Julia) 中向图形添加自由边？

Question

我正在Julia 中向一个简单的加权有向图（来自SimpleWeightedDiGraph()，它是LightGraphs包的一部分）添加边。一些弧是“自由的”（空权重）。但是，当指定权重为 0 时，它不会作为新边添加，最短路径问题也不会将其包含在可能的解决方案中。有没有一种简单的方法可以将“自由”边/弧添加到 Julia 中的图形中？

Answer 1

关键问题是如何在稀疏矩阵中表示零值（这是SimpleWeightedGraphs的底层数据存储。虽然一旦明确设置底层零值确实会被保留：

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

如果您必须对边缘做任何事情，这将失败：

julia> collect(edges(g))
1-element Array{SimpleWeightedGraphs.SimpleWeightedEdge{Int64,Float64},1}:
 Edge 1 => 2 with weight 1.0

对此没有很好的解决方案。我的建议是使用上述建议的足够小的权重来近似为零值。

（PS：initialadd_edge!(g, 1, 3, 0.0)不起作用的原因是因为在 Julia 中，将新 sparsematrix 元素的值设置为零是无操作的。）