Isn't it true that the weakly_connected_components in julia LightGraphs should provide connected components where if The DiGraph is turned into an undirected graph, then each component should be connected? I have tried this and I do not receive such components? As an example I have tried this on the political blogs data as an undirected network
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)
and after getting the largest weakly connected component, I see the following:
isempty([i for i in vertices(temp_net) if isempty(edges(temp_net).adj[i])])
julia>false
which signigies some nodes have no incoming or outgoing edges. What can be the problem? I am using the latest release 6, but the LightGraphs package tests seem to be working.
The TL;DR answer is that edges(temp_net).adj[i]
contains only the vertices i
connects to, and not those connecting to i
. And some vertices have no incoming edges.
The longer version, is the following which shows temp_net
in a randomly generated network and assigned as in the question is indeed weakly-connected. First building a random network with:
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])
And, now, we have:
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
Thus all 814 vertices either have edges from, or to them (or both) and are part of the weakly connected component.