兩組節點的交集（neo4j密碼遍歷路徑）

Question

我有一個100000個節點通過關係相互連接的圖形。 從點A到點B，只有一條可能的路徑，在我的模型中不可能有環路。

我要尋找一個解決方案，將指示節點列表的路徑是否與第二節點列表

我並不需要知道的交集點，如果有一個路口的道路相交。

是否有可能有一個解決方案，而不通過整個圖（停止一旦找到第一個節點）？

例如：picture of graph

節點1的列表：紅色節點的節點2的

列表：藍色節點

至於有至少一個交叉點（黑節點），該請求必須返回true 。

暗號要求：

編輯：CYPHER要求

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; 

Answer 1

由於沒有任何一對節點之間只有一個可能的路徑，我覺得你的圖是一棵樹，你可以選擇任意節點成爲那棵樹的根。

完成此操作後，線性時間預處理工作允許您在常量時間內回答最低的共同祖先查詢，並且任何兩個節點之間的路徑由樹狀結構到其最低共同祖先的路徑組成，其後是下降樹的路徑。我們把這個峯稱爲路徑兩端的最低共同祖先 - 路徑的最低共同祖先。

如果單個節點N在路徑上，那麼該節點的最低共同祖先和該路徑的最低共同祖先是該路徑的最低共同祖先，並且該節點的最低共同祖先和其中一個路徑的末端是節點N.此外，如果這兩者都成立，則節點N位於路徑的最低公共祖先和路徑的一端之間的某處，因此它位於路徑上 - 並且您已找到這在O（1）時間。

如果兩條路徑相交，具有最低共同祖先的路徑必須在另一條路徑上具有該祖先，否則它將完全在另一條路徑下面 - 而上面的段落顯示瞭如何在時間O（1）無論任意節點是否在路徑上，所以我們可以通過查看任一路徑的最低公共祖先是否在另一路徑上來檢查路徑交叉。

Answer 2

要將一組路徑合併到一個節點池中，可以使用UNWIND n + COLLECT（DISTINCT n）。這裏是你如何調整你的示例查詢。

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; 

當然，在你的情況下，如果路徑相交，那麼存在一個從紅色到紅色和藍色的路徑。到目前爲止，更簡單地

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