neo4j - shortest path with conditions include plugin functions

Question

I have a problem with the implementation in cypher. My problem is this: I have a database model, which is photographed here as an overview: https://www.instpic.de/QTIhBbPgVHBHg5pKwVdk.PNG Short for the explanation. The red nodes simulate star systems, the yellow one jump points. Each jump point has a certain size, which determines which body can pass the point. The size is stored as a property at the relation between the yellow nodes. Among the red nodes are other nodes that represent the orbital celestial bodies of a star system. (Planets, moons, stations, etc.) Now, from any point within a solar system (planet, station, moon), I would like to find the shortest path to another lying point in the same solar system or another. In addition, I can calculate the distance of two celestial bodies within a system using the plugin that I have programmed. This value should now be included in finding the path, so I have the shortest path on the database and also the smallest distance between the celestial bodies within a solar system. I already have a query, unfortunately it fails partly because of its performance. I also think that the paths here are very variable, so a change to the database model is well considered.

Here is a part of my acutal query iam using:

MATCH (origin:Marketplace)
               WHERE origin.eid = 'c816c4fa501244a48292f5d881103d7f'
               OPTIONAL MATCH (marketplace:Marketplace)-[:Sell]->(currentPrice:Price)-[:Content]->(product:Product)
               OPTIONAL MATCH p = shortestPath((origin)-[:HasMoon|:HasStation|:HasLandingZone|:HasPlanet|:HasJumpPoint|:CanTravel*]-(marketplace))
               WHERE SIZE([rel in relationships(p) WHERE EXISTS(rel.size)]) <= 3 AND ALL(rel IN [rel in relationships(p) WHERE EXISTS(rel.size)] WHERE rel.size IN ['small', 'medium', 'large'])
               WITH origin, marketplace, p, currentPrice, product
               CALL srt.getRoutes(origin, marketplace, p) YIELD node, jump_sizes, jump_gates, jump_distance, hops, distance
               OPTIONAL MATCH (currentPrice)-[:CompletedVotes]->(:Wrapper)-[:CompletedVote]->(voteHistory:CompletedVote)
               OPTIONAL MATCH (currentPrice)-[:CurrentVote]->(vote:Vote)-[:VotedPrices]->(currentVotings)
               WITH node, currentPrice, product, jump_sizes, jump_gates, jump_distance, hops, distance, voteHistory, currentVotings, vote, origin
               WITH {eid: product.eid, displayName: product.displayName, name: product.name, currentPrice: {eid: currentPrice.eid, price: currentPrice.price}, currentVoting: {approved: vote.approved, count: Count(currentVotings), declined: vote.declined, users: Collect(currentVotings.userId), votes: Collect(currentVotings.price), voteAvg: round(100 * avg(currentVotings.price)) / 100}, voteHistory: Collect({votings: voteHistory.votings, users: voteHistory.users, completed: voteHistory.completed, 
               vote: voteHistory.votes}), marketplace: {eid: node.eid, name: node.name, type: node.type, designation: node.designation}, travel: {jumpSizes: jump_sizes, jumpGate: jump_gates, jumpDistance: jump_distance, jumps: hops, totalDistance: distance}} as sellOptions, currentPrice ORDER BY currentPrice.price
               WITH Collect(sellOptions) as sellOptions

For the moment, this query works pretty well, but now I want to filter (after ".... dium ',' large '])" -> line 5) the minimum total distance you need to travel to reach your destination , I would like to realize this with my written plugin, which calculates the total distance in the path (getTotalDistance (path AS PATH))

For additional: when I cut of 'big' from the possible jump sizes, I get no result, but there is still a path in my graph that leads me to the goal.

For additional 2: iam working on neo4j 3.3.1 and i have set these config:

cypher.forbid_shortestpath_common_nodes=false

which not works in 3.3.3

EIDT 1: (More detailed explanation)

I have a place where I am. Then I search for marketplaces that sell some product. For this I can specify further filters. I can e.g. say that I can travel only through jump points of the size "large". Also, I only want marketplaces that are 4 system away.

Now, looking in the database for the above restrictions, I search for the shortest path to the market places I found. It may well be that I have several paths that meet the conditions. If this is the case, I would like to filter out of all the shortest paths, the one in which one has to overcome the smallest distance within each solar system.

Is that accurate enough? Otherwise, please just report.

You could write all your distance you calculate with you plugin on the edges and just use or modify the shortestpath algorithms from the apoc procedures. Did you already try this? Or do you have a reason not to use this? Are the distance variable? — Yoshi
If I'm reading this correctly, you're looking for a more performant shortestPath? Can you verbally describe in more detail the requirements for this, aside from the size restriction? It looks like you're looking to limit the number of jumps in the path? Also, why is the size on the relationship rather than the jumppoint nodes? — InverseFalcon
Can you also PROFILE this query and add the query plan (with all elements expanded)? We might find something to optimize. There's likely at least one major cardinality issue that's slowing this down. — InverseFalcon
Another observation...each pair of adjacent jump points has two relationships between them, one in each direction (and likely of the same type). Is that needed, some difference in the attributes on the relationships, or some pairs where only one relationship will be present instead of both? If not, you might consider refactoring so that only a single relationship exists between each jump point pair. — InverseFalcon
I'll go through all the comments today, here's the Query Plan in advance: instpic.de/KmItH20rwZN9F01dxY8p.png — Cavez

InverseFalcon InverseFalcon · Accepted Answer · 2018-03-18T19:54:42

The latest APOC releases may be able to help here, though the APOC path expanders work best with labels and relationship types, so a slight change to your model may be needed.

In particular, the size of your jump points. Right now this is a property on the relationships between them, but for APOC to work optimally, these might be better modeled with the size as a label on the :JumpPoint nodes themselves, so you might have :JumpPoint:Small, :JumpPoint:Medium, and :JumpPoint:Large (you can add this in addition to the rel properties if you like).

Keep in mind this approach will be more complex than shortestPath(), as the idea is we're trying to find systems within a certain number of jumps, then find :Marketplaces reachable at those star systems, then filter based on whether they sell the product we want, and we'll stitch the path together as we find the pieces.

MATCH localSystemPath = (origin:Marketplace)-[*]-(s:Solarsystem)
WHERE origin.eid = $originId
WITH origin, localSystemPath, s
LIMIT 1
WITH origin, localSystemPath, s, 
 CASE WHEN coalesce($maxJumps, -1) = -1 
      THEN -1, 
      ELSE 3*$maxJumps 
 END as maxJumps,
 CASE $shipSize 
  WHEN 'small' THEN '' 
  WHEN 'medium' THEN '|-Small' 
  ELSE '|-Small|-Medium' 
 END as sizeBlacklist
CALL apoc.path.spanningTree(s, 
 {relationshipFilter:'HasJumpPoint|CanTravel>', maxLevel:maxJumps, 
 labelFilter:'>Solarsystem' + sizeBlacklist, filterStartNode:true}) YIELD path as jumpSystemPath
WITH origin, localSystemPath, jumpSystemPath, length(jumpSystemPath) / 3 as jumps, last(nodes(jumpSystemPath)) as destSystem
MATCH destSystemPath = (destSystem)-[*]-(marketplace:Market)
WHERE none(rel in relationships(destSystemPath) WHERE type(rel) = 'HasJumpPoint')
AND <insert predicate for filtering which :Markets you want>
WITH origin, apoc.path.combine(apoc.path.combine(localSystemPath, jumpSystemPath), destSystemPath) as fullPath, jumps, destSystem, marketplace
CALL srt.getRoutes(origin, marketplace, fullPath) YIELD node, jump_sizes, jump_gates, jump_distance, hops, distance
...

This assumes parameter inputs of $shipSize for the minimum size of all jump gates to pass through, $originId as the id of the origin :Marketplace (plus you DEFINITELY need an index or unique constraint on :Marketplace(eid) for fast lookups here), and $maxJumps, for the maximum number of jumps to reach a destination system.

Keep in mind the expansion procedure used, spanningTree(), will only find the single shortest path to another system. If you need all possible paths, including multiple paths to the same system, then change the procedure to expandConfig() instead.

neo4j - shortest path with conditions include plugin functions

1 Answers