What is the optimised way to find connected components in a graph with edge weights greater than zero?

Specific Domains Graphs
,
1

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.

  using Graphs
  using SimpleWeightedGraphs
  
  len = 105_000
  g = SimpleWeightedGraph(len)
  
  idxs = []
  
  for i in 1:25000
      x = rand(1:len)
      y = rand(1:len)
      push!(idxs, x,y)
      g.weights[x,y] = 1.0
      g.weights[y,x] = 1.0
  end
  unique!(idxs)
  
  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?

2

Hi Manu, Can you filter based on length of connected component? i.e. try:

cc2 = cc[length.(cc) .> 1]
3

@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.

For example,

  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

[[1]]
4

Capture this case with:

intersect(cc[length.(cc) .== 1],[[i] for i in idxs])

i.e.

result = cc[length.(cc) .> 1] ∪ ( cc[length.(cc) .== 1] ∩ [[i] for i in idxs])
1 Like
5

@jd-foster : Thanks a lot. Your solution is really helpful

1 Like