find shortest path without specifying predicates

[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

[pawanrawal]

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.

[armaneous]

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

[jimanvlad]

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

[armaneous]

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

[pawanrawal]

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

[omurbekjk]

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

[armaneous]

@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)?

[pawanrawal]

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

[campoy]

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: https://gist.github.com/campoy/ca88c27a24656eb6afa202682fc83442

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.

[minhaj-shakeel]

Github issues have been deprecated. This issue has been moved to discuss. You can follow the conversation there and also subscribe to updates by changing your notification preferences.