Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

Appearance settings
This repository was archived by the owner on Apr 22, 2020. It is now read-only.
This repository was archived by the owner on Apr 22, 2020. It is now read-only.

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

Copy link
Copy link
Open
@Stef-van-Diepen

Description

@Stef-van-Diepen
Issue body actions

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"

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions

      Morty Proxy This is a proxified and sanitized view of the page, visit original site.