bridges

A bridge in the graph can be described as an edge which if deleted, creates two disjoint graph components. This algorithm finds bridges within the graph. This algorithm has various practical usages such can be road or internet network design planning. A bridge can represent a bottleneck for many scenarios and it is valuable to have such an algorithm to detect it.

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_from ➡ Represents the first node in bridge edge
• node_to ➡ Represents the second node in bridge edge

Usage:

CALL bridges.get()
YIELD node_from, node_to;

Example

Step 1: Input graph

Step 2: Cypher load commands

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

Step 3: Running command

CALL bridges.get() YIELD node_from, node_to
WITH node_from, node_to
MATCH (node_from)-[bridge]-(node_to)
RETURN bridge, node_from, node_to;

Step 4: Results

+-----------------+-----------------+-----------------+
| bridge          | node_from       | node_to         |
+-----------------+-----------------+-----------------+
| [:RELATION]     | (:Node {id: 3}) | (:Node {id: 4}) |
| [:RELATION]     | (:Node {id: 0}) | (:Node {id: 3}) |
+-----------------+-----------------+-----------------+