1

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 包测试似乎正在工作。

4

2 回答 2

5

除了@dan-getz 所说的，我必须恳求您不要访问结构的任何内部数据字段——我们对所有“公共”的东西都有访问器。具体来说，edges(temp_net).adj不保证可用。对于有向图和无向图，它目前与fadj(g)的前向邻接列表相同g，但它不打算用于帮助保持边缘迭代状态。

如果您使用.adj，您的代码将在某些时候在没有警告的情况下对您造成影响。

于 2017-06-07T23:56:18.497 回答
2

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 个顶点要么具有来自它们的边，要么具有它们（或两者）的边，并且是弱连接组件的一部分。

于 2017-06-01T14:37:02.973 回答