Weakly Connected Components

A weakly connected component (WCC) in a directed graph is a maximal subgraph where any two vertices are connected to each other by some path, regardless of edge direction.

Kuzu implements a parallelized version of the WCC algorithm based on Ligra.

Syntax

CALL weakly_connected_components(
    graph_name,
    maxIterations := 100
)
RETURN node, group_id

Alias: wcc

Parameters

Parameter	Type	Optional	Default	Description
graph_name	STRING	No	-	Name of the projected graph to run the algorithm on
maxIterations	INT64	Yes	100	Maximum number of iterations to run

Return

Column	Type	Description
node	NODE	Node object
group_id	INT64	The ID of the WCC that the node belongs to

Example

Define schema

CREATE NODE TABLE Person(name STRING PRIMARY KEY);
CREATE REL TABLE KNOWS(FROM Person to Person);

Insert nodes and edges

CREATE (u0:Person {name: 'Alice'}),
        (u1:Person {name: 'Bob'}),
        (u2:Person {name: 'Charlie'}),
        (u3:Person {name: 'Derek'}),
        (u4:Person {name: 'Eve'}),
        (u5:Person {name: 'Frank'}),
        (u6:Person {name: 'George'}),
        (u7:Person {name: 'Hina'}),
        (u8:Person {name: 'Ira'}),
        (u0)-[:KNOWS]->(u1),
        (u1)-[:KNOWS]->(u2),
        (u5)-[:KNOWS]->(u4),
        (u6)-[:KNOWS]->(u4),
        (u6)-[:KNOWS]->(u5),
        (u6)-[:KNOWS]->(u7),
        (u7)-[:KNOWS]->(u4),
        (u6)-[:KNOWS]->(u5);

We first create a projected graph from the node and edge tables.

CALL project_graph('Graph', ['Person'], ['KNOWS']);

Then, you can run WCC as follows:

CALL weakly_connected_components('Graph')
RETURN group_id, collect(node.name)
ORDER BY group_id;

┌──────────┬─────────────────────────┐
│ group_id │ COLLECT(node.name)      │
│ INT64    │ STRING[]                │
├──────────┼─────────────────────────┤
│ 0        │ [Derek]                 │
│ 1        │ [Ira]                   │
│ 2        │ [Bob,Charlie,Alice]     │
│ 5        │ [George,Frank,Hina,Eve] │
└──────────┴─────────────────────────┘

Frequently asked questions

How is group_id assigned?

group_id is assigned based on Kuzu’s internal node offsets. Currently there is no way to assign group_id based on node properties.