Julia LightGraphs komponen_terhubung_lemah

Bukankah seharusnya komponen yang terhubung_lemah di julia LightGraphs menyediakan komponen yang terhubung dimana jika DiGraph diubah menjadi grafik tidak berarah, maka setiap komponen harus terhubung? Saya sudah mencobanya dan saya tidak menerima komponen seperti itu? Sebagai contoh saya telah mencobanya pada data blog politik sebagai jaringan tidak terarah

data=readdlm(path,',',Int64) #contains edges in each row
N_ = length(unique(vcat(data[:,1],data[:,2]))) ##to get number of vertices
network  = LightGraphs.DiGraph(N_)
#construct the network
for i in 1:size(data,1)
    add_edge!(network, Edge(data[i,1], data[i,2]))
end
#largest weakly connected component
net = weakly_connected_components(network)[1]
temp_net,vmap = induced_subgraph(network, net)

dan setelah mendapatkan komponen terhubung lemah terbesar, saya melihat yang berikut:

isempty([i for i in vertices(temp_net) if isempty(edges(temp_net).adj[i])])

julia>false

yang menandakan beberapa node tidak memiliki tepi masuk atau keluar. Apa masalahnya? Saya menggunakan rilis terbaru 6, tetapi pengujian paket LightGraphs tampaknya berfungsi.


julia directed-graph lightgraphs
person A.Yazdiha    schedule 01.06.2017    source sumber

Jawaban (2)


arrow_upward
2
arrow_downward

Jawaban TL;DR adalah edges(temp_net).adj[i] hanya berisi simpul-simpul yang terhubung dengan i, dan bukan simpul-simpul yang terhubung ke i. Dan beberapa simpul tidak memiliki sisi masuk.

Versi yang lebih panjang, adalah yang berikut ini yang menunjukkan temp_net dalam jaringan yang dibuat secara acak dan ditetapkan karena dalam pertanyaan memang terhubung dengan lemah. Pertama, bangun jaringan acak dengan:

julia> using LightGraphs

julia> N_ = 1000 ;

julia> network  = LightGraphs.DiGraph(N_)
{1000, 0} directed simple Int64 graph

julia> using Distributions

julia> for i in 1:N_
           add_edge!(network, sample(1:N_,2)...)
       end

julia> net = weakly_connected_components(network)[1]

julia> temp_net,vmap = induced_subgraph(network, net)
({814, 978} directed simple Int64 graph, [1, 3, 4, 5, 6, 9, 10, 11, 12, 13  …  989, 990, 991, 993, 995, 996, 997, 998, 999, 1000])

Dan sekarang, kami memiliki:

julia> length(vertices(temp_net))
814

julia> invertices = union((edges(temp_net).adj[i] for i in vertices(temp_net))...);

julia> outvertices = [i for i in vertices(temp_net) if !isempty(edges(temp_net).adj[i])] ;

julia> length(union(invertices,outvertices))
814

Jadi semua 814 simpul mempunyai sisi dari, atau ke simpul tersebut (atau keduanya) dan merupakan bagian dari komponen yang terhubung lemah.

person Dan Getz    schedule 01.06.2017

arrow_upward
5
arrow_downward

Selain apa yang dikatakan @ dan-getz, saya harus memohon kepada Anda untuk tidak mengakses struktur bidang data internal apa pun - kami memiliki pengakses untuk segala sesuatu yang "publik". Secara khusus, edges(temp_net).adj tidak dijamin tersedia. Saat ini sama dengan fadj(g), daftar kedekatan ke depan dari g, untuk grafik berarah dan tidak berarah, namun tidak dimaksudkan untuk digunakan kecuali untuk membantu mempertahankan status iterasi tepi.

Jika Anda menggunakan .adj, kode Anda akan rusak tanpa peringatan di beberapa titik.

person sbromberger    schedule 07.06.2017