Multiple Pair Shortest Path algorithm with Pregel

[cuneyttyler]

I have an application where I'd like to retrieve shortest paths for multiple source-target pairs. I'd like to write my own function but as far as I figured out that with Pregel, writing such a function is not possible. Because pregel allows sending only one double value to other nodes and in this scenario it is not enough. I'm wondering if I'm right about this or is there any way to write a Pregel Algorithm to work out this problem.

For now, I'm going with Core Graph Api. It's possible to do this with that and it's not that complicated.

[martin_junghann]

Your observation is correct, Pregel messages are limited to double. What you could try is, given n source-target pairs, create a node schema with n distance vectors (one for each start node) and in the compute method update all of them. However, you need to run the computation as long as all targets have been found (or no messages are being sent).

Keep in mind that if you're using the core API, you need to deal with parallelism etc yourself. but you probably saw that.

[cuneyttyler]

How can I output the path then? Like in Core shorest-path functions (Dijkstra etc.). It seems that we can only output context variables which are primitives or primitive arrays.

[martin_junghann · Accepted solution]

Unfortunately, you can't have the same path outputs as the GDS algos if you use the procedure code generation for your Pregel computation. However, you can opt out of the Procedure code generation and add the procedures yourself (similar to how PageRank does it). If you do this, you can construct the paths from the predecessor arrays that you computed via Pregel. Note however, that this is advanced stuff and you need to use internal APIs. If you wanna go down that route, you'd need to have a closer look at what Dijkstra does once if finds a path.

[cuneyttyler]

Hi, thanks for the reply. I actually managed to do a concurrent multiple-pair dijkstra with internal API when I realise that I can't output PATH's with Pregel. See my post here if you're interested : https://community.neo4j.com/t5/neo4j-graph-platform/additional-algorithms-for-graph-data-science/td-...

It was a bit challenging but now I feel comfortable with the internal API. Surely it would be interesting to have possibility to return paths with pregel, I think you already have that in mind. But having the possibility to add procedures is also cool.