Determine the next relationships on the graph Path Finding

[ardan7779]

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]

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

[ardan7779]

Thanks for your answer. I prefer need to the second answer that i don't know where is the best relationship.

But, I have try to implement your algorithm to my graph but until now still get some error null return like this. What I Missed..?

{
"statement": {
"text": "MATCH (a:lokasi {nama:'Terminal Batu'}), (b:lokasi {nama:'Terminal Gadang Malang'})\nWITH a, b, [(a)-[r]-() | r.id] as aIds, [(a)-[r]-() | b.id] as bIds\nWITH a, b, apoc.coll.intersection(aIds, bIds) as ids\nUNWIND ids as id\nMATCH path = shortestPath((a)--(b))\nWHERE all(rel in relationships(path) WHERE rel.id = id)\nRETURN path\nORDER BY length(path) DESC\nLIMIT 1",
"parameters": {}
},
"statementType": "r",
"counters": {
"_stats": {
"nodesCreated": 0,
"nodesDeleted": 0,
"relationshipsCreated": 0,
"relationshipsDeleted": 0,
"propertiesSet": 0,
"labelsAdded": 0,
"labelsRemoved": 0,
"indexesAdded": 0,
"indexesRemoved": 0,
"constraintsAdded": 0,
"constraintsRemoved": 0
}
},
"updateStatistics": {
"_stats": {
"nodesCreated": 0,
"nodesDeleted": 0,
"relationshipsCreated": 0,
"relationshipsDeleted": 0,
"propertiesSet": 0,
"labelsAdded": 0,
"labelsRemoved": 0,
"indexesAdded": 0,
"indexesRemoved": 0,
"constraintsAdded": 0,
"constraintsRemoved": 0
}
},
"plan": false,
"profile": false,
"notifications": ,
"server": {
"address": "localhost:7687",
"version": "Neo4j/3.5.0"
},
"resultConsumedAfter": {
"low": 1,
"high": 0
},
"resultAvailableAfter": {
"low": 3,
"high": 0
}
}

[andrew_bowman · Accepted solution]

That's likely my fault, there's a flaw in the query I gave you when calculating the ids to use. Here's a fixed version:

MATCH (a:Node {name:'A'}), (b:Node {name:'B'})
WITH a, b, [(a)-[r]-() | r.id] as aIds, [(b)-[r]-() | r.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

[ardan7779]

Thanks, The query works!