Den längsten Zweig eines Baumes in Neo4j finden

Question

Ich habe derzeit eine nur angehängte Baumdatenstruktur in Java. Der Hauptzweck dieses Baums besteht darin, einen Zeiger auf den längsten Zweig zu halten. Ich habe dies implementiert, indem ich einen Verweis auf die letzten Knoten in den längsten Zweigen habe, die beim Einfügen neuer Knoten in den Baum aktualisiert werden.

Aus Performance- und Persistenzgründen möchte ich diese Implementierung mithilfe der Neo4j-Java-API zu Neo4j verschieben. Beim Durcharbeiten der Dokumente konnte ich keine praktische Lösung finden, um eine Neo4j-Datenbank für den längsten Zweig abzufragen. In meiner Implementierung kann ich versichern, dass der Graph ein n-ary-Baum ist.

Was ist die bevorzugte Lösung in Neo4j, um den längsten Ast in einem solchen Baum zu finden?

• einen Zeiger auf die letzten Knoten beibehalten, wie ich es in meiner Java-Implementierung mache?
• einen Algorithmus formulieren, um den längsten Pfad zu finden und dies mit der Traversal-API oder über eine Abfrage von Chiffren zu implementieren?
• einige eingebaute Funktionalität in Neo4j, die ich noch nicht gefunden habe?

Answer 1

Es gibt keine eingebaute Funktion zum Suchen eines längsten Pfades.

Eine Möglichkeit, es zu finden, ist, den gesamten Pfad zwischen dem Wurzelknoten und den Blattknoten zu finden und sie dann nach Länge desc zu sortieren. und nimm den ersten.

MATCH (root:Root)-[:HAS_CHILD*]->(n:Node) 
WHERE size((n)-[:HAS_CHILD]->())=0 
RETURN n 
ORDER BY size(RELS(p)) DESC 
LIMIT 1 

Ein besserer Ansatz ist zu berechnen all jene Pfade mit einem Traversal in einer gemeinsamen Aktion:

In cypher sollte es ähnlich wie mit etwas getan werden. Sie können einen Blick auf APOC mit dem apoc.path.expand Verfahren werfen. Aufführungen werden besser sein.

Letzte Lösung, erstellen Sie Ihre eigenen Algo mit einem benutzerdefinierten Traversal, die einen Zweig zurückschneiden, wenn Sie bereits eine längste gefunden haben. (Es kann mit einem benutzerdefinierten Evaluator getan werden). Diese Algo wird eine bessere durchschnittliche Leistung als die vorherige Lösung haben, aber im schlimmsten Fall ist die Komplexität die gleiche.

Wie Sie gesagt haben, können Sie einen Zeiger auf diesen Knoten halten. Es wird sehr schnell sein, um es zu suchen, aber Sie müssen diesen Zeiger beibehalten, wenn ein Schreibvorgang in Ihrem Baum ausgeführt wird (mit einer Auswirkung auf die Schreibleistung).

Die Wahl liegt bei Ihnen und hängt von den Leistungen ab, die Sie für das Lesen und Schreiben erreichen möchten.

Prost