How to remove self-loops in Lightgraphs

user_7824204 0
Viewed 198

I am new to Julia and LightGraphs and I have been trying to find the most efficient way of detecting and removing self-loops. So far, the only way I have found is to iterate over all nodes in the Simplegraph, check whether it has a self-loop, and remove them. Is there any better way like using this combination in Python NetworkX: G.remove_edges_from(G.selfloop_edges())?

The way I am doing it right now:

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
lightgraphs julia
3 Answers

that's probably the best way to do it conditionally, but you can just call rem_edge!(G, node, node) without the has_edge() check - it returns a bool indicating whether the edge was removed so is safe to use if there's not an actual edge there.

user_70817170

You can find the vertices having the self loops with the command:

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

To remove them just do:

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

I did a quick benchmarking between my solution (without the has_edge(), thanks @sbromberger!) and the one proposed by @Przemyslaw (looks quite neat!). It seems my simple way of doing it is still the most efficient way, both in terms of memory and time. I was surprised to see the simplecycles_limited_length() does worse than the loop, considering the function seems to be for this specific purpose. If you know why that is, please let me know.

Here are my benchmarking results (my_graph has 22,470 nodes and 170,823 edges with 179 self-loops):

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)

Edit: Added the interpolated benchmarks as requested.

user_78242040
Related