Find Shortest Path in Social Graph

Hey Fauna-Community,
is it possible to use Fauna for shortest path queries?
I’m looking at the social graph example from the docs which has some details on direct link queries. I’m trying to achieve a query like this: “What is the shortest path between Dave and Bob?” => Dave->Alice->Bob.
This is a shortest path problem in graphs. I’m thinking of running Dijkstra in a Fauna Function. Is this performant?
Next to shortest-path, I’d also be interested in k-shortest-path.
Cheers, Anton

2 Likes

Hi @abegehr - welcome to the forums!

I’m going to set k-shortest aside, as I only learned about it from your post. That said, you should be able to get there from my understanding.

The key to Dijkstra in FQL is recursion with user-defined functions (UDFs). Keep in mind the following constraints:

  1. You must pass the set of visited nodes into each recursive call. This grows linearly per individual potential path but exponentially for the overall calculation. Quite frankly, I’m not sure how this will affect performance. You will need to test/measure to be sure.
  2. Recursive calls in FQL are limited to a depth of 200, which in turn will limit the maximum search path length. Note that there’s no limitation on width, so if each node has thousands of edges, I’m again uncertain about what will happen.

The basic format of recursion is:

CreateFunction({
  name: "ShortestPath",
  body: Query(Lambda(
    ["graph", "source"],
    Map(
      Select(["nodes"], Var("graph")),
      Lambda(
        "nextNode",
        Call(
          "ShortestPath",
          [Var("nextNode"), Var("source")]
        )
      )
    )
  ))
})

Note: This is not an attempt to implement Dijkstra or even what your signature will look like, only an example to show you how recursion is implemented in UDFs.

There’s a lot more to do here. Let us know how this turns out!