Vue d’ensemble

La clause k-hop khop().src().depth() récupère les nodes voisins qu'un node peut atteindre en K sauts (à travers K arêtes) les plus courts. Ces voisins sont communément appelés les voisins k-hop du node source.

Le voisin k-hop est l'un des concepts fondamentaux de la théorie des graphes. Dans le graphe ci-dessus, les nodes B, C et D sont les voisins à 1 saut du node A, les nodes E, F et G sont les voisins à 2 sauts du node A, et le node H est le voisin à 3 sauts du node A.

La valeur de k est unique et dépend de la longueur des chemins les plus courts entre deux nodes. Par exemple, bien qu'il existe de nombreux chemins entre les nodes A et C (A-C, A-D-C, A-D-E-C), la distance la plus courte est 1. Le node C ne devrait pas apparaître dans les résultats autres que les voisins à 1 saut.

Les résultats des requêtes k-hop sont dédupliqués. Par exemple, il existe deux chemins les plus courts entre les nodes A et E, mais E devrait n'apparaître qu'une seule fois dans la requête à 2 sauts du node A.

La requête k-hop d'Ultipa adopte la technique de parcours BFS pour trouver les chemins les plus courts et les voisins k-hop. Des optimisations ont été appliquées pour améliorer la performance de la requête k-hop. Il est recommandé d'utiliser la requête k-hop au lieu d'autres méthodes de requête de chemin pour cet objectif.

Syntaxe

• Alias de la clause : type NODE
• Méthodes :

L'exclusion de certains nodes ou arêtes via node_filter() ou edge_filter() pourrait induire un changement structurel au graphe, influençant potentiellement les résultats de la requête. Voir les exemples sous Filtrage de Nœud et Filtrage d'Arête.

Exemples

Exemple de Graphe

Exécutez ces UQLs ligne par ligne dans un graphset vide pour créer ce graphe :

create().edge_property(@default, "weight", int32)
insert().into(@default).nodes([{_id:"A", _uuid:1}, {_id:"B", _uuid:2}, {_id:"C", _uuid:3}, {_id:"D", _uuid:4}, {_id:"E", _uuid:5}, {_id:"F", _uuid:6}])
insert().into(@default).edges([{_uuid:1, _from_uuid:1, _to_uuid:3, weight:1}, {_uuid:2, _from_uuid:5, _to_uuid:2 , weight:1}, {_uuid:3, _from_uuid:1, _to_uuid:5 , weight:4}, {_uuid:4, _from_uuid:4, _to_uuid:3 , weight:2}, {_uuid:5, _from_uuid:5, _to_uuid:4 , weight:3}, {_uuid:6, _from_uuid:2, _to_uuid:1 , weight:2}, {_uuid:7, _from_uuid:6, _to_uuid:1 , weight:4}])

Définir la Profondeur

Trouver les voisins à 3 sauts du node D.

khop().src({_id == "D"}).depth(3) as n
return n{*}

Résultat :

Trouver les voisins de 1 à 3 sauts du node D.

khop().src({_id == "D"}).depth(:3) as n
return n{*}

Résultat :

Retourner le Nœud Source

Trouver les voisins de 1 à 2 sauts du node D. Retourner en même temps le node D.

khop().src({_id == "D"}).depth(0:2) as n
return n{*}

Résultat :

Filtrage de Nœud

Trouver les voisins à 3 sauts du node D en excluant le node E.

khop().src({_id == "D"}).depth(3).node_filter({_id != "E"}) as n
return n{*}

Résultat :

Lorsque le node E (et ses arêtes adjacentes) est exclu, le node B devient le voisin à 3 sauts du node D.

Filtrage d'Arête

Trouver les voisins à 3 sauts du node D en excluant l'arête 5.

khop().src({_id == "D"}).depth(3).edge_filter({_uuid != 5}) as n
return n{*}

Résultat :

Lorsque l'arête 5 est exclue, les nodes E et B deviennent les voisins à 3 sauts du node D.

Définir la Direction de l'Arête

Trouver les voisins de 1 à 2 sauts du node D tout en s'assurant que toutes les arêtes traversées pointent vers la droite.

khop().src({_id == "D"}).depth(:2).direction(right) as n
return n{*}

Résultat :

Utiliser l'Alias dans src()

Trouver les voisins à 1 saut des nodes D et F.

find().nodes({_id in ["D", "F"]}) as start
khop().src(start).depth(1).direction(right) as n
return table(start._id, n._id)

Résultat :

Utiliser limit()

Trouver trois voisins de 1 à 3 sauts du node D.

khop().src({_id == "D"}).depth(:3).limit(3) as n
return n{*}

Résultat :

La clause k-hop renvoie les nodes voisins dans l'ordre du plus proche au plus éloigné, en commençant par 1-saut, suivi de 2-sauts, puis 3-sauts.

Utiliser OPTIONAL

Trouver les voisins à 2 sauts des nodes A et D tout en s'assurant que toutes les arêtes traversées pointent vers la droite. Retourner null si aucun voisin n'est trouvé.

find().nodes({_id in ["A", "D"]}) as start
optional khop().src(start).depth(2).direction(right) as n
return table(start._id, n._id)

Résultat :