如何删除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()，谢谢@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)

编辑:根据需要添加插值基准。

Answer 2

这可能是有条件的最好方法，但您可以只调用rem_edge!(G, node, node)而不进行has_edge()检查-它返回一个布尔值，指示边缘是否已删除，因此如果没有实际的边缘，则可以安全地使用它。

Answer 3

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

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

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

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