The point to note is that the shortest path is 9 hops away but there is another path which is 11 hops away but the whole graph shown is discoverable at depth = 9. Link to relevant docs.
Setting numpaths: 2 returns the shortest two paths:
That means you should see one or two paths at least. And both are valid.
Also this part
For k-shortest paths (when numpaths > 1), the result of the shortest path query variable will only return a single path. All k paths are returned in _path_ .
I think it means when numpaths = 1 and not x > n. Correct me if I’m wrong.
Yes, it should return two shortest paths if it can find 2, if it finds only 1 or none then it would return that. But my question is regarding the depth parameter. In the above graph you can see two paths (1 direct and other via R-M), so should we return both of these paths if depth = 9. What I want to understand is how do we understand the depth parameter.
This is structure of what is returned in the result. Only shortest path is returned always under path key (irrespective whether you asked for one path or more). Other paths (if available) are returned under _path_ key in the JSON.
After some more investigation here is a nice example which brings forth the confusion on depth parameter. I have introduced weights because I wanted a path which has greater hops but lower cost. In the below graph:
Q: What do you expect as the result for query?:
{
A as var(func: eq(name, "Alice"))
M as var(func: eq(name, "Mallory"))
path as shortest(from: uid(A), to: uid(M), depth:4) {
friend @facets(weight)
}
path(func: uid(path)) {
name
}
}
Ans: We get path — Alice - Manan - Naman - Bob - Tom - Mallory. This is the shortest path though this path has 5 hops and our allowed depth is 4.
IMO depth != hops. Even though docs use them interchangeably. Depth should be understood as the height/level of the tree you want to explore starting from the root. In that case the result is correct because the resulting path is visible if we explore the graph till depth = 4.
Also I feel more confident with this explanation because shortest path and K-shortest path are calculated in two different code blocks and they both seem to support this understanding of depth parameter. Update: Discussion here supports my claim.
Below query returns two paths in this example:
{
A as var(func: eq(name, "Alice"))
M as var(func: eq(name, "Mallory"))
path as shortest(from: uid(A), to: uid(M), numpaths:2, depth:4) {
friend
}
path(func: uid(path)) {
name
}
}
Hey Alvis, I can probably explain this better with a diagram which I’ll try and get one for you but depth is not the same as the length of the path. It is graph hops. At each hop, we start from a set of starting nodes and get their related nodes to get to the destination nodes. Then these destination nodes become the starting nodes for the next hop.
One hop from Alice gets us to Bob and Manan.
For second hop, we start with Bob and Manan and get to Naman and Tom.
For third hop, we get to Mallory from Tom. Note Naman just gets us to Bob which we have already discovered.
So this query with numpaths set to 1 and depth 3, should also return the path to Mallory I suppose?
After speaking to @Anurag and @pawan, I feel like returning paths which are longer than the depth is a bit unintuitive to the user. Taking the example listed here, the shortest path is 5 hops on depth 4. Now, let’s remove an edge which is not in the shortest path Alice-Bob. Running this query again will return “no path found”. This becomes a bit un-predictable for users, so I think it would make sense to update the docs to go the other way, and make depth = hops.
After more discussion internally with folks - depth parameter represents the level/depth of the tree when calculating from from the root node of the query. This means when specifying depth=k, the graph will be explored till depth=k starting from the root node and the shortest paths will be restricted to only those paths which have nodes that have been explored till the given depth.
More concretely for the first example:
We should get two paths 1. A-B-C-D-E-F-G-H-I-L and 2. A-R-Q-P-O-N-M-F-G-H-I-L
For the second example:
We should get the path: Alice - Manan - Naman - Bob - Tom - Mallory
Another edge case to note is in the following graph:
Below query would return only one path: Michone - Andrea - Bob - Alice because even though Matt gets discovered at depth=4 but Matt - Alice edge gets discovered only at depth=5
{
var(func: eq(name, "Michone")){
SOURCE as uid
}
var(func: eq(name, "Alice")){
TARGET as uid
}
path as shortest(from: uid(SOURCE), to: uid(TARGET), numpaths: 2, depth: 4) {
friend
}
path(func: uid(path)) {
name
}
}
