# Find paths between one node and a group of nodes

**URL:** <https://discuss.dgraph.io/t/find-paths-between-one-node-and-a-group-of-nodes/12098>\
**Category:** Dgraph\
**Tags:** kind:question\
**Created:** [December 28, 2020, 12:33pm UTC](https://discuss.dgraph.io/t/find-paths-between-one-node-and-a-group-of-nodes/12098 "2020-12-28T12:33:18Z")\
**Posts on this page:** 15\
**Page:** 1

<div class="post-metadata">

**Author:** ![johan-l](https://yyz1.discourse-cdn.com/flex007/user_avatar/discuss.dgraph.io/johan-l/32/5824_2.png) [@johan-l](https://discuss.dgraph.io/u/johan-l)\
**Post date:** [December 28, 2020, 12:33pm UTC](https://discuss.dgraph.io/t/find-paths-between-one-node-and-a-group-of-nodes/12098/1 "2020-12-28T12:33:18Z")

</div>

I have a particularly difficult issue that I wonder if DGraph can solve easily. I understand that it supports lookup on a path between two nodes ([How to find relationship between two nodes?](http://discuss.hypermode.com/t/how-to-find-relationship-between-two-nodes/7495)). But I’m interested in knowing **if there is a path** between **one particular node and a GROUP of nodes**. This group will be selected based on a filter, which could be part of the query or done before the query.

Is this something the database supports, or am I forced to run multiple node-to-node queries?

I understand that this is a very hard problem to solve, and requires much power if it’s purely algorithmic in nature. I’m hoping that DGraph has some modifications done to speed up queries like this. Even if it doesn’t do you have any suggestions on ways to store or link the data to support quicker query speed for tasks like this?

---

<div class="post-metadata">

**Author:** ![Anurag](https://yyz1.discourse-cdn.com/flex007/user_avatar/discuss.dgraph.io/anurag/32/2599_2.png) [@Anurag](https://discuss.dgraph.io/u/Anurag)\
**Post date:** [December 28, 2020, 12:41pm UTC](https://discuss.dgraph.io/t/find-paths-between-one-node-and-a-group-of-nodes/12098/2 "2020-12-28T12:41:36Z")

</div>

Hi @johan-l Is it possible for you to link `group of nodes` to another dummy node which you create in the data? Then you would be able to run [`shortest path` queries](https://dgraph.io/docs/query-language/kshortest-path-quries/) out-of-the box from `node-1` to `dummy-node`. The path would exist only via the group of nodes which you are interested in.

---

<div class="post-metadata">

**Author:** ![johan-l](https://yyz1.discourse-cdn.com/flex007/user_avatar/discuss.dgraph.io/johan-l/32/5824_2.png) [@johan-l](https://discuss.dgraph.io/u/johan-l)\
**Post date:** [December 28, 2020, 3:52pm UTC](https://discuss.dgraph.io/t/find-paths-between-one-node-and-a-group-of-nodes/12098/3 "2020-12-28T15:52:51Z")

</div>

Hi, thanks for your answer @Anurag!

I’ve had that as a possible solution, although it would only solve part of the issue unless I pollute the graph with tons of these nodes. And at that point I’m not sure a graph database is the correct way to go.

Imagine my graph is a collection of package shipments, with each node being either a processing or position of the package. At any point the package can be split up and repackaged (processed) and branch out to multiple paths. Then I basically want to ask “has this package or parts of it been delivered to any of the stations in Paris, if so which ones?”

Doing the group thing makes sense, since I would be able to have a graph per city to quickly find out an estimate. But I would still have to run a query to find out which places in particular. If I’m thinking correctly.

Have you had a similar problem before?

---

<div class="post-metadata">

**Author:** ![Anurag](https://yyz1.discourse-cdn.com/flex007/user_avatar/discuss.dgraph.io/anurag/32/2599_2.png) [@Anurag](https://discuss.dgraph.io/u/Anurag)\
**Post date:** [December 30, 2020, 11:07am UTC](https://discuss.dgraph.io/t/find-paths-between-one-node-and-a-group-of-nodes/12098/4 "2020-12-30T11:07:53Z")

</div>

I tested below snippet where `P2` expands to more than one node, but it throws `variable(P2) should only expand to 1 uid` therefore the path to a group of nodes is not supported currently.

```auto
path as shortest(from: uid(P1), to: uid(P2)) {
        friend
    }

```

> [@johan-l](#):
>
> But I would still have to run a query to find out which places in particular. If I’m thinking correctly.

You would not have to run more queries to find which places, because the places will be in your path. You would need to parse the path extracted to get the relevant stations to which your package has been delivered.

For example if your dummy node is `0x17` then it would have two paths to it via `0x13` and 0x15`.

```auto
  "_path_": [
    {
      "_weight_": 2.0, 
      "uid": "0x17", 
      "friend": {
        "uid": "0x13", 
        "friend": {
          "uid": "0x14"
        }
      }
    }, 
    {
      "_weight_": 2.0, 
      "uid": "0x17", 
      "friend": {
        "uid": "0x15", 
        "friend": {
          "uid": "0x14"
        }
      }
    }
  ]

```

---

<div class="post-metadata">

**Author:** ![johan-l](https://yyz1.discourse-cdn.com/flex007/user_avatar/discuss.dgraph.io/johan-l/32/5824_2.png) [@johan-l](https://discuss.dgraph.io/u/johan-l)\
**Post date:** [December 30, 2020, 2:53pm UTC](https://discuss.dgraph.io/t/find-paths-between-one-node-and-a-group-of-nodes/12098/5 "2020-12-30T14:53:35Z")

</div>

Sounds great, but if I understood it correctly it would still just map out a single (shortest) path between two nodes since a group of nodes in `P2` isn’t supported yet.

I really need to have more than one “end node” since the packages in question can be split up along the way (imagine a shipment of 1000 screws that gets packaged into batches of 10 and resent to multiple customers). Your example is great, but I would have to either run it multiple times for each end node, or somehow abstract the path into something that’s easier to query.

Unless DGraph supports another query style against multiple nodes? For my example I wouldn’t need any PATH in return, a simple “yes/no” would be enough for each node in `P2`.

Looking forward to your input. Thanks again for the swift response time!

Happy new year 🎉

---

<div class="post-metadata">

**Author:** ![Anurag](https://yyz1.discourse-cdn.com/flex007/user_avatar/discuss.dgraph.io/anurag/32/2599_2.png) [@Anurag](https://discuss.dgraph.io/u/Anurag)\
**Post date:** [December 30, 2020, 4:55pm UTC](https://discuss.dgraph.io/t/find-paths-between-one-node-and-a-group-of-nodes/12098/6 "2020-12-30T16:55:26Z")

</div>

Suppose your group of nodes have nodes `A-H`. If you create a dummy node and link it to each node in `P2` and do a query

```auto
path as shortest(from: uid(src_node), to: uid(dummy_node), numpaths: 8 ) {
        link
    }

```

It will return `4` paths (src - A - dummy\_node; src - C - dummy\_node; src - E - dummy\_node; src - F - dummy\_node).

And you can find out which nodes (from the group P2) it actually went to via `_path_` key in the response.  
An important point is to give `numpath=size(P2)` so that it continues to find all the paths, and you can retrieve all the nodes visited from the response.

If your `P2` nodes are inter-connected then you can give an even higher number to `numpaths` to account for paths like `src - A - B - dummy node`. This is a hacky way to make it visit all nodes even if it has found the shortest path already. Your performance would suffer but you would be making only one query.

 ![Screenshot1609346903](https://canada1.discourse-cdn.com/flex007/uploads/dgraph/original/2X/0/01fc3386006a04e294ff1219571afb9d748cf922.png)

---

<div class="post-metadata">

**Author:** ![johan-l](https://yyz1.discourse-cdn.com/flex007/user_avatar/discuss.dgraph.io/johan-l/32/5824_2.png) [@johan-l](https://discuss.dgraph.io/u/johan-l)\
**Post date:** [January 1, 2021, 3:16pm UTC](https://discuss.dgraph.io/t/find-paths-between-one-node-and-a-group-of-nodes/12098/7 "2021-01-01T15:16:53Z")

</div>

Interesting hack! It would be interesting to compare the performance of a solution like this to a hacky solution in a traditional relational database.

The number would only grow with time and the numpath could quickly reach into the 100k. Do you have any idea how performance heavy that query is? I haven’t used DGraph before so I have a hard time estimating it. I could probably improve the performance a bit by filtering out some nodes (eg on date)

I also assume there is no pagination possible here? If there is, one solution would be to make use of that to save some performance

---

<div class="post-metadata">

**Author:** ![johan-l](https://yyz1.discourse-cdn.com/flex007/user_avatar/discuss.dgraph.io/johan-l/32/5824_2.png) [@johan-l](https://discuss.dgraph.io/u/johan-l)\
**Post date:** [January 5, 2021, 10:53am UTC](https://discuss.dgraph.io/t/find-paths-between-one-node-and-a-group-of-nodes/12098/8 "2021-01-05T10:53:06Z")

</div>

Hi again @Anurag

I’ve explored this further by setting Dgraph up locally and filling it up with some data, so I got some more information and knowledge now.

I’ve encountered a problem. Below you’ll see an image of an example query, let me explain the issue.

To get this Graph I’ve queried for the shortest path between the nodes inside of the Green Circles.  
The issue is that in the real world I’d want to query for the paths between the nodes inside of the Red Circles. But when I do that (even with numpath: 2) all the nodes striked with a purple line is removed from the query, since it’s a circular path. But without those nodes I’m unable to determine if the removed node is in the path or not.

 ![Screenshot 2021-01-05 at 11.47.33](https://canada1.discourse-cdn.com/flex007/uploads/dgraph/original/2X/a/a05f016f010b211970ee3738025a3db639c143c0.jpeg)

Your example works because there is no circular dependency.

From this thread ([Identify all the paths between two nodes - #3 by AlBar](http://discuss.hypermode.com/t/identify-all-the-paths-between-two-nodes/1482/3)) I gather that this isn’t a feature that’s supported yet. Or did I query the data wrongly?

For reference here is the query that I’ve been using:

```auto
{
 	path as shortest(from: <SOURCE_UID>, to: <TARGET_UID>, numpaths: 2) {
  	~origins
    ~assembledFrom
    ~processedFrom
    company
 	}
 	path(func: uid(path)) {
    name
    number
    assembledFrom {
      name: number
    }
    processedFrom {
      name: number
    }
    origins {
      name: number
    }
    company {
      name
    }
 	}
}

```

One solution would be to fetch the entire tree for a specific node as a base. From what I’ve gathered this should be possible with the recurse query. But I’m not getting it to work. I’m either just getting a single node as a response (QUERY #1) or an error `recurse queries require that all predicates are specified in one level` (QUERY #2). The [documentation](https://dgraph.io/docs/query-language/recurse-query/) isn’t of much help here unfortunately. It looks like you’ve added support for it from this [thread](http://discuss.hypermode.com/t/recursive-queries/1306/5), maybe I’m not using it correctly? 🙂

QUERY #1:

```auto
{
  tree(func: eq(number, "3429d692")) @recurse(depth: 12992203, loop: true) {
    name: number
    company
    processedFrom
    assembledFrom
    origins
  }
}

```

QUERY 2:

```auto
{
  tree(func: eq(number, "3429d692")) @recurse(depth: 12992203, loop: true) {
    name: number
    company {
      name 
    }
    processedFrom {
      number 
    }
    assembledFrom {
      number 
    }
    origins {
      number 
    }
  }
}

```

---

<div class="post-metadata">

**Author:** ![johan-l](https://yyz1.discourse-cdn.com/flex007/user_avatar/discuss.dgraph.io/johan-l/32/5824_2.png) [@johan-l](https://discuss.dgraph.io/u/johan-l)\
**Post date:** [January 5, 2021, 1:23pm UTC](https://discuss.dgraph.io/t/find-paths-between-one-node-and-a-group-of-nodes/12098/9 "2021-01-05T13:23:11Z")

</div>

I’m making a new comment, since the other one is growing large… But first: **IGNORE THE RECURSE ISSUES I HAD IN THE COMMENT ABOVE**.

The issues were caused by not following the edges direction correctly, so I solved it by making a reverse lookup.

```auto
{
  q(func: eq(number, "3429d692")) @recurse(loop: true, depth: 1000) {
    number 
    name
    ~origins
    ~assembledFrom
    ~processedFrom
    company
  }
}

```

 ![Screenshot 2021-01-05 at 14.13.56](https://canada1.discourse-cdn.com/flex007/uploads/dgraph/original/2X/6/66f0965badf5ad518423299854a1d8c769f49dc6.png)

In the picture above I’ve placed the nodes and edges according to the previous picture I posted. This query seems to satisfy what I’m looking for. Although it would return a lot of extra data since it’s returning the entire tree, when I’m actually just interested in **the entire tree leading to a specific end node**. I’m still very happy to get some help in this issue.

I have a problem with the query still, it seems like 4 nodes are missing for 2 different nodes. They are marked as red circles in the image. These seem to be missing because of the way I’m storing the directions of the edges and querying for it. I’m going to look over my dataset and make sure it’s all correct before going further.

EDIT: Got the Recursive query working. It would still be great if it’s possible to get DGraph filter out all paths that’s not of interest, worst case I’ll have to fetch the entire subtree for a node and filter out that myself 👍

---

<div class="post-metadata">

**Author:** ![Anurag](https://yyz1.discourse-cdn.com/flex007/user_avatar/discuss.dgraph.io/anurag/32/2599_2.png) [@Anurag](https://discuss.dgraph.io/u/Anurag)\
**Post date:** [January 8, 2021, 10:20pm UTC](https://discuss.dgraph.io/t/find-paths-between-one-node-and-a-group-of-nodes/12098/10 "2021-01-08T22:20:57Z")

</div>

Hi @johan-l,  
Thanks for your questions. I will try to answer them below.

> [@johan-l](#):
>
> Do you have any idea how performance heavy that query is? I haven’t used DGraph before so I have a hard time estimating it.

The query which I suggested will be computation intensive. Internally it will try to `either find the number off paths you asked for` or `continue until it visits all the nodes in the process`. See [runKshortestPaths](https://github.com/dgraph-io/dgraph/blob/b05fb930ffdbbb2f849d73a1e57bc8bd7575255d/query/shortest.go#L296).

> [@johan-l](#):
>
> I also assume there is no pagination possible here? If there is, one solution would be to make use of that to save some performance

There are two shortest path functions implemented internally: [shortestPath](https://github.com/dgraph-io/dgraph/blob/b05fb930ffdbbb2f849d73a1e57bc8bd7575255d/query/shortest.go#L465) and [runKshortestPaths](https://github.com/dgraph-io/dgraph/blob/b05fb930ffdbbb2f849d73a1e57bc8bd7575255d/query/shortest.go#L296). The former returns one path and the latter returns (or tries to return) total `numPaths` in ascending order of the distance . I do know understand how would `pagination` work here.

---

<div class="post-metadata">

**Author:** ![Anurag](https://yyz1.discourse-cdn.com/flex007/user_avatar/discuss.dgraph.io/anurag/32/2599_2.png) [@Anurag](https://discuss.dgraph.io/u/Anurag)\
**Post date:** [January 8, 2021, 10:30pm UTC](https://discuss.dgraph.io/t/find-paths-between-one-node-and-a-group-of-nodes/12098/11 "2021-01-08T22:30:53Z")

</div>

> [@johan-l](#):
>
> But when I do that (even with numpath: 2) all the nodes striked with a purple line is removed from the query, since it’s a circular path. But without those nodes I’m unable to determine if the removed node is in the path or not.

It is not clear to me from the diagram and the explanation as to what is failing. Is it possible for you to give a sample schema/data for me to work through it?

Looking at the diagram if you do query between two red circled nodes with `numPaths=2` it should return two paths of length `7` and `9`. [Circular walks are removed](https://github.com/dgraph-io/dgraph/blob/b05fb930ffdbbb2f849d73a1e57bc8bd7575255d/query/shortest.go#L389) because they are not paths in strictest terms of the word. (See [definitions on Wikipedia](https://en.wikipedia.org/wiki/Path_(graph_theory)))

Happy to work with you on this if you could provide more information on schema and data.

Cheers!

---

<div class="post-metadata">

**Author:** ![Anurag](https://yyz1.discourse-cdn.com/flex007/user_avatar/discuss.dgraph.io/anurag/32/2599_2.png) [@Anurag](https://discuss.dgraph.io/u/Anurag)\
**Post date:** [January 8, 2021, 10:43pm UTC](https://discuss.dgraph.io/t/find-paths-between-one-node-and-a-group-of-nodes/12098/12 "2021-01-08T22:43:12Z")

</div>

> [@johan-l](#):
>
> The [documentation](https://dgraph.io/docs/query-language/recurse-query/) isn’t of much help here unfortunately.

Also what would you have liked to see more of in the documentation? Tagging our technical writers @damian and @acarey who can help us get our documentation upgraded.

---

<div class="post-metadata">

**Author:** ![johan-l](https://yyz1.discourse-cdn.com/flex007/user_avatar/discuss.dgraph.io/johan-l/32/5824_2.png) [@johan-l](https://discuss.dgraph.io/u/johan-l)\
**Post date:** [January 14, 2021, 5:59pm UTC](https://discuss.dgraph.io/t/find-paths-between-one-node-and-a-group-of-nodes/12098/14 "2021-01-14T17:59:58Z")

</div>

> There are two shortest path functions implemented internally: [shortestPath](https://github.com/dgraph-io/dgraph/blob/b05fb930ffdbbb2f849d73a1e57bc8bd7575255d/query/shortest.go#L465) and [runKshortestPaths](https://github.com/dgraph-io/dgraph/blob/b05fb930ffdbbb2f849d73a1e57bc8bd7575255d/query/shortest.go#L296). The former returns one path and the latter returns (or tries to return) total `numPaths` in ascending order of the distance .

Thanks, thats excellent!

> Happy to work with you on this if you could provide more information on schema and data.

Sorry my posts became quite messy since I couldn’t edit the original one (time ran out). I sorted this issue out myself, it was an error in my data as mentioned in the post above.

> Also what would you have liked to see more of in the documentation? Tagging our technical writers @damian and @acarey who can help us get our documentation upgraded.

I’m pretty sure the issue was that I were querying the data in the wrong order, and wherefore the returned results were empty. I originally assumed that is must be somethings wrong with the Query and since the documentation only had one example and not too much explanation on my issue I felt stuck.

I ended up re-seeding the database and make sure all edged were in the right direction, which got it working.

Thank you once more for the excellent support!

---

<div class="post-metadata">

**Author:** ![chewxy](https://yyz1.discourse-cdn.com/flex007/user_avatar/discuss.dgraph.io/chewxy/32/4339_2.png) [@chewxy](https://discuss.dgraph.io/u/chewxy)\
**Post date:** [April 1, 2021, 9:48pm UTC](https://discuss.dgraph.io/t/find-paths-between-one-node-and-a-group-of-nodes/12098/15 "2021-04-01T21:48:24Z")

</div>

A post was split to a new topic: [Order query](https://discuss.dgraph.io/t/order-query/13511)

---

<div class="post-metadata">

**Author:** ![chewxy](https://yyz1.discourse-cdn.com/flex007/user_avatar/discuss.dgraph.io/chewxy/32/4339_2.png) [@chewxy](https://discuss.dgraph.io/u/chewxy)\
**Post date:** [April 1, 2021, 9:48pm UTC](https://discuss.dgraph.io/t/find-paths-between-one-node-and-a-group-of-nodes/12098/16 "2021-04-01T21:48:32Z")

</div>