# Find connected components?

**URL:** <https://discuss.dgraph.io/t/find-connected-components/5245>\
**Category:** Users\
**Created:** [October 16, 2019, 12:32pm UTC](https://discuss.dgraph.io/t/find-connected-components/5245 "2019-10-16T12:32:20Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![timnon](https://avatars.discourse-cdn.com/v4/letter/t/b9e5f3/32.png) [@timnon](https://discuss.dgraph.io/u/timnon)\
**Post date:** [October 16, 2019, 12:32pm UTC](https://discuss.dgraph.io/t/find-connected-components/5245/1 "2019-10-16T12:32:21Z")

</div>

How to find connected components?

i found this closed issue, but the answer is not very helpful: [Finding connected components in graph](http://discuss.hypermode.com/t/finding-connected-components-in-graph/3838)

Thanks!!!

P.S. To be precise, the following graph has two components, how to return them?:

```auto
{
    set {
     _:node_1 <code> "node_1" .
     _:node_1 <dgraph.type> "node" .     
     _:node_2 <code> "node_2" .
     _:node_2 <dgraph.type> "node" .  
     _:node_3 <code> "node_3" .
     _:node_3 <dgraph.type> "node" .  
     _:node_4 <code> "node_4" . 
     _:node_4 <dgraph.type> "node" . 
       
     _:node_1 <neighbor> _:node_2 .
     _:node_2 <neighbor> _:node_1 .
     _:node_3 <neighbor> _:node_4 .
     _:node_4 <neighbor> _:node_3 .
    }
}

```

---

<div class="post-metadata">

**Author:** ![MichelDiz](https://yyz1.discourse-cdn.com/flex007/user_avatar/discuss.dgraph.io/micheldiz/32/11873_2.png) [@MichelDiz](https://discuss.dgraph.io/u/MichelDiz)\
**Post date:** [October 16, 2019, 9:10pm UTC](https://discuss.dgraph.io/t/find-connected-components/5245/2 "2019-10-16T21:10:36Z")

</div>

> [@timnon](#):
>
> How to find connected components?

What is the concept of components in this sample?

```auto
{
  q(func: type(node)) @filter(has(neighbor)){
    uid
    name 
    neighbor {
        uid
        name 
        neighbor
      }
  }
}

```

```auto
{
  "data": {
    "q": [
      {
        "uid": "0x2738",
        "name": "node_1",
        "neighbor": [
          {
            "uid": "0x2739",
            "name": "node_2"
          }
        ]
      },
      {
        "uid": "0x2739",
        "name": "node_2",
        "neighbor": [
          {
            "uid": "0x2738",
            "name": "node_1"
          }
        ]
      },
      {
        "uid": "0x273a",
        "name": "node_3",
        "neighbor": [
          {
            "uid": "0x273b",
            "name": "node_4"
          }
        ]
      },
      {
        "uid": "0x273b",
        "name": "node_4",
        "neighbor": [
          {
            "uid": "0x273a",
            "name": "node_3"
          }
        ]
      }
    ]
  }
}

```

---

<div class="post-metadata">

**Author:** ![timnon](https://avatars.discourse-cdn.com/v4/letter/t/b9e5f3/32.png) [@timnon](https://discuss.dgraph.io/u/timnon)\
**Post date:** [October 17, 2019, 5:16am UTC](https://discuss.dgraph.io/t/find-connected-components/5245/3 "2019-10-17T05:16:20Z")

</div>

Hi, thanks for the feedback.

In the example above, there are two connected components, one consisting of `node_1` and `node_2`, and one consisting of `node_3` and `node_4` (in the style of [Component (graph theory) - Wikipedia](https://en.wikipedia.org/wiki/Component_(graph_theory)). So ideally, it would be nice to have a query that returns sth like:

```auto
[
[node_1, node_2], 
[node_3, node_4] 
]

```

It is possible to return the connected component that contains e.g. `node_1` by running:

```auto
{
  q(func: eq(code,node_1), first: 100) @recurse @normalize{
  N as neighbor
  }

  component(func: uid(N)){
  code
  }
}

```

So the only way i see is to iteratively run this query for each node which has not been found in a component yet. This will result in a number of queries proportional to the number of nodes in the graph (quite infeasible sometimes). So is it possible to return all components at once? with pagination to iteratively fetch them.

---

<div class="post-metadata">

**Author:** ![timnon](https://avatars.discourse-cdn.com/v4/letter/t/b9e5f3/32.png) [@timnon](https://discuss.dgraph.io/u/timnon)\
**Post date:** [October 17, 2019, 5:22am UTC](https://discuss.dgraph.io/t/find-connected-components/5245/4 "2019-10-17T05:22:54Z")

</div>

P.S. just realized that `name` has a special meaning and is not indexed. In my local examples i am using `code` to label a node, so updated my examples above by replacing `name` by `code`

---

<div class="post-metadata">

**Author:** ![MichelDiz](https://yyz1.discourse-cdn.com/flex007/user_avatar/discuss.dgraph.io/micheldiz/32/11873_2.png) [@MichelDiz](https://discuss.dgraph.io/u/MichelDiz)\
**Post date:** [October 18, 2019, 12:27am UTC](https://discuss.dgraph.io/t/find-connected-components/5245/5 "2019-10-18T00:27:42Z")

</div>

If I slightly change your dataset, it changes the whole meaning?

```auto
<code>: string .
<neighbor>: [uid] @reverse . //we need reverse

```

```auto
{
    set {
     _:node_1 <code> "node_1" .
     _:node_1 <dgraph.type> "node" .
     _:node_2 <code> "node_2" .
     _:node_2 <dgraph.type> "node" .  
     _:node_3 <code> "node_3" .
     _:node_3 <dgraph.type> "node" .
     _:node_4 <code> "node_4" .
     _:node_4 <dgraph.type> "node" .
       
     _:node_1 <neighbor> _:node_2 .
   # _:node_2 <neighborConfirm> _:node_1 . #change this pred or remove it
     _:node_3 <neighbor> _:node_4 .
   # _:node_4 <neighborConfirm> _:node_3 . #change this pred or remove it
    }
}

```

## Reach all nodes

```auto
{
  q(func: type(node)) 
    {
    uid
    code 
    neighbor {
        uid
        code 
        neighbor
      }
	~neighbor { #or use the the pred "neighborConfirm"
        uid
        code 
        neighbor
      }
  }
}

```

## Filter the ones that is reversed

```auto
{
  q(func: type(node)) @filter(not has(~neighbor))
    {
    uid
    code 
    neighbor {
        uid
        code 
        neighbor
      }
  }
}

```

if you wanna use `recurse`

```auto
{
 q(func: type(node)) @filter(not has(~neighbor)) @recurse(depth: 2, loop: true)
    {
    uid
    code
    neighbor
  }
}

```

---

<div class="post-metadata">

**Author:** ![timnon](https://avatars.discourse-cdn.com/v4/letter/t/b9e5f3/32.png) [@timnon](https://discuss.dgraph.io/u/timnon)\
**Post date:** [October 18, 2019, 6:32am UTC](https://discuss.dgraph.io/t/find-connected-components/5245/6 "2019-10-18T06:32:27Z")

</div>

Using @recurse as in `<neighbor>: [uid] @reverse . ` is nice syntactic sugar (good to remember), but doesnt change the problem. If i run e.g.

```auto
{
  q(func: type(node)) @recurse
    {
    name
    neighbor
    }
}

```

(Slight modification of your queries above), we get:

```auto
{
  "data": {
    "q": [
      {
        "name": "node_1",
        "neighbor": [
          {
            "name": "node_2"
          }
        ]
      },
      {
        "name": "node_2"
      },
      {
        "name": "node_3",
        "neighbor": [
          {
            "name": "node_4"
          }
        ]
      },
      {
        "name": "node_4"
      },
      {
        "name": "node_3",
        "neighbor": [
          {
            "name": "node_4"
          }
        ]
      },
      {
        "name": "node_4",
        "neighbor": [
          {
            "name": "node_3"
          }
        ]
      },
      {
        "name": "node_1",
        "neighbor": [
          {
            "name": "node_2"
          }
        ]
      },
      {
        "name": "node_2",
        "neighbor": [
          {
            "name": "node_1"
          }
        ]
      },
      {
        "name": "node_2",
        "neighbor": [
          {
            "name": "node_1"
          }
        ]
      },
      {
        "name": "node_3",
        "neighbor": [
          {
            "name": "node_4"
          }
        ]
      },
      {
        "name": "node_4",
        "neighbor": [
          {
            "name": "node_3"
          }
        ]
      },
      {
        "name": "node_1",
        "neighbor": [
          {
            "name": "node_2"
          }
        ]
      }
    ]
  },
  "extensions": {
    "server_latency": {
      "parsing_ns": 10169,
      "processing_ns": 5402004,
      "encoding_ns": 42478,
      "assign_timestamp_ns": 534517
    },
    "txn": {
      "start_ts": 30370384
    }
  }
}

```

Note that every connected component appears many times, e.g. for the connected component `[node_1,node_2]`:

```auto
{
        "name": "node_1",
        "neighbor": [
          {
            "name": "node_2"
          }
        ]
      }

```

and

```auto
      {
        "name": "node_2",
        "neighbor": [
          {
            "name": "node_1"
          }
        ]
      }

```

Now imagine a connected component consisting of 100’000 nodes. Returning this component should be no problem, but if we return this component more than 100’000 times, we have a problem. So how can we ensure that each connected component is only listed once in the query result??

Sorry, i am mixing up `code` and `name` during these queries, just think about it as some label of the nodes.

---

<div class="post-metadata">

**Author:** ![MichelDiz](https://yyz1.discourse-cdn.com/flex007/user_avatar/discuss.dgraph.io/micheldiz/32/11873_2.png) [@MichelDiz](https://discuss.dgraph.io/u/MichelDiz)\
**Post date:** [October 18, 2019, 3:42pm UTC](https://discuss.dgraph.io/t/find-connected-components/5245/7 "2019-10-18T15:42:06Z")

</div>

> [@timnon](#):
>
> If i run e.g.

Not sure what you mean, you can’t get anything treated without applying filters or some param strategy.

> [@timnon](#):
>
> (Slight modification of your queries above), we get:

Which modifications?

> [@timnon](#):
>
> So how can we ensure that each connected component is only listed once in the query result??

If you filter it by reverse is the fastest one.

## This query

```auto
{
  q(func: type(node)) @filter(not has(~neighbor))
    {
    uid
    code 
    neighbor {
        uid
        code 
        neighbor
      }
  }
}

```

## Results

```auto
{
  "data": {
    "q": [
      {
        "uid": "0x2760",
        "code": "node_1",
        "neighbor": [
          {
            "uid": "0x2761",
            "code": "node_2"
          }
        ]
      },
      {
        "uid": "0x2762",
        "code": "node_3",
        "neighbor": [
          {
            "uid": "0x2763",
            "code": "node_4"
          }
        ]
      }
    ]
  }
}

```

---

<div class="post-metadata">

**Author:** ![timnon](https://avatars.discourse-cdn.com/v4/letter/t/b9e5f3/32.png) [@timnon](https://discuss.dgraph.io/u/timnon)\
**Post date:** [October 21, 2019, 12:51pm UTC](https://discuss.dgraph.io/t/find-connected-components/5245/8 "2019-10-21T12:51:34Z")

</div>

Your query only works for the case that each component has size 2, what about the following case with two components of size 4 each? (and similar cases with even larger components):

```auto
{
    set {
     _:node_1 <code> "node_1" .
     _:node_1 <dgraph.type> "node" .
     _:node_2 <code> "node_2" .
     _:node_2 <dgraph.type> "node" .
     _:node_3 <code> "node_3" .
     _:node_3 <dgraph.type> "node" .
     _:node_4 <code> "node_4" .
     _:node_4 <dgraph.type> "node" .
     _:node_5 <code> "node_5" .
     _:node_5 <dgraph.type> "node" .
     _:node_6 <code> "node_6" .
     _:node_6 <dgraph.type> "node" .
     _:node_7 <code> "node_7" .
     _:node_7 <dgraph.type> "node" .
     _:node_8 <code> "node_8" .
     _:node_8 <dgraph.type> "node" .

     _:node_1 <neighbor> _:node_2 .
     _:node_2 <neighbor> _:node_1 .
     _:node_2 <neighbor> _:node_3 .
     _:node_3 <neighbor> _:node_2 .
     _:node_3 <neighbor> _:node_4 .
     _:node_4 <neighbor> _:node_3 .

     _:node_5 <neighbor> _:node_6 .
     _:node_6 <neighbor> _:node_5 .
     _:node_6 <neighbor> _:node_7 .
     _:node_7 <neighbor> _:node_6 .
     _:node_7 <neighbor> _:node_8 .
     _:node_8 <neighbor> _:node_7 .
    }
}

```

---

<div class="post-metadata">

**Author:** ![system](https://canada1.discourse-cdn.com/flex007/uploads/dgraph/original/2X/2/2b38fdece2abe5814f2e51bee69d1e67fc304b0a.png) [@system](https://discuss.dgraph.io/u/system)\
**Post date:** [November 20, 2019, 1:05pm UTC](https://discuss.dgraph.io/t/find-connected-components/5245/9 "2019-11-20T13:05:47Z")

</div>

This topic was automatically closed 30 days after the last reply. New replies are no longer allowed.