How to remove self-loops in Lightgraphs

Question

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

score 3 · Answer 1 · answered Jan 08 '21 at 16:01

3

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.

answered Jan 08 '21 at 16:01

sbromberger

1,026
6
12

score 0 · Answer 2 · answered Jan 08 '21 at 18:23

0

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)

answered Jan 08 '21 at 18:23

Przemyslaw Szufel

40,002
3
32
62

thanks, this looks very close to what I was looking for, but strangely enough, it is not efficient compared to my simple solution (see my posted answer). Do you have any idea why is that? – pegah Jan 09 '21 at 21:55
In my code you have `flatten` that does additional allocation but keeps the code short. – Przemyslaw Szufel Jan 09 '21 at 23:35

pegah · Accepted Answer · 2021-01-10T13:03:31.160

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.

Can you benchmark with interpolation? As `@benchmark s11($my_graph)` and `@benchmark s12($my_graph)`. Current benchmarking is not correct. — Andrej Oskin, Jan 09 '21 at 22:15
@AndrejOskin I added them. I kept the previous ones as reference too. The comparison still gives the same result. But could you tell me why benchmarking without interpolation is wrong? — pegah, Jan 10 '21 at 13:05
Here you can find good explanation: https://stackoverflow.com/questions/57314092/when-to-interpolate-in-benchmarking-expressions — Andrej Oskin, Jan 11 '21 at 08:57

How to remove self-loops in Lightgraphs

3 Answers3