Source: https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/k_hop/
Documentation version: v5.3.2

# K-Hop

## Algorithm introduction

K-hop traversal enumerates nodes reachable within at most K edges from a source node.

Return the deduplicated exact k-hop reachable nodes from source_id in a directed graph whose node primary key is id. Nodes reached within fewer than k hops are excluded.

For more information, see [K-Hop](https://en.wikipedia.org/wiki/Breadth-first_search).

## Data model

To implement the K-Hop algorithm in GQL, the following data model is used to create a graph type:

- Entities are represented by nodes of type `Node`, with properties `id` and `rating`.
- Relationships are represented by edges of type `Link`, with property `weight`.

For the complete definition of the graph type, see [Prepare graph data](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/k_hop/#1_prepare_graph_data).

## Procedure implementation[]()

To compute K-Hop results, a [procedure](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/procedures/create/) is created.

For more information about the procedure, see [Procedure implementation](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/k_hop/#procedure_implement). The following section describes the key components of the procedure and how it works.

The procedure takes the following input parameters:

- `source_id`: `INT64`. ID of the source node to expand from.
- `k`: `INT64`. Maximum number of hops from the source node.

Additionally, the following variables are defined within the procedure:

 | Variable name | Variable type | Description
 | `frontier` | [Primitive value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/value-variable/) | Active set of nodes in the current hop layer.
 | `step` | [Primitive value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/value-variable/) | Current hop count from the source node.
 | `has_next` | [Primitive value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/value-variable/) | Whether the current frontier expanded to new nodes.
 | `result_ids` | Global [SumAgg aggregator value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | Accumulated list of visited node IDs across all hops.
 | `visited` | Node-attached [SumAgg aggregator value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | Per-node flag: node has been reached.

The following steps outline the logic of the procedure:

1. Initialize the source node as `visited`; add it to `result_ids` and set it as the initial `frontier`.
2. For each hop step up to `k`, expand the `frontier`: find all unvisited neighbors, mark them `visited`, add to `result_ids`, and set as the new `frontier`.
3. Stop when `has_next` is false (no new nodes reached) or `step` equals `k`.
4. Return the list of all visited node IDs within k hops.

## Steps

Run the following code blocks in order in the NebulaGraph Studio CONSOLE. For first-time setup, follow [Prepare algorithm sample data](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/prepare-data/) to check where to run commands and how the directory is mounted.

### 1. Prepare graph data[]()

1. 

Create a graph type that matches your data model.

````
'''
CREATE GRAPH TYPE IF NOT EXISTS k_hop_graph_type AS {
    NODE Node (LABEL Node {id INT PRIMARY KEY, rating INT}),
    EDGE Link (Node)-[LABEL Link {weight INT, MULTIEDGE KEY()}]->(Node)
}
'''

````

2. 

Download these CSV files and save them with their original names in `examples/algorithms/k_hop/` under your deployment directory:

  - [k_hop_node.csv](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/files/k_hop/k_hop_node.csv): Node data.
  - [k_hop_edge.csv](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/files/k_hop/k_hop_edge.csv): Edge data.

Preview the CSV files

k_hop_node.csv

````
id,rating
1,0
2,2
3,1
4,0
5,0
6,2
7,1
8,2
9,0
10,1
11,0
12,2
13,1
14,1
15,0
16,2
17,0
18,1
19,2
20,0
21,2
22,1
23,0
24,1

````

k_hop_edge.csv

````
src_id,dst_id,weight
1,2,4
1,3,2
1,4,7
1,5,9
2,3,1
2,4,6
2,5,5
2,6,2
3,4,3
3,5,4
3,6,8
4,6,2
4,7,6
4,8,5
5,6,4
5,8,7
5,9,6
6,8,1
6,9,5
6,10,6
7,9,2
7,10,9
8,9,3
8,11,6
8,12,4
9,10,4
9,12,7
9,13,2
10,12,1
10,13,8
10,14,4
11,12,2
11,14,5
11,15,7
12,14,3
12,15,6
12,16,5
13,15,2
13,16,7
14,15,4
14,17,8
14,18,2
15,16,1
15,18,5
15,19,3
16,18,3
16,19,6
17,18,2
17,20,7
17,21,5
18,19,4
18,21,9
18,22,6
19,21,1
19,22,5
20,21,3
20,23,6
20,24,8
21,22,2
21,23,4
21,24,7
22,24,4
23,24,1

````

3. 

Create a temporary graph based on the graph type and load the data files into the temporary graph.

````
CREATE TEMPORARY GRAPH IF NOT EXISTS #k_hop_graph TYPED k_hop_graph_type

````

````
'''
USE #k_hop_graph IMPORT INTO GRAPH {
      NODE (v@Node {id: id, rating: rating}) FROM DATAFILE {
          PATH: "file:///examples/algorithms/k_hop/k_hop_node.csv",
          FORMAT: "CSV",
          DELIMITER: ','
      },
      EDGE (id: src_id)-[e@Link {weight: weight}]->(id: dst_id) FROM DATAFILE {
          PATH: "file:///examples/algorithms/k_hop/k_hop_edge.csv",
          FORMAT: "CSV",
          DELIMITER: ','
      }
  }
'''

````

After the import succeeds, run this query in the console to check the node count:

````
'''
USE #k_hop_graph
MATCH (n)
RETURN count(n) AS node_count
'''

````

The expected `node_count` is `24`. If it differs, [check the files and import results](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/prepare-data/#troubleshooting) before continuing.

### 2. Create a procedure[]()

Create a procedure to implement the K-Hop algorithm. For more information about the procedure, see [Procedure implementation](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/k_hop/#procedure_implement). 

````
'''
CREATE OR REPLACE PROCEDURE k_hop(source_id INT64, k INT64)
RETURNS (vertex_ids LIST<INT64>)
COMMENT "Return the deduplicated exact k-hop reachable vertices from source_id in a directed graph whose vertex primary key is id. Vertices reached within fewer than k hops are excluded."
AS {
  VALUE frontier ACTIVE_SET

  VALUE step INT64 = 0
  VALUE has_next OrAgg = false
  VALUE result_ids ListAgg<INT64>

  NODE VALUE visited OrAgg = false

  MATCH (s)
  WHERE s.id = source_id
  PER NODE (s) {
    SET s.@visited = true
  }
  FINALLY {
    SET frontier = s
  }

  WHILE step < k THEN {
    SET @has_next = false
    SET step = step + 1

    MATCH (s)-[e]->(t)
    WHERE s IN frontier AND t.@visited = false
    PER PATH {
      SET t.@visited += true
      SET @has_next += true
    }
    FINALLY {
      SET frontier = t
    }

    IF @has_next = false THEN {
      BREAK
    }
  }

  IF step = k THEN {
    MATCH (n)
    WHERE n IN frontier
    PER NODE (n) {
      SET @result_ids += n.id
    }
  }

  RETURN @result_ids AS vertex_ids
}
'''

````

### 3. Call your procedure[]()

Expand from node `1` and return the IDs visited within at most `2` hops.

````
USE #k_hop_graph CALL k_hop(1, 2) RETURN vertex_ids

````

Returns:

````
+--------------+
| vertex_ids   |
+--------------+
| [7, 8, 9, 6] |
+--------------+

````

Save results to a file or graph

To save the returned results as CSV files or write them to a graph, see [EXPORT](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/in-out/export/). Match the exported fields to the returned columns and target properties.