Julia LightGraphs weakly_connected_components

Не правда ли, что weakly_connected_components в julia LightGraphs должны предоставлять связанные компоненты, где, если DiGraph превратить в неориентированный граф, то каждый компонент должен быть связанным? Я пробовал это, и я не получаю такие компоненты? В качестве примера я попробовал это на данных политических блогов в качестве ненаправленной сети.

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)

и после получения наибольшей слабо связанной компоненты я вижу следующее:

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

julia>false

что означает, что некоторые узлы не имеют ни входящих, ни исходящих ребер. В чем может быть проблема? Я использую последнюю версию 6, но тесты пакета LightGraphs, похоже, работают.


julia directed-graph lightgraphs
person A.Yazdiha    schedule 01.06.2017    source источник

Ответы (2)


arrow_upward
2
arrow_downward

Ответ TL; DR заключается в том, что edges(temp_net).adj[i] содержит только вершины, к которым подключается i, а не те, которые соединяются с i. А некоторые вершины не имеют входящих ребер.

Ниже приведена более длинная версия, которая показывает temp_net в случайно сгенерированной сети и назначается, поскольку в вопросе действительно слабо связано. Сначала создайте случайную сеть с:

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])

И, теперь, у нас есть:

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

Таким образом, все 814 вершин имеют ребра либо от них, либо к ним (или и то, и другое) и являются частью слабосвязной компоненты.

person Dan Getz    schedule 01.06.2017

arrow_upward
5
arrow_downward

В дополнение к тому, что сказал @dan-getz, я должен умолять вас не обращаться к каким-либо внутренним полям данных структур - у нас есть средства доступа для всего, что является «общедоступным». В частности, наличие edges(temp_net).adj не гарантируется. В настоящее время это то же самое, что и fadj(g), прямой список смежности g, как для ориентированных, так и для неориентированных графов, но он не предназначен для использования, кроме как для сохранения состояния итерации края.

Если вы используете .adj, в какой-то момент ваш код сломается без предупреждения.

person sbromberger    schedule 07.06.2017