2

我是 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
4

3 回答 3

3

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

于 2021-01-08T16:01:33.473 回答
0

我在我的解决方案（没有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)

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

于 2021-01-09T21:52:56.560 回答
0

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

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

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

rem_edge!.(Ref(g), vxs, vxs)
于 2021-01-08T18:23:09.597 回答