2組のノードの交差点（neo4j cypher traversal path）

Question

私は100000ノードのグラフを関係で接続しています。 ポイントAからポイントBまで、可能なパスは1つしかありません。私のモデルではループは不可能です。

私は、ノードのリストのパスは、第2ノードのリスト私は交差点がある場合、交点を知っている必要はありません

のパスと交差するかどうかを示します解決策を探しています。

グラフ全体（最初のノードが見つかると停止します）を経由しないで解決することは可能でしょうか？

例：赤ノードのノード2の

リスト：ノード1のpicture of graph

リストブルーノード

を少なくとも一つの交差点（黒のノード）が存在するように、要求がtrueを返す必要があります。

サイファー要求：

EDIT：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

ノードの任意のペア間の唯一の可能な経路があるので、私はあなたのグラフが木であると思うし、あなたが任意のノードを選択することができますその木の根になる

これを実行すると、線形時間の前処理作業によって、一定の時間内に最も一般的な祖先クエリに答えることができます。また、2つのノード間のパスは、ツリーを最も低い共通祖先木を下る道。パスの2つの端の最も低い共通の祖先であるこのピークを、パスの最も低い共通の祖先と呼ぶことにしましょう。

単一のノードNがパス上にある場合、そのノードの最も低い共通祖先とそのパスの最も低い共通祖先は、パスの最も低い共通祖先であり、そのノードの最も低い共通祖先であり、ノードNは、ノードNです。さらに、これらの両方が保持されている場合、ノードNはパスの最下位共通祖先とパスの端の1つの間にあるため、パス上にあります。これはO（1）時間内に行われます。

2つのパスが交差する場合、最も共通の祖先を持つパスは、もう一方のパスにその祖先を持たなければなりません。まったく別のパスの下にあります。上の段落は時間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