pgr_bridges
¶
pgr_bridges
- Return the bridges of an undirected graph.
Availability
- Version 3.0.0
- Return columns change:
seq
is removed - Official function
- Return columns change:
- Version 2.5.0
- New experimental function
Description¶
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:
- Works for undirected graphs.
- The returned values are ordered:
edge
ascending
- Running time: \(O(E * (V + E))\)
Signatures¶
pgr_bridges(Edges SQL) RETURNS SET OF (edge) OR EMPTY SET
Example: | The bridges of the graph |
---|
SELECT * FROM pgr_bridges(
'SELECT id, source, target, cost, reverse_cost FROM edges'
);
edge
------
1
6
7
14
17
18
(6 rows)
Inner Queries¶
Edges SQL¶
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 (
|
Where:
ANY-INTEGER: | SMALLINT , INTEGER , BIGINT |
---|---|
ANY-NUMERICAL: | SMALLINT , INTEGER , BIGINT , REAL , FLOAT |
Result Columns¶
Returns set of (edge)
Column | Type | Description |
---|---|---|
edge |
BIGINT |
Identifier of the edge that is a bridge. |
See Also¶
- https://en.wikipedia.org/wiki/Bridge_%28graph_theory%29
- The queries use the Sample Data network.
Indices and tables