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

# Triangle Count

## Algorithm introduction

Triangle count computes the number of closed triplets in the graph and can be used to estimate clustering strength.

Count the number of undirected triangles in a graph whose node primary key is id.

For more information, see [Triangle Count](https://en.wikipedia.org/wiki/Triangle-free_graph).

## Data model

To implement the Triangle Count 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/triangle_count/#1_prepare_graph_data).

## Procedure implementation[]()

To compute Triangle Count 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/triangle_count/#procedure_implement). The following section describes the key components of the procedure and how it works.

The procedure takes the following input parameters:

- This procedure does not require input parameters.

Additionally, the following variables are defined within the procedure:

 | Variable name | Variable type | Description
 | `total` | Global [SumAgg aggregator value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | Global accumulator for the total triangle count.
 | `fwd` | 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 set of neighbor IDs with a larger ID (used for triangle intersection).

The following steps outline the logic of the procedure:

1. For each edge (s, t) where s.id < t.id, add t.id to s's `fwd` neighbor set.
2. For each edge (s, t) where s.id < t.id, check each node u in t's `fwd` set; if u is also in s's `fwd` set, increment `total`.
3. Each common entry represents a closed triangle; the count is divided by 1 (already deduplicated by the ID ordering).
4. Return the total triangle count.

## 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 triangle_count_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/triangle_count/` under your deployment directory:

  - [triangle_count_node.csv](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/files/triangle_count/triangle_count_node.csv): Node data.
  - [triangle_count_edge.csv](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/files/triangle_count/triangle_count_edge.csv): Edge data.

Preview the CSV files

triangle_count_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

````

triangle_count_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 #triangle_count_graph TYPED triangle_count_graph_type

````

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

````

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

````
'''
USE #triangle_count_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 Triangle Count algorithm. For more information about the procedure, see [Procedure implementation](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/triangle_count/#procedure_implement). 

````
'''
CREATE OR REPLACE PROCEDURE triangle_count()
RETURNS (triangle_count INT64)
COMMENT "Count the number of undirected triangles in a graph whose vertex primary key is id."
AS {
  VALUE total SumAgg<INT64> = 0

  NODE VALUE fwd SetAgg<INT64>

  MATCH (s)-[e]-(t)
  WHERE s.id < t.id
  PER PATH {
    SET s.@fwd += t.id
  }

  MATCH (s)-[e]-(t)
  WHERE s.id < t.id
  PER PATH {
    VALUE idx INT64 = 0
    VALUE candidate_id INT64 = 0

    WHILE idx < t.@fwd.size() THEN {
      SET candidate_id = t.@fwd[idx]
      IF s.@fwd.contains_key(candidate_id) THEN {
        SET @total += 1
      }
      SET idx = idx + 1
    }
  }

  RETURN @total AS triangle_count
}
'''

````

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

Count the triangles in the sample graph.

````
USE #triangle_count_graph CALL triangle_count() RETURN triangle_count

````

Returns:

````
+----------------+
| triangle_count |
+----------------+
| 47             |
+----------------+

````

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.