Cypher BFS with multiple Relations in Path

Question

I'd like to model autonomous systems and their relationships in Graph Database (memgraph-db)

There are two different kinds of relationships that can exist between nodes:

• undirected peer2peer relationships (edges without arrows in image)
• directed provider2customer relationships (arrows pointing to provider in image)

The following image shows valid paths that I want to find with some query

They can be described as

(s)-[:provider*0..n]->()-[:peer*0..n]—()<-[:provider*0..n]-(d)

or in other words

0-n c2p edges followed by 0-n p2p edges followed by 0-n p2c edges

I can fix the first and last node and would like to find a (shortest/cheapest) path. As I understand I can do BFS if there is ONE relation on the path.

Is there a way to query for paths of such form in Cypher?

As an alternative I could do individual queries where I specify the length of each of the segments and then do a query for every length of path until a path is found.

i.e.

MATCH (s)<-[]->(d)                            // All one hop paths
MATCH (s)-[:provider]->()-[:peer]-(d)         
MATCH (s)-[:provider]->()<-[:provider]-(d)
...

Answer 1

Since it's viable to have 7 different path sections, I don't see how 3 BFS patterns (... BFS*0..n) would yield a valid solution. It's impossible to have an empty path because the pattern contains some nodes between them (I have to double-check that).

Writing individual patterns is not great.

Some options are:

• MATCH path=(s)-[:BFS*0.n]-(d) WHERE {{filter_expression}} -> The expression has to be quite complex in order to yield valid paths.
• MATCH path=(s)-[:BFS*0.n]-(d) CALL module.filter_procedure(path) -> The module.procedure(path) could be implemented in Python or C/C++. Please take a look here. I would recommend starting with Python since it's much easier. Python for the PoC should be fine. I would also recommend starting with this option because I'm pretty confident the solution will work, + it's modular. After all, the filter_procedure could be extended easily, while the query will stay the same.

Could you please provide a sample dataset in a format of a Cypher query (a couple of nodes and edges / a small graph)? I'm glad to come up with a solution.