ShortestPath

Users
1

when doing the shortest path, how can I return all the “names” the path has traversed through, rather than just getting the UID.
In my use case I need to find different dept of interconnections between entities.

another question would be if I want to find the with numpaths of 2 or greater, but for 3 nodes
somehow numpaths does not work in this scenario

{
A as var(func: eq(name, “Alice”))
E as var(func: eq(name, “Ethan”))
C as var(func: eq(name, “Chow”))

AEpath as shortest(from: uid(A), to: uid(E), numpaths: 2) {
friend
}

ACpath as shortest(from: uid(A), to: uid(C), numpaths: 2) {
friend
}

CEpath as shortest(from: uid(C), to: uid(E), numpaths: 2) {
friend
}

sp1path(func: uid(AEpath)) {
name
uid
}

sp2path(func: uid(ACpath)) {
name
uid
}

sp3path(func: uid(CEpath)) {
name
uid
}

}


.......................The mutation.................
{
  set {
    _:a <friend> _:b .
    _:b <friend> _:c .
    _:c <friend> _:d .
    _:a <friend> _:d .
    _:d <friend> _:e .
    _:a <friend> _:e .
    _:a <friend> _:f .
    _:a <name> "Alice" .
    _:a <dgraph.type> "Person" .
    _:b <name> "Bob" .
    _:b <dgraph.type> "Person" .
    _:c <name> "Chow" .
    _:c <dgraph.type> "Person" .
    _:d <name> "Danny" .
    _:d <dgraph.type> "Person" .
    _:e <name> "Ethan" .
    _:e <dgraph.type> "Person" .
    _:f <name> "Francis" .
    _:f <dgraph.type> "Person" .
   
  }
}
2

In the _path_ block? you can’t.

Not sure what you mean. Can you explain?

3

I was trying to find the shortest path between three nodes
A,B,C

seems dgraph is not able to compute multiple shortest in a single go, it has to be queried individually.
please do let me know if my understanding is correct.

4

Correct, shortest path can be only run now between 2 uids right now.

feature request time - if you have an algorithm in mind go ahead and put in a feature suggestion. Be sure to explain the algorithm and/or UX. Some times the hardest part is getting a good UX on a feature.

Currently if you say “the shortest path between 3 nodes” I am not sure what that would mean or what the response would look like.

5

Well in my use case, if i have 3 nodes and i want to find the interconnection between them
say Nodes A,B and C

I would need to find the below paths:
A–>B
B–>A *
A–>C
C–>A *
B–>C
C–>B *

(*)assuming no reverse relation is used)

If i could do this in a single query…would be great, but i would now need to loop and query multiple times to find the interconnections between them.

6

Multiple blocks, but still single network request, which on its own is pretty cool.

Note than in your original post you can union your three query blocks together:

paths(func: uid(AEpath,CEpath,ACpath)) {
  name
  uid
}

Not that that saves you from having the 3 shortest path blocks.