intersection of two set of nodes (neo4j cypher traversal path)

0
votes

I have a graph of 100000 nodes connected to each other by a relation. From a point A to a point B, there is only one possible path, no loop is possible in my model.

I am looking for a solution that will indicate whether the path of a list of nodes intersects with the path of a second node list

I do not need to know the intersection points if there is an intersection.

Would it be possible to have a solution without going through the whole graph (stop once the first node is found) ?

example : picture of graph

list of nodes 1 : red nodes

list of nodes 2 : blue nodes

As there is at least one intersection(black node), the request must return true.

cypher request :

EDIT : cypher request

match path=shortestPath((n1)-[r*]-(n2))
where id(n1) = node1 and id(n2) in nodesList1
with nodes(path) as nodespath1

match path=shortestPath((n1)-[r*]-(n2))
where id(n1) = node2 and id(n2) in nodesList2
with nodespath1, nodes(path) as nodespath2

with ANY (n IN nodespath1 WHERE n IN nodespath2) AS conflit
with ANY (n IN collect(conflit) WHERE n = true) AS conflit
RETURN conflit;
2
neo4jcyphertraversal
What does "the path of a list of nodes" mean? Do you mean "all the paths between all possible pairs of nodes taken from a list", or "any path between all possible pairs of nodes taken from a list", or "all paths that include every node from a list", or something else? – cybersam
the path of a list of nodes means the shortestopath between all pairs of nodes from list (there is only one possible path) – gsaad

2 Answers

1
votes

Since there is only one possible path between any pair of nodes, I think your graph is a tree, and you can pick an arbitrary node to be the root of that tree.

Once you have done this, linear time pre-processing work allows you to answer lowest common ancestor queries in constant time, and the path between any two nodes consists of a path ascending the tree to their lowest common ancestor, followed by a path descending the tree. Let's call this peak - the lowest common ancestor of the two ends of the path - the lowest common ancestor of the path.

If a single node N is on a path, the lowest common ancestor of that node and the lowest common ancestor of that path is the lowest common ancestor of the path, and the lowest common ancestor of that node and one of the ends of the path is that node N. Furthermore, if both of these things hold, node N is somewhere between the lowest common ancestor of the path and one of the ends of the path, so it is on the path - and you have found this out in O(1) time.

If two paths intersect, the path with lowest common ancestor must have that ancestor on the other path, or it would be entirely below the other path - and the paragraph just above shows how to work out in time O(1) whether an arbitrary node is on a path, so we can check for path intersections by looking to see if the lowest common ancestor of either path is on the other path.

1
votes

To consolidate a set of paths into a pool of nodes, you can use UNWIND n + COLLECT(DISTINCT n). Here is how you would adjust your sample query.

match path=shortestPath((n1)-[r*]-(n2))
where id(n1) = node1 and id(n2) in nodesList1
UNWIND nodes(path) as nodespath1
WITH collect(DISTINCT nodespath1) as nodespath1

match path=shortestPath((n1)-[r*]-(n2))
where id(n1) = node2 and id(n2) in nodesList2
UNWIND nodes(path) as nodespath2
WITH nodespath1, collect(DISTINCT nodespath2) as nodespath2

with ANY (n IN nodespath1 WHERE n IN nodespath2) AS conflict
RETURN conflict;

Of course, in your case, if the paths intersect, then a path exists from a red to a red and a blue. So far more simply

MATCH (a), (b)
WHERE id(a) in nodesList1 AND id(b) in nodesList2
// Match a c node in path to an a and a b node
MATCH (a)-[*]-(c)-[*]-(a2), (b)-[*]-(c)-[*]-(b2)
WHERE id(a2) in nodesList1 AND id(b2) in nodesList2
WITH c
LIMIT 1
RETURN (COUNT(c) == 1) as conflict