search

neo4j-contrib / neo4j-graph-algorithms

Efficient Graph Algorithms for Neo4j
https://github.com/neo4j/graph-data-science/
GNU General Public License v3.0
770 stars 194 forks source link

DFS/BFS: Cost calculation incorrect for incoming relationships #936

Open Stef-van-Diepen opened 4 years ago

Stef-van-Diepen commented 4 years ago

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"

tomasonjo commented 4 years ago

Please try the https://github.com/neo4j/graph-data-science as the graph algorithms will not be maintained anymore. I have tried it and it seems the undirected problem does not persist there.