How to limit hop in Yen’s Shortest Path algorithm in Neo4j

[xiaoxlm]

Guidelines

Please note that GitHub issues are only meant for bug reports/feature requests. If you have questions on how to use Neo4j, please ask on StackOverflow instead of creating an issue here.

Before creating a new issue, please check whether someone else has raised the same issue. You may be able to add context to that issue instead of duplicating the report. However, each issue should also only be focussed on a single problem, so do not describe new problems within an existing thread - these are very hard to track and manage, and your problem may be ignored. Finally, do not append comments to closed issues; if the same problem re-occurs, open a new issue, and include a link to the old one.

To help us understand your issue, please specify important details, primarily:

• Neo4j version: 5.18.0

• Operating system: MacOS, Docker DeskTop, image:neo4j:5.18.0

• API/Driver: Cypher

• Steps to reproduce

  1. create graph command:

     CREATE (c:Node {name: "liming"})
     WITH [{name:"youxue-0"},{name:"youxue-1"}] AS upNode UNWIND upNode AS per CREATE (n:Node) SET n = per
     CREATE (c:Node {name: "final"})
     WITH [{startName: "liming", endName: "youxue-0", cost:2},{startName: "youxue-0", endName: "youxue-1", cost:2},{startName: "youxue-1", endName: "final", cost:2}] AS relationships UNWIND relationships AS rel MATCH (start:Node {name: rel.startName}), (end:Node {name: rel.endName}) CREATE (start)-[:ROAD {cost:rel.cost}]->(end)
     WITH [{name:"cw-0"}] AS upNode UNWIND upNode AS per CREATE (n:Node) SET n = per
     WITH [{startName: "liming", endName: "cw-0", cost:2},{startName: "cw-0", endName: "final", cost:2}] AS relationships UNWIND relationships AS rel MATCH (start:Node {name: rel.startName}), (end:Node {name: rel.endName}) CREATE (start)-[:ROAD {cost:rel.cost}]->(end)
     WITH [{name:"yiyun-0"},{name:"yiyun-1"},{name:"yiyun-2"},{name:"yiyun-3"}] AS upNode UNWIND upNode AS per CREATE (n:Node) SET n = per
     WITH [{startName: "liming", endName: "yiyun-0", cost:1},{startName: "yiyun-0", endName: "yiyun-1", cost:1},{startName: "yiyun-1", endName: "yiyun-2", cost:1},{startName: "yiyun-2", endName: "yiyun-3", cost:1},{startName: "yiyun-3", endName: "final", cost:1}] AS relationships UNWIND relationships AS rel MATCH (start:Node {name: rel.startName}), (end:Node {name: rel.endName}) CREATE (start)-[:ROAD {cost:rel.cost}]->(end)
     WITH [{name:"rock-0"}] AS upNode UNWIND upNode AS per CREATE (n:Node) SET n = per
     WITH [{startName: "liming", endName: "rock-0", cost:1},{startName: "rock-0", endName: "final", cost:1}] AS relationships UNWIND relationships AS rel MATCH (start:Node {name: rel.startName}), (end:Node {name: rel.endName}) CREATE (start)-[:ROAD {cost:rel.cost}]->(end)

  2. use GDS gds.shortestPath.yens.stream algorithm

     CALL gds.graph.project(
     'yoGraph',
     'Node',
     'ROAD',
     {
     relationshipProperties: 'cost'
     }
     )
     MATCH (source:Node {name: 'liming'}), (target:Node {name: 'final'})
     CALL gds.shortestPath.yens.stream('myGraph', {
     sourceNode: source,
     targetNode: target,
     k: 3,
     relationshipWeightProperty: 'cost'
     })
     YIELD index, sourceNode, targetNode, totalCost, nodeIds, costs, path
     WHERE SIZE(costs) < 5
     RETURN
     index,
     gds.util.asNode(sourceNode).name AS sourceNodeName,
     gds.util.asNode(targetNode).name AS targetNodeName,
     totalCost,
     [nodeId IN nodeIds | gds.util.asNode(nodeId).name] AS nodeNames, 
     costs,
     nodes(path) as path

• Expected behavior I hope get 3 records.

  ╒═════╤══════════════╤══════════════╤═════════╤═══════════════════════════════════════════╤════════════════════╤══════════════════════════════════════════════════════════════════════╕
  │index│sourceNodeName│targetNodeName│totalCost│nodeNames                                  │costs               │path                                                                  │
  ╞═════╪══════════════╪══════════════╪═════════╪═══════════════════════════════════════════╪════════════════════╪══════════════════════════════════════════════════════════════════════╡
  │0    │"liming"      │"final"       │2.0      │["liming", "rock-0", "final"]              │[0.0, 1.0, 2.0]     │[(:Node {name: "liming"}), (:Node {name: "rock-0"}), (:Node {name: "fi│
  │     │              │              │         │                                           │                    │nal"})]                                                               │
  ├─────┼──────────────┼──────────────┼─────────┼───────────────────────────────────────────┼────────────────────┼──────────────────────────────────────────────────────────────────────┤
  │1    │"liming"      │"final"       │4.0      │["liming", "cw-0", "final"]                │[0.0, 2.0, 4.0]     │[(:Node {name: "liming"}), (:Node {name: "cw-0"}), (:Node {name: "fina│
  │     │              │              │         │                                           │                    │l"})]                                                                 │
  ├─────┼──────────────┼──────────────┼─────────┼───────────────────────────────────────────┼────────────────────┼──────────────────────────────────────────────────────────────────────┤
  │3    │"liming"      │"final"       │6.0      │["liming", "youxue-0", "youxue-1", "final"]│[0.0, 2.0, 4.0, 6.0]│[(:Node {name: "liming"}), (:Node {name: "youxue-0"}), (:Node {name: "│
  │     │              │              │         │                                           │                    │youxue-1"}), (:Node {name: "final"})]                                 │
  └─────┴──────────────┴──────────────┴─────────┴───────────────────────────────────────────┴────────────────────┴──────────────────────────────────────────────────────────────────────┘

• Actual behavior just got 2 records, But I expect 3.

  ╒═════╤══════════════╤══════════════╤═════════╤═════════════════════════════╤═══════════════╤══════════════════════════════════════════════════════════════════════╕
  │index│sourceNodeName│targetNodeName│totalCost│nodeNames                    │costs          │path                                                                  │
  ╞═════╪══════════════╪══════════════╪═════════╪═════════════════════════════╪═══════════════╪══════════════════════════════════════════════════════════════════════╡
  │0    │"liming"      │"final"       │2.0      │["liming", "rock-0", "final"]│[0.0, 1.0, 2.0]│[(:Node {name: "liming"}), (:Node {name: "rock-0"}), (:Node {name: "fi│
  │     │              │              │         │                             │               │nal"})]                                                               │
  ├─────┼──────────────┼──────────────┼─────────┼─────────────────────────────┼───────────────┼──────────────────────────────────────────────────────────────────────┤
  │1    │"liming"      │"final"       │4.0      │["liming", "cw-0", "final"]  │[0.0, 2.0, 4.0]│[(:Node {name: "liming"}), (:Node {name: "cw-0"}), (:Node {name: "fina│
  │     │              │              │         │                             │               │l"})]                                                                 │
  └─────┴──────────────┴──────────────┴─────────┴─────────────────────────────┴───────────────┴──────────────────────────────────────────────────────────────────────┘

chatGPT mentioned that in older versions, you can limit the number of hops through "maxDepth" in the "algo.kShortestPaths" algorithm. But in the latest version of the documentation, I didn't find the relevant parameters in the related algorithms such as "gds.shortestPath.yens.stream", so do you have any other suggestions?

[IoannisPanagiotas]

Hi @xiaoxlm,

What. you describe. happens because of the fact that there are four possible paths with distances 2, 4, 5, 6. Since you specified k with 3, Yens will find the first three. Now the tlast path has size 5 so it is pruned afterwards which is an operation that happens after the algorithm has finished.

Currently there is no internal possibility to define maxDepth. I am not sure whether it existed and was removed at some point. We wil mark the feature request and possibly work on it at some point, though I cannot promise you anything for the moment.

For the moment, I think you could try to raise k to a larger value (for example here instead of 3 to 4 would bring you the answer you wanted) and apply the same filtering you have applied with the size of the cost array. As this will generate more paths, it is more likely to find all the paths with the size requirement you want.

I will close this for now, Let me know if you have any other question.

Best Ioannis.