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,
the first scenario remains true even after removing any node from 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.

Source code

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

Procedures

You can execute this algorithm on graph projections, subgraphs or portions of the graph.

`get()`

The procedure finds biconnected components.

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. If subgraph is not specified, the algorithm is computed on the entire graph by default.

Output:

bcc_id: integer ➡ Biconnected component identifier. There is no order of nodes within one biconnected component.
node_from: Vertex ➡ First node of a relationship contained in biconnected component.
node_to: Vertex ➡ Second node of a relationship contained in biconnected component

Usage:

To find biconnected components in the graph, use the following query:

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

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

Find biconnected componentes

Get the values using the following query:

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

Results:

+------------------+------------------+------------------+------------------+
| bcc_id           | relationship     | 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}) |
+------------------+------------------+------------------+------------------+

betweenness_centrality bipartite_matching