Does nebula offer all shortest path algorithm?

[lingxuan9]

Hi, I would like to know that if nebula offers an algorithm to search all the shortest paths between different node pairs? Rather than only find one shortest path for each node pair?

Many thanks.

[xiajingchun]

You may consider running Nebula Algorithms in a spark cluster, check this out: https://docs.nebula-graph.io/3.0.1/nebula-algorithm/

[xiajingchun]

Wait a minute :), if you meant to use "FIND SHORTEST PATH", it does return all paths between node pairs.
For instance:

(root@nebula) [nba]> find shortest path from "Dirk Nowitzki" to "Suns" over * yield path as paths
+--------------------------------------------------------------------------+
| paths |
+--------------------------------------------------------------------------+
| <("Dirk Nowitzki")-[:like@0 {}]->("Steve Nash")-[:serve@1 {}]->("Suns")> |
| <("Dirk Nowitzki")-[:like@0 {}]->("Steve Nash")-[:serve@0 {}]->("Suns")> |
| <("Dirk Nowitzki")-[:like@0 {}]->("Jason Kidd")-[:serve@0 {}]->("Suns")> |
+--------------------------------------------------------------------------+
Got 3 rows (time spent 1244/14759 us)

cc @jamieliu1023

[lingxuan9]

Hi, thanks for your reply. Does it mean, according to this query I could get all the shortest paths between two nodes, instead of only one shortest path? Is there any place I can find the codes/algorithms behind this query?

[wey-gu]

Dear @lingxuan9
You cloud check how it's planed with explain like:

EXPLAIN FIND SHORTEST PATH FROM "player100" TO "player101" OVER follow BIDIRECT UPTO 5 STEPS YIELD path as p

or

EXPLAIN format="dot" FIND SHORTEST PATH FROM "player100" TO "player101" OVER follow BIDIRECT UPTO 5 STEPS YIELD path as p

For the format="dot", you could render the plan in nebula studio or GraphViz like:

And it actually does BFSShortest from the start and end vertex(at the same time), up to [5/2]==3 steps , if you check the loop condition from the table format of EXPLAIN

(root@nebula) [basketballplayer]> EXPLAIN FIND SHORTEST PATH FROM "player100" TO "player101" OVER follow BIDIRECT UPTO 5 STEPS YIELD path as p
Execution succeeded (time spent 4789/14434 us)

Execution Plan (optimize time 1090 us)
...
-----+--------------+--------------+----------------+------------------------------------------------------------------------------------------------------
|  8 | Loop         | 0            |                | outputVar: [                                                                                        |
|    |              |              |                |   {                                                                                                 |
|    |              |              |                |     "colNames": [],                                                                                 |
|    |              |              |                |     "type": "DATASET",                                                                              |
|    |              |              |                |     "name": "__Loop_8"                                                                              |
|    |              |              |                |   }                                                                                                 |
|    |              |              |                | ]                                                                                                   |
|    |              |              |                | inputVar:                                                                                           |
|    |              |              |                | condition: ((++($__VAR_2)<=3) AND (($__ConjunctPath_7==__EMPTY__) OR (size($__ConjunctPath_7)==0))) |
|    |              |              |                | loopBody: 7                                                                                         |
-----+--------------+--------------+----------------+------------------------------------------------------------------------------------------------------
...

Then, you could check the corresponding planner/ executor code in the codebase of the current repo.

ref:

• planner: https://github.com/vesoft-inc/nebula/tree/master/src/graph/planner
  • pathplanner
• executor: https://github.com/vesoft-inc/nebula/tree/master/src/graph/executor
  • BFSShortestPathExecutor.cpp
• blogs post like: https://nebula-graph.io/posts/nebula-query-engine-introduction/
• more posts: https://nebula-graph.io/tags/architecture/ , https://nebula-graph.io/tags/source-code/ or in Chinese https://nebula-graph.com.cn/tags/%E6%9E%B6%E6%9E%84%E8%AE%BE%E8%AE%A1/

(root@nebula) [basketballplayer]> FIND SHORTEST PATH FROM "player100" TO "player101" OVER follow BIDIRECT UPTO 5 STEPS YIELD path as p
+-----------------------------------------------+
| p                                             |
+-----------------------------------------------+
| <("player100")-[:follow@0 {}]->("player101")> |
| <("player100")<-[:follow@0 {}]-("player101")> |
+-----------------------------------------------+

[wey-gu]

I guess Rather than only find one shortest path for each node pair? the one refers to one pair of start-end nodes.

If I understood this correctly(you are looking for whole graph shortest paths), please, as @xiajingchun mentioned use the nebula algorithm to do so.