Excluding certain paths from allShortestPaths

[stefan_schaubsc]

I want to find the shortest paths between two nodes in a graph. I use the allShortestPaths algorithm in Neo4j Cypher. Not all possible paths should be considered when applying the algorithm, some certain paths should be excluded from the search. I don't want to exclude certain node labels or certain relationships, I need to exclude a certain path pattern from the algorithm.

Let's consider the following simplified example:

CREATE 
    (b:Bank {name: "Money Bank"}),
    (c1:Customer {customerNumber:123}),
    (c2:Customer {customerNumber:456}),
    (p:Person {name:"Mr. X"}),
    (com:Company {name:"ACME Inc."}),
    (c1)-[:HAS_ACCOUNT_IN]->(b),
    (c2)-[:HAS_ACCOUNT_IN]->(b),
    (c1)-[:MATCHES]->(com),
    (c2)-[:MATCHES]->(p),
    (p)-[:WORKS_FOR]->(com)

Two customers have an account in the "Money Bank". Customer 123 matches the company "ACME Inc." and Customer 456 matches the person "Mr. X", who is working for "ACME Inc.". I want to find all shortest paths between "Money Bank" and "ACME Inc.", but I don't want to consider the path (Company)-(Customer)-(Bank) in my search for the shortest paths.

To me, the most intuitive way to accomplish this, would be the following cypher:

MATCH path=allShortestPaths((b:Bank {name:"Money Bank"})-[*1..5]-(com:Company{name: "ACME Inc."}))
WHERE NOT (b)<-[:HAS_ACCOUNT_IN]-(:Customer)-[:MATCHES]->(com)
RETURN path

But this returns no records/paths. I would have expected that the WHERE is evaluated before applying the allShortestPath algorithm. Is this assumption wrong? If this is the case, what would be the best way to achieve what I want? Thanks for your help!

[Cobra]

Hello @stefan.schaubschlaeg

There is at least two ways to achieve what you would like to do:

• The first use GDS, you can create a graph projection with the nodes and relationships you want, then execute a path algorithm on it.
• The second use APOC, you can use the procedure apoc.path.expandConfig() which allow you to filter node labels or relationship types.

Regards,
Cobra

[stefan_schaubsc]

Hi @Cobra.
Thanks for your suggestions. The point is, that I can't just filter out certain node labels or relationship types. I have to filter out a certain path pattern.

If I just had to filter out node or relationship types, I guess I could change the query to something like that:

MATCH path=allShortestPaths((b:Bank {name:"Money Bank"})-[*1..5]-(com:Company{name: "ACME Inc."}))
WHERE ALL (r IN relationships(path) WHERE type(r) <>  'WORKS_FOR') 
RETURN path

But this filter is to general as I don't want to filter out all WORKS_FOR relationships. I just want to filter out the path that goes directly from the bank to a customer to a company.

Regards,
Stefan

[Cobra · Accepted solution]

You cannot use allShortestPaths() or shortestPath() functions to do what you want. You can use apoc.path.expandConfig() procedure which is able to make certain restrictions on patterns:

In this query, I just increased the "minLevel" to 3 to make sure the algorithm doesn't take a direct path:

MATCH (b:Bank {name: "Money Bank"})
MATCH (c:Company {name: "ACME Inc."})
CALL apoc.path.expandConfig(b, {
	minLevel: 3,
	maxLevel: 5,
    terminatorNodes: c
})
YIELD path
RETURN path, length(path) AS hops
ORDER BY hops;

You can play with the configuration if you want to have more particular results.

[stefan_schaubsc]

Thank you for clarifying the use of apoc.path.expandConfig. This procedure is definitely a solution to my problem. Besides the solution for my rather simple example, I am also able to solve the issue in my real scenario quite well after playing a bit with the configuration!

In order to achieve a better understanding of cypher and shortest paths, just let me again ask the question, why my original cypher did not work as I thought:

MATCH path=allShortestPaths((b:Bank {name:"Money Bank"})-[*1..5]-(com:Company{name: "ACME Inc."}))
WHERE NOT (b)<-[:HAS_ACCOUNT_IN]-(:Customer)-[:MATCHES]->(com)
RETURN path

As it is possible to filter certain relationships/labels in the WHERE clause (and it seems to me that this filtering is done BEFORE the shortest path is applied), I would have expected that it is also possible to filter a whole path pattern in the WHERE clause before the algorithm is applied. Where is my thought error?

[Cobra]

It is possible to apply the WHERE clause but you cannot filter the path like this. This query means you want all shortest paths between b and com but they cannot be connected like (b)<-[:HAS_ACCOUNT_IN]-(:Customer)-[:MATCHES]->(com) which is not the case in your dataset. I do not know if it's clear. Generally, if you want to apply certain conditions to nodes/relationships or properties, you should use predicate functions.

But if you want to filter the path, you only have two options which I described earlier.

[genealogy]

Have you considered using collect or reduce to aggregate properties from the paths and then filtering out the undesired paths. I've used this strategy in traversing family trees to get the paths that represent X-chromosome inheritance; that is, no father to father inheritance. This statement creates a concatenated string of the sex of the person at each hop in the family tree traversal.

reduce(srt2 ='', q IN nodes(p)| srt2 + q.sex)

You then filter with

where sortOrder=replace(sortOrder,'MM','')

which removes any path with "MM" from the return leaving you with only the paths which where X-chromosome might be inherited..