K-Hop

Overview

The k-hop clause khop().src().depth() retrieves the neighbor nodes a node can reach in K hops (through K edges) the shortest. These neighbors are commonly referred to as the k-hop neighbors of the source node.

K-hop neighbor is one of the fundamental concepts in graph theory. In the graph above, nodes B, C and D are the 1-hop neighbors of node A, nodes E, F and G are the 2-hop neighbors of node A, and node H is the 3-hop neighbor of node A.

The value of k is unique and depends on the length of the shortest paths between two nodes. For example, although there are many paths exist between nodes A and C (A-C, A-D-C, A-D-E-C), the shortest distance is 1. Node C shouldn't appear in the results other than 1-hop neighbors.

The results of k-hop queries are deduplicated. For example, there are two shortest paths exist between nodes A and E, but E should only appear once in the 2-hop query of node A.

Ultipa's k-hop query adopts the BFS traversal technique to find the shortest paths and the k-hop neighbors. Optimizations have been applied to improve the performance of the k-hop query. It's recommended to use the k-hop query instead of other path query methods for the same purpose.

Syntax

• Clause alias: NODE type
• Methods:

NOTE

The exclusion of certain nodes or edges through node_filter() or edge_filter() might induce structural change to the graph, potentially influencing the query outcomes. See examples under Node Filtering and Edge Filtering.

Examples

Example Graph

Run these UQLs row by row in an empty graphset to create this graph:

UQL
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}])
Click to expand

Set Depth

Find the 3-hop neighbors of node D.

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

Result:

Find 1-hop to 3-hop neighbors of node D.

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

Result:

Return Source Node

Find the 1- to 2-hop neighbors of node D. Return node D at the same time.

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

Result:

Node Filtering

Find the 3-hop neighbors of node D while excluding node E.

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

Result:

When node E (and its adjacent edges) is excluded, node B becomes the 3-hop neighbor of node D.

Edge Filtering

Find the 3-hop neighbors of node D while excluding edge 5.

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

Result:

When edge 5 is excluded, node E and B become the 3-hop neighbor of node D.

Set Edge Direction

Find the 1- to 2-hop neighbors of node D while ensuring that all edges that pass through point to the right.

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

Result:

Call Alias in src()

Find the 1-hop neighbors of nodes D and F.

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

Result:

Use limit()

Find three 1- to 3-hop neighbors of node D.

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

Result:

The k-hop clause returns neighbor nodes in order from nearest to farthest, starting with 1-hop, followed by 2-hop, and then 3-hop.

Use OPTIONAL

Find the 2-hop neighbors of nodes A and D while ensuring that all edges that pass through point to the right. Return null if no neighbors are found.

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

Result: