Determine the next relationships on the graph Path Finding

shortest-path
path

(Ardan7779) #1

I Need to determine the next relationship from my graph thats have many path from node A to node B.

I tried to implement the shortest agorithm, but i haven't find the algorithm to determine the next relation. For example, i want to go from A to B, and it return many path thats can solve the trip, but i need to know the path that's the relationships inside it is same by id, so from A to B the best path that's have relations with same IDs,.

Can anyone help me..?
I'm sorry if my english not so good. Thanks


(Andrew Bowman) #2

You'll want to use the shortestPath() function in your MATCH, and supply the id for all relationships in the match. Here's one way, assuming you already have the id you want to use for all relationships in the path (we'll assume we're passing it in as an $id parameter):

MATCH (a:Node {name:'A'}), (b:Node {name:'B'})
MATCH path = shortestPath((a)-[*]-(b))
WHERE all(rel in relationships(path) WHERE rel.id = $id)
RETURN path

If you don't know the id ahead of time, then in order for the ids to be evaluated during expansion of the shortestPath, we need to get the ids ahead of time. This will require matching to the ids of relationships connected to a and b and getting the intersection (so we don't chase relationships where we know the id isn't used for the last hop to the end node), and for each of those ids do a shortestPath() then take the shortest of all those paths.

MATCH (a:Node {name:'A'}), (b:Node {name:'B'})
WITH a, b, [(a)-[r]-() | r.id] as aIds, [(a)-[r]-() | b.id] as bIds
WITH a, b, apoc.coll.intersection(aIds, bIds) as ids
UNWIND ids as id
MATCH path = shortestPath((a)-[*]-(b))
WHERE all(rel in relationships(path) WHERE rel.id = id)
RETURN path
ORDER BY length(path) DESC
LIMIT 1