朱莉娅 LightGraphs weakly_connected_components

Question

julia LightGraphs 中的 weakly_connected_components 是不是应该提供连通分量，如果有向图变成无向图，那么每个分量都应该连通？我已经试过了，但我没有收到这样的组件？作为一个例子，我在政治博客数据上尝试了这个作为无向网络

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 包测试似乎有效。

Answer 1

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 个顶点都具有来自或指向它们（或两者）的边，并且是弱连通分量的一部分。

Answer 2

除了@dan-getz 所说的之外，我必须恳请您不要访问结构的任何内部数据字段 - 我们拥有 "public" 的所有内容的访问器。具体来说，edges(temp_net).adj 不保证可用。它目前与 fadj(g) 相同，即 g 的前向邻接列表，适用于有向图和无向图，但除了帮助保持边迭代状态外，不打算使用它。

如果您使用 .adj，您的代码有时会在没有警告的情况下中断。

朱莉娅 LightGraphs weakly_connected_components

Julia LightGraphs weakly_connected_components

directed-graph

julia

lightgraphs