Find shortest path without specifying predicates

Issues Dgraph
, , , ,
1

Moved from GitHub dgraph/2265

Posted by omurbekjk:

How to find shortest path between two nodes ignoring any edge/route between them?
Example:

{
 path as shortest(from: 0x2, to: 0x5) {
  friend # here??? 
 }
 path(func: uid(path)) {
   name
 }
}

more ex: A->B->C->D, A->C->D
find shortest path between A and D should return A->C->D

2

pawanrawal commented :

You need to specify the intermediate nodes for now. Though I think we could make that optional given that we store the list of outgoing predicates from a uid.

3

armaneous commented :

@pawanrawal I think there are some real use-cases where someone would need to know whether there exists any relationship from A to D and if it exists what the shortest path is.

4

jimanvlad commented :

I’m in agreement to the above. There are situations where you wouldn’t
easily know the intermediary node.

On Fri, 30 Mar 2018 at 23:37, Andrew Armaneous notifications@github.com
wrote:

@pawanrawal https://github.com/pawanrawal I think there are some real
use-cases where we need to know whether there exists any relationship from
A to D and if it exists what the shortest path is.

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub
https://github.com/dgraph-io/dgraph/issues/2265#issuecomment-377638891,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACKSZhFVy1NWM9byflwah6rGxu5Fk3R6ks5tjrOugaJpZM4S8TfH
.

–
Thanks,
Vlad

5

armaneous commented :

@pawanrawal Is there any update to whether or not something like this will be included in the roadmap?

How do I get the list of outgoing predicates from a uid?

6

pawanrawal commented :

@pawanrawal Is there any update to whether or not something like this will be included in the roadmap?

Sure, it is on the roadmap and would be done soon.

How do I get the list of outgoing predicates from a uid?

You can get the list of outgoing predicates from a uid using _predicate_.

7

omurbekjk commented :

@pawanrawal Just to clarify, right now there is no distinction between node property and edge and everything is predicate in dgraph right? Can we say dgraph supports property graph? Because property graph has properties and edges between nodes.

8

armaneous commented :

@pawanrawal _predicate_ returns all predicates, not necessarily just the ones that are edges, correct? Is there way to just get the edges?

On that note, is there any way to filter on predicates (not on predicate values)?

9

pawanrawal commented :

Nope, there isn’t yet a way to filter on the predicate names.

10

campoy commented :

Hi there,

There’s a way to do this by first fetching the schema and then using all of the predicates available.

I wrote a small Go program demonstrating how to do so in this gist: Dgraph: K-Shortest Path with all predicates · GitHub

Note that limiting the depth of the search is very important, as otherwise the search space is huge.
In our case, since we know that the relationship should look like director - movie - performance - actor we’re setting it to 2 (as in two hops).

The program does the following:

  • fetches the UID for Steven Spielberg as a director (or whatever value -director has)
  • fetches the UID for Jeff Goldblum as a director (or whatever value -actor has)
  • fetches the list of all predicates
    • ignoring those starting with dgraph. as they are internal
    • ignoring those of type password because … there’s a bug #3657
  • sends a shortest path query with the UIDs and all the predicates

This works!

I hope the workaround is useful. That said, I’ll keep this issue open to consider implementing this functionality on the Dgraph server directly.