如何在LightGraphs (朱莉娅)中给图添加自由边？

Question

我在朱莉娅中向一个简单的加权有向图(来自SimpleWeightedDiGraph()，它是LightGraphs包的一部分)添加边。一些弧是“免费的”(零权重)。但是，当指定0的权重时，它不会被添加为新的边，并且最短路径问题不包括在可能的解决方案中。在Julia中，是否有一种简单的方法可以将“空闲”边/弧添加到图中？

Answer 1

关键问题是零值是如何在稀疏矩阵中表示的(稀疏矩阵是SimpleWeightedGraph的底层数据存储区)。

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:初始add_edge!(g, 1, 3, 0.0)不能工作的原因是，在朱莉娅中，将新的稀疏矩阵元素的值设置为零是没有操作的。)

Answer 2

对SimpleWeightedGraphs 自述实例的修改适用于我：

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]

注意，顶点必须在图中(根据其大小)才能设置权重，如docs：?add_edge!中所述。