shortestPath doesn't work for cycles/loops

[IanRogers]

• Neo4j version: 3.1.1 with web browser app: 2.0.0-M10
• Operating system: Ubuntu 16.04

I'm trying to detect simple relationship cycles/loops as efficiently as possible, but shortestPath doesn't return anything...

# Start with a clean database
create constraint on (n:T) assert n.name is unique
create (a:T {name:'a'})-[:isa]->(:T {name:'b'})-[:isa]->(:T {name:'c'})-[:isa]->(a)

match (n) return *   # works (obviously) - shows the loop we expect
match p = (a:T {name:'a'})-[:isa*]-(a) return p  # works - shows the loop
match (a:T {name:'a'}), p = (a)-[:isa*]-(a) return p # works

# in fact we only care if there's a loop or not
match p = (a:T {name:'a'})-[:isa*]-(a) return p limit 1 # works

match p = shortestPath((a:T {name:'a'})-[:isa*]-(a)) return p # no match
match (a:T {name:'a'}), p = shortestPath((a)-[:isa*]-(a)) return p  # no match
# same with allShortestPaths

[spacecowboy]

@IanRogers shortestPath You are telling it to find the shortestPath from Node A to itself and the shortest path to your starting location is a path of length 0.

I encourage you to write your own traversal function with the use case you have in mind.

Closing this as it's working as intended.

[IanRogers-LShift]

I'm kinda disappointed that you closed this so quickly out of hand because the use case is clear: what is the most efficient way to tell if the current node is part of a loop of relationships labelled "R".

And I'm not convinced that shortestPath is working correctly as the query was (a)-[:isa*]-(a) i.e. at least one link. Though I'm doubting myself now - does [:isa*] imply [:isa*1..] or [:isa*0..] ? I've just read through http://neo4j.com/docs/developer-manual/current/cypher/syntax/patterns/ again and it doesn't specify...

@spacecowboy can you reopen this issue at least until this question is answered please?

[craigtaverner]

The shortestPath algorithm explicitly disallows the case of startNode=endNode. See https://github.com/neo4j/neo4j/blob/3.2/community/graph-algo/src/main/java/org/neo4j/graphalgo/impl/path/ShortestPath.java#L142. I believe this is due to the fact that the bi-directional BFS search uses a check of node-uniqueness to prune out already touched nodes and detect when the left and right searches reach each other. This means that it is not possible to use this algorithm to detect existing cycles. However, it would be possible to use it to detect if a planned relationship creation would result in a cycle. For example, if you want to create a relationship between two different nodes a and b, and you first check if there is already path between a and b using shortestPath, and then only make the relationship if there is no existing path, you should be able to avoid cycles.

On the question of the default minimum value for shortest path, it appears that both the varlength-expand syntax and the shortestPath syntax default to 1 for the min length, but both can be expressed with an explicit 0 like so:

MATCH p = (a:T {name:'a'})-[:isa*0..]-(a) return length(p)  # returns 0,3,3
MATCH p = shortestPath((a:T {name:'a'})-[:isa*0..]-(a)) return length(p)  # returns 0

These two example both give the correct answer. However, when you express the min length as 1, then we get:

MATCH p = (a:T {name:'a'})-[:isa*1..]-(a) return length(p)  # returns 3,3 (correct)
MATCH p = shortestPath((a:T {name:'a'})-[:isa*1..]-(a)) return length(p)  # no result (incorrect)

As described above, shortestPath gives the incorrect answer because it cannot handle the same start and end node. However, it would be possible to get Cypher to revert to the explicit var-length algorithm for this case, and we'll investigate that option. It does not satisfy your requirement on the most efficient algorithm, but would at least give the correct answer.

[marcusze]

Is there a solution to this available in the graph algorithm package?
I need to find a work-around to force the algorithm to leave the start/finish node.
//Shortest path search MATCH (start:USD), (end:USD) CALL algo.shortestPath.stream(start, end, 'rate') YIELD nodeId, cost RETURN labels(algo.asNode(nodeId)) AS name, cost //returns (no changes, no records)

[sherfert]

@marcusze I'd recommend asking that question over in https://github.com/neo4j/graph-data-science