Skip to content
This repository has been archived by the owner on Apr 22, 2020. It is now read-only.

MaxDepth param for Breadth-first search #898

Open
tomasonjo opened this issue Apr 22, 2019 · 1 comment
Open

MaxDepth param for Breadth-first search #898

tomasonjo opened this issue Apr 22, 2019 · 1 comment

Comments

@tomasonjo
Copy link
Collaborator

It looks like the DFS algorithm has the maxDepth parameter that includes the max value while the BFS algorithm does not include it. This can be confusing to an end user.

Create graph:

MERGE (nAlice:User {id:'Alice'})
MERGE (nBridget:User {id:'Bridget'})
MERGE (nCharles:User {id:'Charles'})
MERGE (nDoug:User {id:'Doug'})
MERGE (nMark:User {id:'Mark'})
MERGE (nMichael:User {id:'Michael'})

MERGE (nAlice)-[:FOLLOW]->(nBridget)
MERGE (nAlice)-[:FOLLOW]->(nCharles)
MERGE (nBridget)-[:FOLLOW]->(nMichael)
MERGE (nDoug)-[:FOLLOW]->(nMark)
MERGE (nAlice)-[:FOLLOW]->(nMichael)
MERGE (nCharles)-[:FOLLOW]->(nDoug);

BFS

MATCH (s:User{id:'Bridget'}) 
WITH id(s) as start_id 
CALL algo.bfs.stream('User', 'FOLLOW', 'BOTH', start_id, 
{maxDepth:2}) YIELD nodeIds 
UNWIND nodeIds as nodeId 
RETURN algo.asNode(nodeId).id as user

results:

user
"Bridget"
"Alice"
"Michael"

DFS

MATCH (s:User{id:'Bridget'}) 
WITH id(s) as start_id 
CALL algo.dfs.stream('User', 'FOLLOW', 'BOTH', start_id, 
{maxDepth:2}) 
YIELD nodeIds 
UNWIND nodeIds as nodeId 
RETURN algo.asNode(nodeId).id as user

results:

user
"Bridget"
"Michael"
"Alice"
"Charles"
@tomasonjo
Copy link
Collaborator Author

I inspected the code a bit and it is a simple difference in the comparing operator:

DFS:

exitFunction = (s, t, w) -> w > maxDepth ? Traverse.ExitPredicate.Result.CONTINUE : Traverse.ExitPredicate.Result.FOLLOW;
BFS:

exitFunction = (s, t, w) -> w >= maxDepth ? Traverse.ExitPredicate.Result.CONTINUE : Traverse.ExitPredicate.Result.FOLLOW;

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant