ArangoDB: Holen Sie sich jeden Knoten, der in irgendeiner Weise mit einem ausgewählten Knoten verwandt ist

Question

Ich habe ein einfaches Knoten-Links-Diagramm in ArangoDB. Wie kann ich von einem vorausgewählten Knoten aus verfahren und alle damit verbundenen Knoten zurückgeben?

Zum Beispiel: A → B, B → C, C → D, C → E, F → B, F → E

Auswahl einer von ihnen soll das gleiche Ergebnis (alle) zurückzukehren.

Ich bin sehr neu in ArangoDB.

Answer 1

Was Sie brauchen, ist AQL graph traversal, verfügbar seit ArangoDB 2.8. Ältere Versionen stellten eine Reihe von graphbezogenen Funktionen zur Verfügung, aber die native AQL-Traversierung ist schneller, flexibler und die Grafikfunktionen sind ab 3.0 nicht mehr verfügbar.

---

AQL Traversal lassen Sie Kanten folgen zu einem Startknoten verbunden ist, bis zu einer variablen Tiefe. Auf jeden angetroffenen Eckpunkt kann zugegriffen werden, z. Zum Filtern oder Konstruieren eines Ergebnisses, sowie der Kante, die Sie zu diesem Scheitelpunkt geführt hat, und dem vollständigen Pfad von Anfang bis Ende einschließlich der Scheitelpunkte und Kanten.

In Ihrem Fall müssen nur die Namen der besuchten Scheitelpunkte zurückgegeben werden. Sie können die folgenden AQL-Abfragen ausführen, vorausgesetzt, es ist eine Dokumentensammlung node und eine Kante Sammlung links und sie enthalten die Daten für dieses Diagramm:

// follow edges ("links" collection) in outbound direction, starting at A 
FOR v IN OUTBOUND "node/A" links 
    // return the key (node name) for every vertex we see 
    RETURN v._key 

Dieses nur [ "B" ] zurückkehren, weil die Traversal Tiefe ist implizit 1..1 (min = 1, max = 1). Wenn wir die maximale Tiefe erhöhen, dann können wir Knoten enthalten, die indirekt verbunden sind, wie auch:

FOR v IN 1..10 OUTBOUND "node/A" links 
    RETURN v._key 

Dies wird uns [ "B", "C", "D", "E"]. Wenn wir uns den Graphen ansehen, ist das richtig: Wir folgen nur Kanten, die von dem Scheitelpunkt, von dem wir kommen, auf einen anderen Scheitelpunkt zeigen (Richtung des Pfeils). Um das Gegenteil zu tun, könnten wir INBOUND, verwenden Sie aber in Ihrem Fall wollen wir die Richtung der Kante ignorieren und folgen trotzdem:

FOR v IN 1..10 ANY "node/A" links 
    RETURN v._key 

Das Ergebnis könnte zunächst ein wenig überraschend sein:
[ "B", "C", "D", "E", "F", "B", "F", "E", "C", "D", "B" ]

Wir sehen doppelte Knoten zurückgegeben. Der Grund ist, dass es beispielsweise mehrere Pfade von A nach C gibt (über B und auch über B-F-E), und die Abfrage gibt den letzten Knoten jedes Pfades als Variable v zurück. (Es ist nicht wirklich verarbeiten alle möglichen Pfade bis zur maximalen Tiefe von 10, aber man konnte die Traversal Option OPTIONS {uniqueEdges: "none"} tun so eingestellt.)

Es kann helfen, formatiert Traversal Pfade zurückzukehren, besser zu verstehen, was ist geht (dh, wie Knoten erreicht werden):

FOR v, e, p IN 1..10 ANY "node/A" links OPTIONS {uniqueEdges: "path"} 
    RETURN CONCAT_SEPARATOR(" - ", p.vertices[*]._key) 

Ergebnis:

[ 
    "A - B", 
    "A - B - C", 
    "A - B - C - D", 
    "A - B - C - E", 
    "A - B - C - E - F", 
    "A - B - C - E - F - B", 
    "A - B - F", 
    "A - B - F - E", 
    "A - B - F - E - C", 
    "A - B - F - E - C - D", 
    "A - B - F - E - C - B" 
] 

Es gibt einen Zyklus in der Grafik, aber es kann nicht eine unendliche Schleife sein, da die maximale Tiefe nach hinten überschritten wird Er 10 Hopfen.Aber wie Sie oben sehen können, erreicht es nicht einmal die Tiefe von 10, es stoppt vielmehr, weil die (Standard) -Option ist, Kanten nicht zweimal pro Pfad zu folgen (uniqueEdges: "path").

Wie auch immer, das ist nicht das gewünschte Ergebnis. Ein billiger Trick wäre, RETURN DISTINCT, COLLECT oder etwas ähnliches zu verwenden, um Duplikate zu entfernen. Aber wir sind besser daran, die Traversaloptionen zu optimieren, um Kanten nicht unnötig zu folgen.

uniqueEdges: "global" würde immer noch den B-Knoten zweimal enthalten, aber uniqueVertices: "global" gibt das gewünschte Ergebnis. Außerdem kann in diesem Fall bfs: true für die Breitensuche verwendet werden. Der Unterschied besteht darin, dass der Pfad zum F-Knoten kürzer ist (A-B-F anstelle von A-B-C-E-F). Im Allgemeinen hängen die genauen Optionen, die Sie verwenden sollten, weitgehend von dem Datensatz und den Fragen ab, die Sie haben.

Es gibt ein weiteres Problem zu lösen: Die Traversierung enthält nicht den Startknoten (anders als in p.vertices[0] für jeden Pfad). Dies kann leicht gelöst werden, indem ArangoDB 3.0 oder später durch die minimale Tiefe auf 0 setzen:

FOR v IN 0..10 ANY "node/A" links OPTIONS {uniqueVertices: "global"} 
    RETURN v._key 

[ "A", "B", "C", "D", "E", "F" ]

Um sicherzustellen, dass alle Knoten von A bis F zurückgegeben werden, unabhängig von dem Anfangsknoten, können wir geben Sie die folgende Testabfrage ein:

FOR doc IN node 
    RETURN (
     FOR v IN 0..10 ANY doc links OPTIONS {uniqueVertices: "global"} 
      SORT v._key 
      RETURN v._key 
    ) 

Alle Sub-Arrays sollten gleich aussehen. Entfernen Sie die SORT-Operation, wenn Sie möchten, dass die Knotennamen in umgekehrter Reihenfolge zurückgegeben werden. Hoffe das hilft =)