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

**URL:** <https://discourse.julialang.org/t/what-is-the-optimised-way-to-find-connected-components-in-a-graph-with-edge-weights-greater-than-zero/85902>\
**Category:** Graphs\
**Tags:** question, graphs\
**Created:** [August 18, 2022, 2:41am UTC](https://discourse.julialang.org/t/what-is-the-optimised-way-to-find-connected-components-in-a-graph-with-edge-weights-greater-than-zero/85902 "2022-08-18T02:41:01Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![Manu\_Francis](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/manu_francis/32/10010_2.png) [@Manu\_Francis](https://discourse.julialang.org/u/Manu_Francis)\
**Post date:** [August 18, 2022, 2:41am UTC](https://discourse.julialang.org/t/what-is-the-optimised-way-to-find-connected-components-in-a-graph-with-edge-weights-greater-than-zero/85902/1 "2022-08-18T02:41:01Z")

</div>

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.

```julia
  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?

---

<div class="post-metadata">

**Author:** ![jd-foster](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jd-foster/32/35824_2.png) [@jd-foster](https://discourse.julialang.org/u/jd-foster)\
**Post date:** [August 18, 2022, 4:23am UTC](https://discourse.julialang.org/t/what-is-the-optimised-way-to-find-connected-components-in-a-graph-with-edge-weights-greater-than-zero/85902/2 "2022-08-18T04:23:19Z")

</div>

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

```julia
cc2 = cc[length.(cc) .> 1]

```

---

<div class="post-metadata">

**Author:** ![Manu\_Francis](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/manu_francis/32/10010_2.png) [@Manu\_Francis](https://discourse.julialang.org/u/Manu_Francis)\
**Post date:** [August 18, 2022, 4:29am UTC](https://discourse.julialang.org/t/what-is-the-optimised-way-to-find-connected-components-in-a-graph-with-edge-weights-greater-than-zero/85902/3 "2022-08-18T04:29:43Z")

</div>

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

```julia
  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

```julia
[[1]]

```

---

<div class="post-metadata">

**Author:** ![jd-foster](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jd-foster/32/35824_2.png) [@jd-foster](https://discourse.julialang.org/u/jd-foster)\
**Post date:** [August 18, 2022, 4:40am UTC](https://discourse.julialang.org/t/what-is-the-optimised-way-to-find-connected-components-in-a-graph-with-edge-weights-greater-than-zero/85902/4 "2022-08-18T04:40:34Z")

</div>

Capture this case with:

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

```

i.e.

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

```

---

<div class="post-metadata">

**Author:** ![Manu\_Francis](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/manu_francis/32/10010_2.png) [@Manu\_Francis](https://discourse.julialang.org/u/Manu_Francis)\
**Post date:** [August 18, 2022, 5:37am UTC](https://discourse.julialang.org/t/what-is-the-optimised-way-to-find-connected-components-in-a-graph-with-edge-weights-greater-than-zero/85902/5 "2022-08-18T05:37:16Z")

</div>

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