Comment suivre un cycle une seule fois?

Question

Je suis un nouvel utilisateur ArangoDB et j'ai un problème que je ne sais pas comment le résoudre. J'ai un graphique composé de plus de 340k nœuds et de plus de 430k liens avec des cycles et j'essaie de trouver un chemin entre A et B. Je sais avec certitude que dans le chemin entre ces 2 nœuds je rencontrerai des boucles donc j'ai utilisé l'option followCycles. Comme une requête que j'utilise quelque chose:

FOR target, unused, path IN 1..150 OUTBOUND "A" connected OPTIONS {followCycles: True, uniqueEdges: "none"} FILTER target._id == "B" LIMIT 1 RETURN path

OMI cette requête devrait me revenir ce chemin entre A et B considérant également la boucle. Malheureusement cette requête n'est pas capable de trouver le chemin et elle tourne "pour toujours" à cause de la dimension du graphique.

De toute façon, j'ai remarqué que si j'utilise un nœud intermédiaire, je suis capable de trouver le chemin. Je l'ai fait quelque chose comme:

FOR target, unused, path IN 1..150 OUTBOUND "A" connected OPTIONS {followCycles: True, uniqueEdges: "none"} FILTER target._id == "intermediate" LIMIT 1 RETURN path

FOR target, unused, path IN 1..150 OUTBOUND "intermediate" connected OPTIONS {followCycles: True, uniqueEdges: "none"} FILTER target._id == "B" LIMIT 1 RETURN path Je soupçonne qu'en raison des boucles ne suffit pas la valeur 150, j'ai essayé aussi avec 15000 mais j'ai eu le même résultat. Savez-vous s'il existe une option permettant de dire de parcourir une boucle une seule fois ou quoi que ce soit d'autre afin d'éviter le problème?

Merci

Answer 1

Si vous cherchez seulement pour tout chemin entre A et B la requête suivante devrait fonctionner pour vous.

FOR target, unused, path IN 1..150 OUTBOUND "myCollection/A" connected 
OPTIONS {uniqueVertices: "global", bfs: true} 
    FILTER target._id == "myCollection/B" 
    LIMIT 1 
    RETURN path 

Avec uniqueVertices: "global" chaque sommet (noeud) n'est visité une fois pendant la traversée. Ce qui signifie que les boucles ne sont pas suivies. Avec bfs: true, vous utilisez l'algorithme breadth-first. Ce qui signifie que la traversée parcourt d'abord tous les sommets trouvés de profondeur 1 puis 2 et ainsi de suite. L'utilisation de ceci vous permet de trouver un chemin plus court en évitant de suivre un chemin jusqu'à ce que votre profondeur maximale (150) soit atteinte pour réaliser qu'il n'y a pas de chemin connecté.

Pour plus d'informations sur la traversée de graphe AQL, consultez le docs.