biconnected_components

Finding biconnected components means finding a maximal biconnected subgraph. Subgraph is biconnected if:

• It is possible to go from each node to another within a biconnected subgraph
• First scenario remains true even after removing any vertex in the subgraph

The algorithm works by finding articulation points, and then traversing from these articulation points toward other nodes, which all together form one biconnected component.

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:

• bcc_id ➡ Biconnected component identifier. There is no order of nodes within one biconnected component.
• node_from ➡ First node of an edge contained in biconnected component.
• node_to ➡ Second node of an edge contained in biconnected component

Usage:

CALL biconnected_components.get()
YIELD bcc_id, node_from, node_to;

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: 1}) MERGE (b:Node {id: 3}) CREATE (a)-[:RELATION]->(b);
MERGE (a:Node {id: 2}) MERGE (b:Node {id: 3}) CREATE (a)-[:RELATION]->(b);
MERGE (a:Node {id: 2}) MERGE (b:Node {id: 4}) CREATE (a)-[:RELATION]->(b);
MERGE (a:Node {id: 3}) MERGE (b:Node {id: 4}) CREATE (a)-[:RELATION]->(b);
MERGE (a:Node {id: 1}) MERGE (b:Node {id: 5}) CREATE (a)-[:RELATION]->(b);
MERGE (a:Node {id: 0}) MERGE (b:Node {id: 6}) CREATE (a)-[:RELATION]->(b);
MERGE (a:Node {id: 5}) MERGE (b:Node {id: 6}) CREATE (a)-[:RELATION]->(b);
MERGE (a:Node {id: 5}) MERGE (b:Node {id: 7}) CREATE (a)-[:RELATION]->(b);
MERGE (a:Node {id: 5}) MERGE (b:Node {id: 8}) CREATE (a)-[:RELATION]->(b);
MERGE (a:Node {id: 7}) MERGE (b:Node {id: 8}) CREATE (a)-[:RELATION]->(b);
MERGE (a:Node {id: 8}) MERGE (b:Node {id: 9}) CREATE (a)-[:RELATION]->(b);
MERGE (a:Node {id: 10}) MERGE (b:Node {id: 11}) CREATE (a)-[:RELATION]->(b);

Step 3: Running command

CALL biconnected_components.get()
YIELD bcc_id, node_from, node_to
WITH bcc_id, node_from, node_to
MATCH (node_from)-[edge]-(node_to)
RETURN bcc_id, edge, node_from, node_to;

Step 4: Results

+------------------+------------------+------------------+------------------+
| bcc_id           | edge             | node_from        | node_to          |
+------------------+------------------+------------------+------------------+
| 0                | [:RELATION]      | (:Node {id: 2})  | (:Node {id: 4})  |
| 0                | [:RELATION]      | (:Node {id: 3})  | (:Node {id: 4})  |
| 0                | [:RELATION]      | (:Node {id: 1})  | (:Node {id: 3})  |
| 0                | [:RELATION]      | (:Node {id: 2})  | (:Node {id: 3})  |
| 0                | [:RELATION]      | (:Node {id: 1})  | (:Node {id: 2})  |
| 1                | [:RELATION]      | (:Node {id: 8})  | (:Node {id: 9})  |
| 2                | [:RELATION]      | (:Node {id: 5})  | (:Node {id: 8})  |
| 2                | [:RELATION]      | (:Node {id: 7})  | (:Node {id: 8})  |
| 2                | [:RELATION]      | (:Node {id: 5})  | (:Node {id: 7})  |
| 3                | [:RELATION]      | (:Node {id: 0})  | (:Node {id: 6})  |
| 3                | [:RELATION]      | (:Node {id: 5})  | (:Node {id: 6})  |
| 3                | [:RELATION]      | (:Node {id: 1})  | (:Node {id: 5})  |
| 3                | [:RELATION]      | (:Node {id: 0})  | (:Node {id: 1})  |
| 4                | [:RELATION]      | (:Node {id: 10}) | (:Node {id: 11}) |
+------------------+------------------+------------------+------------------+