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

Question

在朱莉娅。一些弧是 "free"（空重）。但是，当指定权重为 0 时，它不会作为新边添加，并且最短路径问题不会将其包含在可能的解决方案中。有没有一种简单的方法可以将 "free" edges/arcs 添加到 Julia 中的图形？

Answer 1

SimpleWeightedGraphs README example 的这种修改对我有用：

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]

请注意，顶点必须在图中（根据其大小）才能设置它们的权重，如文档中所述：?add_edge!.

Answer 2

关键问题是零值如何在稀疏矩阵（它是 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：初始 add_edge!(g, 1, 3, 0.0) 不起作用的原因是因为在 Julia 中，将新的稀疏矩阵元素的值设置为零是 no-op。)

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

How to add free edge to graph in LightGraphs (Julia)?

graph

julia

lightgraphs