Cypher für alle Pfade zwischen zwei Knoten

Question

Ich habe ein Diagramm mit Millionen von Knoten und Beziehungen. Ich muss alle Pfade zwischen zwei Knoten bekommen. In meinem Fall müssen alle Knoten in Relationspfaden gleichen Labels sein

meine Abfrage so;

match (n:Label) match (m:Label) where n.NAME='foo' and m.NAME='foo2' 
match p=(n)-[r*..20]-(m) where all(x in nodes(p) where (x:Label)) 
with p 
return p, EXTRACT(x IN nodes(p) | x.NAME), EXTRACT(r IN relationships(p) | type(r)) 

Knoten mit dem Label „Label“ zählen etwa 20, aber diese Abfrage Verfahrweg in allen Graphen alle möglichen Pfade zwischen zwei Knoten zu finden und dann reduzieren versuchen, Wege mit meinem „wo alle“ -Klausel. Es stürzt dann meine db ab.

Ich brauche alle Knoten mit Label-Name "Label" und ihre Beziehungen, dann Abfragen Pfade zwischen Subgraph, um Kosten zu reduzieren.

Answer 1

Es gibt eine Reihe von Path Expander APOC-Prozeduren, die hilfreich sein können, da viele Ihnen erlauben, einen Label-Filter beim Erzeugen von Pfaden anzugeben.

Zum Beispiel:

MATCH (n:Label {NAME: 'foo'}) 
WITH COLLECT(n) AS ns1 
MATCH (m:Label {NAME: 'foo2'}) 
WITH ns1 + COLLECT(m) AS startNodes 
CALL apoc.path.expandConfig(
    startNodes, 
    {labelFilter: '+Label', minLevel: 1, maxLevel: 20} 
) YIELD path 
RETURN 
    path, 
    [x IN nodes(path) | x.NAME] AS names, 
    [r IN relationships(path) | TYPE(r)] AS types; 

Answer 2

Des Versuch, alle möglichen Wege zu finden (auch wenn bis zu einer Länge von 20) in einem Graphen von Millionen von Knoten wahrscheinlich einen Speicherüberlauf verursachen.

Was Sie tun können, ist es in kleinere Segmente zu zerlegen. Die Abfrage wird nicht so elegant sein, aber es sollte funktionieren.

Zum Beispiel, wenn wir eine Weglänge von 5 zu einem Zeitpunkt zu tun, eine Zwei-Segment-Abfrage wird wie folgt aussehen:

MATCH p1 = (n1:Label)-[r1*..5]-(n2:Label), p2 = (n2:Label)-[r2*..5]-(n3:Label) 
WHERE all(x1 in nodes(p1) WHERE (x1:Label)) 
AND all(x2 in nodes(p2) WHERE (x2:Label)) 
RETURN r1, r2 

Der Kostenplan für diese Abfrage sieht so aus:

+-----------------------+----------------------+---------------------+ 
| Operator    | Variables   | Other    | 
+-----------------------+----------------------+---------------------+ 
| +ProduceResults  | r1     | r1     | 
| |      +----------------------+---------------------+ 
| +Filter    | n1, n2, n3, r1, r2 | [see below]   | 
| |      +----------------------+---------------------+ 
| +VarLengthExpand(All) | n1, r1 -- n2, n3, r2 | (n2)-[r1:*..5]-(n1) | 
| |      +----------------------+---------------------+ 
| +Filter    | n2, n3, r2   | n3:Label   | 
| |      +----------------------+---------------------+ 
| +VarLengthExpand(All) | n3, r2 -- n2   | (n2)-[r2:*..5]-(n3) | 
| |      +----------------------+---------------------+ 
| +NodeByLabelScan  | n2     | :Label    | 
+-----------------------+----------------------+---------------------+ 

So können Sie sehen, dass direkt nach der ersten Erweiterung ein Filter alle Pfade filtern wird, die nicht beginnen und enden mit :Label und erst dann wird die zweite Erweiterung passieren.

So lange Ihre Neo-Version ist 2.2 oder höher, p1 und p2will not include the same relationships.

Sie können tatsächlich diese Filterung im Filter vor der ProduceResults Operator (zweite Zeile) getan sehen:

all(x1 in NodesFunction(ProjectedPath(Set(r1, n1),)) where x1:Label) 
AND none(r1 in r1 where any(r2 in r2 where r1 == r2)) 
AND n1:Label 

Jetzt sollten Sie auch sehen, dass die wir nur für alle Knoten im Pfad überprüfen auf dem letzten Filter . Ein Pfad wie dieser: (a: Label) - (b: Blah) - (c: Label) wird immer über das erste Segment hinausgehen und nur vor der Ergebnisproduktion gefiltert werden.

So können Sie weiter optimieren, indem Sie überprüfen, dass alle Segmentknoten :Label haben, und dann eine manuelle Überprüfung auf Beziehung ähnlich früheren Beziehungen vornehmen. Nur die zweite Stufe zeigt:

WITH n2, r1 
MATCH p2 = (n2:Label)-[r2*..5]-(n3:Label) 
WHERE all(x2 in nodes(p2) WHERE (x2:Label)) 
AND none(r1 in r1 where any(r2 in r2 where r1 == r2)) 

ich vergaß zu erwähnen, aber denken Sie daran, dass Anfragen als solche in einem faulen Weise ausgeführt werden.