DFS/BFS: Cost calculation incorrect for incoming relationships #936
Description
I'm using version Neo4j Graph Algorithms 3.5.14.0. The cost is not calculated correctly for incomming relationships atf the bfs en dfs function. See my test case:
MERGE (a:Test {id:"A"})
MERGE (b:Test {id:"B"})
MERGE (c:Test {id:"C"})
MERGE (d:Test {id:"D"})
MERGE (e:Test {id:"E"})
MERGE (a)-[:LINK {cost:2}]->(b)
MERGE (b)-[:LINK {cost:2}]->(c)
MERGE (c)-[:LINK {cost:2}]->(d)
MERGE (d)-[:LINK {cost:2}]->(e)
Setting the maxCost value means that nodes behind the relationship at which the maxCost is reached, will not be returned. So in this test case with maxCost:3, we expect only nodes B and D to be returned:
Direction: BOTH
MATCH (start:Test{id:'C'})
CALL algo.dfs.stream(null, 'LINK', 'BOTH', id(start),
{maxCost:3, weightProperty:'cost'})
YIELD nodeIds
UNWIND nodeIds as nodeId
RETURN algo.asNode(nodeId).id as node
node
"C"
"B"
"A"
"D"
Node A should not be returned..
Direction: OUTGOING
MATCH (start:Test{id:'C'})
CALL algo.dfs.stream(null, 'LINK', 'OUT', id(start),
{maxCost:3, weightProperty:'cost'})
YIELD nodeIds
UNWIND nodeIds as nodeId
RETURN algo.asNode(nodeId).id as node
node
"C"
"D
This is correct
Direction: INCOMING
MATCH (start:Test{id:'C'})
CALL algo.dfs.stream(null, 'LINK', 'IN', id(start),
{maxCost:3, weightProperty:'cost'})
YIELD nodeIds
UNWIND nodeIds as nodeId
RETURN algo.asNode(nodeId).id as node
node
"C"
"B"
"A"
Node A should not be returned. It looks like the value of the cost property is not valuated for incoming relationships, but it just increases the cost with 1 at every relationship.
Check this:
MATCH (start:Test{id:'C'})
CALL algo.dfs.stream(null, 'LINK', 'IN', id(start),
{maxCost:2, weightProperty:'cost'})
YIELD nodeIds
UNWIND nodeIds as nodeId
RETURN algo.asNode(nodeId).id as node
node
"C"
"B"
MATCH (start:Test{id:'C'})
CALL algo.dfs.stream(null, 'LINK', 'IN', id(start),
{maxCost:1, weightProperty:'cost'})
YIELD nodeIds
UNWIND nodeIds as nodeId
RETURN algo.asNode(nodeId).id as node
node
"C"