cancel
Showing results for 
Search instead for 
Did you mean: 

Graph Data Science Breadth-first-search doesn't give desired results

cuneyttyler
Ninja
Ninja

I have the following Graph Data Science BFS call. In this call, When I gave both 'Apple Inc.' and 'Microsoft' as target nodes, it only returns results with 'Steve Jobs' and 'Apple' which are directly linked. When I only give 'Microsoft' as target node, it returns a lot of nodes including source and target and many irrelevant.

I'd expect it to return only the PATH although it returns a lot of nodes(about 300) that are not in the path. I also would expect it that when I give both 'Apple' and 'Microsoft' as target nodes to return a union of these two although it now only returns a very small graph with only 'Steve Jobs' and 'Apple' (and a one common node linked by both)

These are some unexpected output I have encountered. Can you explain why are these happening and is there any way to get correct output?

Thanks.

My query:

MATCH (a:Entity{name:'Steve Jobs'}), (d:Entity{name:'Apple Inc.'}), (e:Entity{name:'Microsoft'})
WITH id(a) AS source, [id(d),id(e)] AS targetNodes
CALL gds.bfs.stream('myGraph', {
sourceNode: source,
targetNodes: targetNodes,
maxDepth: 4
})
YIELD path
RETURN path
1 ACCEPTED SOLUTION

Hi @cuneyttyler,

Your questions likely have to do with the fact that BFS returns not a source--target path, but instead a list of all nodes examined until a target is hit (when one is specified).

That is why the 'Steve Jobs' -'Microsoft' query has a lot of seemingly unrelated nodes: they were all examined at some point prior to the 'Microsoft' node.

Note also that BFS quits as soon as any target node is reached, hence why putting 'Apple' in your target-list returns so few nodes.

Indeed, as you have figured out, Djikstra's output is probably better suited towards your application.

I hope the above answer your questions.

Best regards.

View solution in original post

4 REPLIES 4

Hi @cuneyttyler: what version of the GDS library are you using here?

It's 2.0.4. Although I found that dijkstra's shortest path is more suitable for my purpose and I'm also considering writing a multiple-pairs shortest path using pregel. But this question remains though as it has some points.

Hi @cuneyttyler,

Your questions likely have to do with the fact that BFS returns not a source--target path, but instead a list of all nodes examined until a target is hit (when one is specified).

That is why the 'Steve Jobs' -'Microsoft' query has a lot of seemingly unrelated nodes: they were all examined at some point prior to the 'Microsoft' node.

Note also that BFS quits as soon as any target node is reached, hence why putting 'Apple' in your target-list returns so few nodes.

Indeed, as you have figured out, Djikstra's output is probably better suited towards your application.

I hope the above answer your questions.

Best regards.

cuneyttyler
Ninja
Ninja

Thanks I'm using Dijkstra now.