如何删除 Lightgraphs 中的自循环

Question

我是 Julia 和 LightGraphs 的新手，我一直在努力寻找检测和删除自循环的最有效方法。到目前为止，我找到的唯一方法是遍历 Simplegraph 中的所有节点，检查它是否有自循环，然后将其删除。有没有更好的方法，比如在 Python NetworkX 中使用此组合：G.remove_edges_from(G.selfloop_edges())?

我现在的做法：

path = adrs\to\my\edgeList
G = SimpleGraph(loadgraph(path, GraphIO.EdgeList.EdgeListFormat()))
for node in vertices(G)
   if has_edge(G,node,node)
      rem_edge!(G,node,node)
   end
end

Answer 1

这可能是有条件地执行此操作的最佳方法，但您可以在不进行 has_edge() 检查的情况下调用 rem_edge!(G, node, node) - 它 returns 一个布尔值，指示边缘是否已被删除如果那里没有实际边缘，可以安全使用。

Answer 2

您可以使用以下命令找到具有自循环的顶点：

vxs = Iterators.flatten(simplecycles_limited_length(g,1))

要删除它们，只需执行以下操作：

rem_edge!.(Ref(g), vxs, vxs)

Answer 3

我在我的解决方案（没有 has_edge()，感谢@sbromberger！）和@Przemyslaw 提出的解决方案（看起来很整洁！）之间做了一个快速基准测试。看来我的简单方法仍然是最有效的方法，无论是在内存还是时间方面。我很惊讶地看到 simplecycles_limited_length() 比循环更糟糕，考虑到函数似乎是为了这个特定目的。如果你知道这是为什么，请告诉我。

这是我的基准测试结果（my_graph 有 22,470 个节点和 170,823 个边以及 179 个自环）：

using BenchmarkTools


function sl1(G)
    for node in vertices(G)
      rem_edge!(G,node,node)
    end
end

function sl2(G)
    vxs = Iterators.flatten(simplecycles_limited_length(G,1))
    rem_edge!.(Ref(G), vxs, vxs)
end

@benchmark sl1(my_graph)
>>> BenchmarkTools.Trial: 
  memory estimate:  0 bytes
  allocs estimate:  0
  --------------
  minimum time:     554.401 μs (0.00% GC)
  median time:      582.899 μs (0.00% GC)
  mean time:        592.032 μs (0.00% GC)
  maximum time:     1.292 ms (0.00% GC)
  --------------
  samples:          8440
  evals/sample:     1

@benchmark sl1($my_graph)
>>> BenchmarkTools.Trial: 
  memory estimate:  0 bytes
  allocs estimate:  0
  --------------
  minimum time:     555.500 μs (0.00% GC)
  median time:      603.501 μs (0.00% GC)
  mean time:        616.309 μs (0.00% GC)
  maximum time:     1.281 ms (0.00% GC)
  --------------
  samples:          8108
  evals/sample:     1


@benchmark sl2(my_graph)
>>> BenchmarkTools.Trial: 
  memory estimate:  448 bytes
  allocs estimate:  6
  --------------
  minimum time:     792.400 μs (0.00% GC)
  median time:      836.000 μs (0.00% GC)
  mean time:        855.634 μs (0.00% GC)
  maximum time:     1.836 ms (0.00% GC)
  --------------
  samples:          5839
  evals/sample:     1

@benchmark sl2($my_graph)
>>> BenchmarkTools.Trial: 
  memory estimate:  448 bytes
  allocs estimate:  6
  --------------
  minimum time:     795.600 μs (0.00% GC)
  median time:      853.250 μs (0.00% GC)
  mean time:        889.450 μs (0.00% GC)
  maximum time:     2.022 ms (0.00% GC)
  --------------
  samples:          5618
  evals/sample:     1


@btime sl1(my_graph)
>>> 555.999 μs (0 allocations: 0 bytes)
@btime sl1($my_graph)
>>>  564.000 μs (0 allocations: 0 bytes)


@btime sl2(my_graph)
>>> 781.800 μs (6 allocations: 448 bytes)
@btime sl2($my_graph)
>>>  802.200 μs (6 allocations: 448 bytes)

编辑：根据要求添加了插值基准。

如何删除 Lightgraphs 中的自循环

How to remove self-loops in Lightgraphs

julia

lightgraphs