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.

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.

Procedure implementation ¶

To compute Strong Connected Component results, a procedure is created.

For more information about the procedure, see Procedure implementation. 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	List of all node IDs for the outer pivot iteration.
`k_idx`	Primitive value variable	Index into vertex_ids for the current outer loop iteration.
`mid_id`	Primitive value variable	Current pivot node ID for SCC forward/backward reachability.
`round`	Primitive value variable	Current outer-loop round counter.
`max_round`	Primitive value variable	Maximum allowed outer-loop rounds (safety limit).
`changed`	Primitive value variable	Whether the reachability set changed in the current round.
`k_reach`	Global SumAgg aggregator value variable	Global set of nodes reachable from (and to) the current pivot.
`reach`	Node-attached SumAgg aggregator value variable	Per-node set of nodes reachable from this node.
`component`	Node-attached SumAgg aggregator value variable	Per-node minimum ID among all reachable nodes (used as SCC label).
`result_table`	Table variable	Output table storing (vertex_id, component_id) pairs.

The following steps outline the logic of the procedure:

Iterate over all nodes as pivots; for each pivot, compute the set of nodes reachable from it and that can reach it back.
Nodes in this mutual reachability set form one SCC; label them with the minimum ID in the set.
Remove the identified SCC nodes from further processing and repeat until all nodes are assigned.
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 to check where to run commands and how the directory is mounted.

1. Prepare graph data ¶

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)
}
'''

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: Node data.
- 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
```

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 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.

'''
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. Match the exported fields to the returned columns and target properties.

Strong Connected Component¶

Algorithm introduction¶

Data model¶

Procedure implementation¶

Steps¶

1. Prepare graph data¶

2. Create a procedure¶

3. Call your procedure¶

Procedure implementation ¶

1. Prepare graph data ¶

2. Create a procedure ¶

3. Call your procedure ¶