weakly_connected_components

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.

TraitValue
Module typealgorithm
ImplementationC++
Graph directionundirected
Edge weightsunweighted
Parallelismsequential

Procedures

get()

Use the procedure to get disconnected componentes.

Input:

  • subgraph: Graph (OPTIONAL) ➡ A specific subgraph, which is an object of type Graph returned by the project() function, on which the algorithm is run.

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:

Run the following query to get disconnected components:

CALL weakly_connected_components.get()
YIELD node, component_id;

Example

Database state

The database contains the following data:

Created with the following Cypher queries:

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);

Analyze graph

Get weekly connected components by running the following query:

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

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