Hi I am trying to find the connected components of a simple weighted graph with edge weights having a value greater than zero as below.
len = 105_000
g = SimpleWeightedGraph(len)
idxs = 
for i in 1:25000
x = rand(1:len)
y = rand(1:len)
g.weights[x,y] = 1.0
g.weights[y,x] = 1.0
cc = connected_components(g);
@time filter(c->(any(x->(x ∈ c), idxs)), cc)
The last line filter out connected components with edge weight greater than zero. But this is very expensive in terms of computational time and resource usage for huge graphs. Is there any optimised way to do the same?
Hi Manu, Can you filter based on length of connected component? i.e. try:
cc2 = cc[length.(cc) .> 1]
@jd-foster: Thanks for your reply.
But there is chance for weight of edge that points to same node can be greater than one and that node doesn’t connect to any other nodes.
g = SimpleWeightedGraph(5)
g.weights[1,1] = 1.0
cc = connected_components(g)
Then method that you have suggested will not work, because I expect result something like
Capture this case with:
intersect(cc[length.(cc) .== 1],[[i] for i in idxs])
result = cc[length.(cc) .> 1] ∪ ( cc[length.(cc) .== 1] ∩ [[i] for i in idxs])
@jd-foster : Thanks a lot. Your solution is really helpful