pgr_bridges
- Return the bridges of an undirected graph.
Warning
Experimental functions
A bridge is an edge of an undirected graph whose deletion increases its number of connected components. This implementation can only be used with an undirected graph.
The main Characteristics are:
- The returned values are ordered:
- edge ascending
- Running time: \(O(E * (V + E))\)
pgr_bridges(edges_sql)
RETURNS SET OF (seq, node)
OR EMPTY SET
The signature is for a undirected graph.
Example: |
---|
SELECT * FROM pgr_bridges(
'SELECT id, source, target, cost, reverse_cost FROM edge_table'
);
seq | edge
-----+------
1 | 1
2 | 6
3 | 7
4 | 14
5 | 17
6 | 18
(6 rows)
edges_sql: | an SQL query, which should return a set of rows with the following columns: |
---|
Column | Type | Default | Description |
---|---|---|---|
id | ANY-INTEGER |
Identifier of the edge. | |
source | ANY-INTEGER |
Identifier of the first end point vertex of the edge. | |
target | ANY-INTEGER |
Identifier of the second end point vertex of the edge. | |
cost | ANY-NUMERICAL |
Weight of the edge (source, target)
|
|
reverse_cost | ANY-NUMERICAL |
-1 | Weight of the edge (target, source),
|
Where:
ANY-INTEGER: | SMALLINT, INTEGER, BIGINT |
---|---|
ANY-NUMERICAL: | SMALLINT, INTEGER, BIGINT, REAL, FLOAT |
Parameter | Type | Default | Description |
---|---|---|---|
edges_sql | TEXT |
SQL query as described above. |
Returns set of (seq, node)
Column | Type | Description |
---|---|---|
seq | INT |
Sequential value starting from 1. |
edge | BIGINT |
Identifier of the edge. |
Indices and tables