weakly_connected_components

The first analysis that is most often run on a graph is usually a search for disconnected components. The algorithm implemented within this module does exactly that, it searches for different components of the graph. Within components, nodes have connections toward each other, while between components there is no edge that connects nodes from separate components.

Trait	Value
Module type	algorithm
Implementation	C++
Graph direction	undirected
Edge weights	unweighted
Parallelism	sequential

Procedures

info

If you want to execute this algorithm on graph projections, subgraphs or portions of the graph, be sure to check out the guide on How to run a MAGE module on subgraphs.

get()

Output:

• node ➡ Vertex object with all properties which is going to be related to the component ID it belongs.
• component_id ➡ Component ID for each node in the graph. Components are zero-indexed and there is no rule of how they will be appointed to node. The only guarantee is that divided components will have distinct component IDs.

Usage:

CALL weakly_connected_components.get()
YIELD node, component_id;

Example

Step 1: Input graph

Step 2: Cypher load commands

MERGE (a:Node {id: 0}) MERGE (b:Node {id: 1}) CREATE (a)-[:RELATION]->(b);
MERGE (a:Node {id: 1}) MERGE (b:Node {id: 2}) CREATE (a)-[:RELATION]->(b);
MERGE (a:Node {id: 2}) MERGE (b:Node {id: 0}) CREATE (a)-[:RELATION]->(b);
MERGE (a:Node {id: 3}) MERGE (b:Node {id: 3}) CREATE (a)-[:RELATION]->(b);
MERGE (a:Node {id: 3}) MERGE (b:Node {id: 4}) CREATE (a)-[:RELATION]->(b);
MERGE (a:Node {id: 3}) MERGE (b:Node {id: 5}) CREATE (a)-[:RELATION]->(b);

Step 3: Running command

CALL weakly_connected_components.get()
YIELD node, component_id
RETURN node, component_id;

Step 4: Results

+-----------------+-----------------+
| node            | component_id    |
+-----------------+-----------------+
| (:Node {id: 5}) | 1               |
| (:Node {id: 4}) | 1               |
| (:Node {id: 3}) | 1               |
| (:Node {id: 2}) | 0               |
| (:Node {id: 0}) | 0               |
| (:Node {id: 1}) | 0               |
+-----------------+-----------------+