Finding all paths from point to point?

Question

Algorithms

Hello!
There is the following task: to find all possible paths from point to point on the network graph. The connections in the ~200M graph are in MySQL Percona.
Trying to solve a problem with MariaDB & OQGRAPH , but it either shows all nodes that can be reached from the starting point (depth = 1) latch=0 and origid=<x>, or the shortest path between points (latch=1|2 and origid=<x> and destid=<y>), or all possible paths from the point (latch=1 and origid=<x>).
A query for all possible paths from a point (latch=1 and origid=<x>) would, in principle, be fine if it were possible to limit the graph travel paths by points and depth (using linkid not in(x...) and weight=<z>, where <z> is ​​always the same for all nodes), but I get the feeling that with such a query, a complete enumeration of the graph occurs, and the filter is applied only to display the result.
First, I would like to ask those who have experience with mariadb & oqgraph, does where (weight=<x> and linkid=<y>) apply during graph traversal, or does it just filter all data after a full traversal?
Secondly, please advise what alternatives to this solution can be? We need a graph-oriented DBMS with an algorithm for finding all paths between points.

Answer 1

Your task is unsolvable in practice - neither by means of the DBMS, nor even by writing a program that implements the algorithm.
I'll explain why. Let's decide for simplicity that we are only looking for paths that do not visit the same vertex more than once - the so-called "simple" paths. If this restriction is not imposed, then the number of paths will be incomparably greater, and if there are cycles in the graph, it will be infinite.
But even enumeration of simple paths is impossible with such a size of the graph. The point is that the number of simple paths from node A to node B depends exponentially on the number of edges in the graph. The exponential growth of complexity leads to the fact that when the number of edges exceeds tens, the enumeration of paths takes an unacceptably long time. In the case of millions of edges, things are still much worse.
You can try to implement a depth-first search and see for yourself.
I note that when some strict restrictions are imposed on the graph structure (for example, no more than 2 edges coming out of each vertex), the running time of the depth-first search becomes acceptable - polynomial asymptotics instead of exponential. But in practice, of course, the matter is not limited to such graphs.