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

# Strong Connected Component

## Algorithm introduction

Strongly connected component identifies maximal subgraphs where every node is reachable from every other node.

Compute classic strongly connected components on a directed graph by transitive reachability closure plus mutual-reachability component propagation.

For more information, see [Strong Connected Component](https://en.wikipedia.org/wiki/Strongly_connected_component).

## Data model

To implement the Strong Connected Component 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/strong_connected_component/#1_prepare_graph_data).

## Procedure implementation[]()

To compute Strong Connected Component 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/strong_connected_component/#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
 | `vertex_ids` | Global [SumAgg aggregator value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | List of all node IDs for the outer pivot iteration.
 | `k_idx` | [Primitive value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/value-variable/) | Index into vertex_ids for the current outer loop iteration.
 | `mid_id` | [Primitive value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/value-variable/) | Current pivot node ID for SCC forward/backward reachability.
 | `round` | [Primitive value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/value-variable/) | Current outer-loop round counter.
 | `max_round` | [Primitive value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/value-variable/) | Maximum allowed outer-loop rounds (safety limit).
 | `changed` | [Primitive value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/value-variable/) | Whether the reachability set changed in the current round.
 | `k_reach` | Global [SumAgg aggregator value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | Global set of nodes reachable from (and to) the current pivot.
 | `reach` | 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 nodes reachable from this node.
 | `component` | 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 minimum ID among all reachable nodes (used as SCC label).
 | `result_table` | [Table variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/table-variable/) | Output table storing (vertex_id, component_id) pairs.

The following steps outline the logic of the procedure:

1. Iterate over all nodes as pivots; for each pivot, compute the set of nodes reachable from it and that can reach it back.
2. Nodes in this mutual reachability set form one SCC; label them with the minimum ID in the set.
3. Remove the identified SCC nodes from further processing and repeat until all nodes are assigned.
4. Return (`vertex_id`, `component_id`) for all nodes.

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

  - [strong_connected_component_node.csv](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/files/strong_connected_component/strong_connected_component_node.csv): Node data.
  - [strong_connected_component_edge.csv](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/files/strong_connected_component/strong_connected_component_edge.csv): Edge data.

Preview the CSV files

strong_connected_component_node.csv

````
id,rating
1,0
2,0
3,0
4,0
5,0
6,0
7,0
8,0

````

strong_connected_component_edge.csv

````
src_id,dst_id,weight
1,2,1
2,3,1
3,1,1
3,4,1
4,5,1
5,4,1
5,6,1
6,7,1
7,6,1
7,8,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 #strong_connected_component_graph TYPED strong_connected_component_graph_type

````

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

````

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

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

````

The expected `node_count` is `8`. 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 Strong Connected Component algorithm. For more information about the procedure, see [Procedure implementation](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/strong_connected_component/#procedure_implement). 

````
'''
CREATE OR REPLACE PROCEDURE strong_connected_component()
RETURNS (vertex_id INT64, component_id INT64)
COMMENT "Compute classic strongly connected components on a directed graph by transitive reachability closure plus mutual-reachability component propagation."
AS {
  VALUE vertex_ids ListAgg<INT64>
  VALUE k_idx INT64 = 0
  VALUE mid_id INT64 = 0
  VALUE round INT64 = 0
  VALUE max_round INT64 = 256
  VALUE changed OrAgg = true
  VALUE k_reach SetAgg<INT64>

  NODE VALUE reach SetAgg<INT64>
  NODE VALUE component MinAgg<INT64> = 9223372036854775807

  TABLE result_table TYPED TABLE {
    vertex_id INT64,
    component_id INT64
  }

  MATCH (n)
  PER NODE (n) {
    SET @vertex_ids += n.id
    SET n.@reach.clear()
    SET n.@reach += n.id
    SET n.@component = n.id
  }

  MATCH (s)-[e]->(t)
  PER PATH {
    SET s.@reach += t.id
  }

  WHILE k_idx < @vertex_ids.size() THEN {
    SET mid_id = @vertex_ids[k_idx]
    SET k_idx = k_idx + 1
    SET @k_reach.clear()

    MATCH (k)
    WHERE k.id = mid_id
    PER NODE (k) {
      SET @k_reach += k.@reach
    }

    MATCH (s)
    WHERE s.@reach.contains_key(mid_id)
    PER NODE (s) {
      SET s.@reach += @k_reach
    }
  }

  WHILE @changed AND round < max_round THEN {
    SET @changed = false
    SET round = round + 1

    MATCH (s)-[e]->(t)
    WHERE s.@reach.contains_key(t.id) AND t.@reach.contains_key(s.id)
    PER PATH {
      VALUE min_component INT64 = s.@component

      IF t.@component < min_component THEN {
        SET min_component = t.@component
      }

      IF min_component < s.@component THEN {
        SET s.@component += min_component
        SET @changed += true
      }

      IF min_component < t.@component THEN {
        SET t.@component += min_component
        SET @changed += true
      }
    }
  }

  MATCH (n)
  PER NODE (n) {
    EXPORT n.id, n.@component INTO result_table
  }

  FOR r IN result_table
  RETURN r.vertex_id AS vertex_id, r.component_id AS component_id
  ORDER BY component_id ASC, vertex_id ASC
}
'''

````

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

Compute strongly connected components and return each node's component ID.

````
USE #strong_connected_component_graph CALL strong_connected_component() RETURN vertex_id, component_id

````

Returns:

Expand to view results

````
+-----------+--------------+
| vertex_id | component_id |
+-----------+--------------+
| 1         | 1            |
| 2         | 1            |
| 3         | 1            |
| 4         | 4            |
| 5         | 4            |
| 6         | 6            |
| 7         | 6            |
| 8         | 8            |
+-----------+--------------+

````

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.