Dgraph: Query paths between 2 nodes

[magallardo]

It will be nice if query could return all paths between 2 different nodes S (source node) and D (destination node). The query should allow to provide predicates and also the length of the paths to be returned. For example, if I want all the paths between S and D with no nodes in between, the length would be 2. If I want all the paths between S and D with 2 nodes in between, the length would be 4.
The use case is airline routing scenarios. For example, find all routes between 2 airports with 0 connections. Or find all routes between 2 airports with 2 connections.
Thanks

[weickdev]

This is very useful, and I think every graph db user need it.

[manishrjain]

We already have a way to get K shortest paths. We could add a maxweight argument, which can be used to restrict the search. In the above example, this can be 2 or 4 if each edge weighs 1.

Can you confirm that accurately describes what you're looking for?

[magallardo]

@manishrjain That might work but I don't know if that will be the best implementation. The reason is that I am not looking for the shortest paths. I am interested in all the paths of certain length (i.e 2, 3, 6, etc) that match some predicate conditions. In my scenario, I don't have any weights. However, your suggestion is something that might for scenarios where the query is for the k shortest paths of length x, where shortest is calculated by some weight field.
Thanks

[manishrjain]

The length in your case is the weight. You can set it so that each edge is of weight 1, which would then fit well with the k-shortest path algorithm, where you're looking for all paths between S and D, with a particular weight.

Also, shortest path is important here. If you have a loop between A -> B -> A, then if you continue to follow this loop, then you'd consider the distance between A and B to be of length 1, 3, 5, 7, 11, and so on. That wouldn't be right.

[weickdev]

@manishrjain
In other graph databases, the path searching will stop if find a loop, such as ArangoDB and OrientDB. So you can get a path like A -> B -> A, but never get A -> B ->A -> B.

K shortest paths is very useful, but as @magallardo said, sometimes we don't want the k shortest paths. Such as

• How many paths between two nodes?
• Is there a path bigger than X between two nodes？ Of course excluding A->B->A-B.
• Is there a path it's length is X? Of course excluding A->B->A-B.
• find all the node between two nodes.
  and so on.

I think dgraph can add a length range parameter to the k-shortest path method. This will make it much more useful.

[manishrjain]

We could allow minweight and maxweight arguments to our K shortest path algo. That would give the needed outcome.

[fendor]

Is there some update to this issue?
I would require such an functionality, and it seems that it is currently not possible.

[zhuzhongshu]

+1, this functionality is extremely useful.

[martinmr]

Reopening issue to add documentation.

[martinmr]

Added the new arguments to the docs.