Saya baru mengenal Julia dan LightGraphs dan saya telah mencoba menemukan cara paling efisien untuk mendeteksi dan menghapus loop otomatis. Sejauh ini, satu-satunya cara yang saya temukan adalah mengulangi semua node di Simplegraph, memeriksa apakah ia memiliki loop sendiri, dan menghapusnya. Apakah ada cara yang lebih baik seperti menggunakan kombinasi ini di Python NetworkX: G.remove_edges_from(G.selfloop_edges())?

Cara saya melakukannya sekarang:

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
2
pegah 8 Januari 2021, 16:11

3 jawaban

Jawaban Terbaik

Saya melakukan pembandingan cepat antara solusi saya (tanpa has_edge(), terima kasih @sbromberger!) dan yang diusulkan oleh @Przemyslaw (terlihat cukup rapi!). Sepertinya cara sederhana saya ini masih merupakan cara yang paling efisien, baik dari segi memori maupun waktu. Saya terkejut melihat simplecycles_limited_length() melakukan lebih buruk daripada loop, mengingat fungsinya tampaknya untuk tujuan khusus ini. Jika Anda tahu mengapa demikian, beri tahu saya.

Berikut adalah hasil benchmarking saya (my_graph memiliki 22.470 node dan 170.823 edge dengan 179 self-loop):

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)

Sunting: Menambahkan tolok ukur yang diinterpolasi seperti yang diminta.

0
pegah 10 Januari 2021, 13:03

Itu mungkin cara terbaik untuk melakukannya secara kondisional, tetapi Anda bisa memanggil rem_edge!(G, node, node) tanpa pemeriksaan has_edge() - ini mengembalikan bool yang menunjukkan apakah tepi telah dihapus sehingga aman digunakan jika tidak ada tepi yang sebenarnya sana.

3
sbromberger 8 Januari 2021, 16:01

Anda dapat menemukan simpul yang memiliki loop sendiri dengan perintah:

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

Untuk menghapusnya lakukan saja:

rem_edge!.(Ref(g), vxs, vxs)
0
Przemyslaw Szufel 8 Januari 2021, 18:23