The problem definition
Connected components
A connected component of an undirected graph is a set of vertices that are all reachable
from each other.
Notice: This problem defines on an undirected graph.
Given the following query:
pgr_connectedComponentsV(\(sql\))
where \(sql = \{(id_i, source_i, target_i, cost_i, reverse\_cost_i)\}\)
and
 \(source = \bigcup source_i\),
 \(target = \bigcup target_i\),
The graphs are defined as follows:
The weighted undirected graph, \(G(V,E)\), is definied by:
 the set of vertices \(V\)
 \(V = source \cup target\)
 the set of edges \(E\)
 \(E = \begin{cases} &\{(source_i, target_i, cost_i) \text{ when } cost >=0 \} \\ \cup &\{(target_i, source_i, cost_i) \text{ when } cost >=0 \} &\quad \text{ if } reverse\_cost = \varnothing \\ \\ &\{(source_i, target_i, cost_i) \text{ when } cost >=0 \} \\ \cup &\{(target_i, source_i, cost_i) \text{ when } cost >=0 \} \\ \cup &\{(target_i, source_i, reverse\_cost_i) \text{ when } reverse\_cost_i >=0)\} \\ \cup &\{(source_i, target_i, reverse\_cost_i) \text{ when } reverse\_cost_i >=0)\} &\quad \text{ if } reverse\_cost \neq \varnothing \\ \end{cases}\)
Given:
Then:
\[\begin{split}\text{pgr_connectedComponentsV}(sql) =
\begin{cases}
\text{all connected components } \boldsymbol{\pi} \text{ in } G(V,E) &\quad \text{if } \exists \boldsymbol{\pi} \\
\varnothing &\quad \text{otherwise} \\
\end{cases}\end{split}\]
\(\boldsymbol{\pi} = \{(component_i, n\_seq_i, node_i)\}\)
 where:
 \(component_i = \min \{node_j  node_j \in component_i\}\)
 \(n\_seq_i\) is a sequential value starting from 1 in a component.
 \(node_i \in component_i\)
 The returned values are ordered:
 component ascending
 node ascending
 Example:
 The first component is composed of nodes
0
, 1
and 4
.
 The second component is composed of node
3
.
 The third component is composed of nodes
2
and 5
.
Strongly connected components
A strongly connected component of a directed graph is a set of vertices that are all reachable
from each other.
Notice: This problem defines on a directed graph.
Given the following query:
pgr_strongComponentsV(\(sql\))
where \(sql = \{(id_i, source_i, target_i, cost_i, reverse\_cost_i)\}\)
and
 \(source = \bigcup source_i\),
 \(target = \bigcup target_i\),
The graphs are defined as follows:
The weighted directed graph, \(G_d(V,E)\), is definied by:
 the set of vertices \(V\)
 \(V = source \cup target \cup {start_{vid}} \cup {end_{vid}}\)
 the set of edges \(E\)
 \(E = \begin{cases} &\{(source_i, target_i, cost_i) \text{ when } cost >=0 \} &\quad \text{ if } reverse\_cost = \varnothing \\ \\ &\{(source_i, target_i, cost_i) \text{ when } cost >=0 \} \\ \cup &\{(target_i, source_i, reverse\_cost_i) \text{ when } reverse\_cost_i >=0)\} &\quad \text{ if } reverse\_cost \neq \varnothing \\ \end{cases}\)
Given:
Then:
\[\begin{split}\text{pgr_strongComponentsV}(sql) =
\begin{cases}
\text{all strongly connected components } \boldsymbol{\pi} \text{ in } G(V,E) &\quad \text{if } \exists \boldsymbol{\pi} \\
\varnothing &\quad \text{otherwise} \\
\end{cases}\end{split}\]
\(\boldsymbol{\pi} = \{(component_i, n\_seq_i, node_i)\}\)
 where:
 \(component_i = \min {node_j  node_j \in component_i}\)
 \(n\_seq_i\) is a sequential value starting from 1 in a component.
 \(node_i \in component_i\)
 The returned values are ordered:
 component ascending
 node ascending
 Example:
 The first component is composed of nodes
1
, 2
and 4
.
 The second component is composed of node
0
.
 The third component is composed of node
3
.
 The fourth component is composed of node
5
.
 The fifth component is composed of node
6
.
Biconnected components
The biconnected components of an undirected graph are the maximal subsets of vertices such that the removal of a vertex from
particular component will not disconnect the component. Unlike connected components, vertices may belong to multiple biconnected
components. Vertices can be present in multiple biconnected components, but each edge can only be contained in a single biconnected
component. So, the output only has edge version.
Notice: This problem defines on an undirected graph.
Given the following query:
pgr_biconnectedComponents(\(sql\))
where \(sql = \{(id_i, source_i, target_i, cost_i, reverse\_cost_i)\}\)
and
 \(source = \bigcup source_i\),
 \(target = \bigcup target_i\),
The graphs are defined as follows:
The weighted undirected graph, \(G(V,E)\), is definied by:
 the set of vertices \(V\)
 \(V = source \cup target\)
 the set of edges \(E\)
 \(E = \begin{cases} &\{(source_i, target_i, cost_i) \text{ when } cost >=0 \} \\ \cup &\{(target_i, source_i, cost_i) \text{ when } cost >=0 \} &\quad \text{ if } reverse\_cost = \varnothing \\ \\ &\{(source_i, target_i, cost_i) \text{ when } cost >=0 \} \\ \cup &\{(target_i, source_i, cost_i) \text{ when } cost >=0 \} \\ \cup &\{(target_i, source_i, reverse\_cost_i) \text{ when } reverse\_cost_i >=0)\} \\ \cup &\{(source_i, target_i, reverse\_cost_i) \text{ when } reverse\_cost_i >=0)\} &\quad \text{ if } reverse\_cost \neq \varnothing \\ \end{cases}\)
Given:
Then:
\[\begin{split}\text{pgr_biconnectedComponents}(sql) =
\begin{cases}
\text{all biconnected components } \boldsymbol{\pi} \text{ in } G(V,E) &\quad \text{if } \exists \boldsymbol{\pi} \\
\varnothing &\quad \text{otherwise} \\
\end{cases}\end{split}\]
\(\boldsymbol{\pi} = \{(component_i, n\_seq_i, node_i)\}\)
 where:
 \(component_i = \min {node_j  node_j \in component_i}\)
 \(n\_seq_i\) is a sequential value starting from 1 in a component.
 \(edge_i \in component_i\)
 The returned values are ordered:
 component ascending
 edge ascending
 Example:
 The first component is composed of edges
1  2
, 0  1
and 0  2
.
 The second component is composed of edges
2  4
, 2  3
and 3  4
.
 The third component is composed of edge
5  6
.
 The fourth component is composed of edge
6  7
.
 The fifth component is composed of edges
8  9
, 9  10
and 8  10
.
Articulation Points
Those vertices that belong to more than one biconnected component are called
articulation points or, equivalently, cut vertices. Articulation points are
vertices whose removal would increase the number of connected components in
the graph.
Notice: This problem defines on an undirected graph.
Given the following query:
pgr_articulationPoints(\(sql\))
where \(sql = \{(id_i, source_i, target_i, cost_i, reverse\_cost_i)\}\)
and
 \(source = \bigcup source_i\),
 \(target = \bigcup target_i\),
The graphs are defined as follows:
The weighted undirected graph, \(G(V,E)\), is definied by:
 the set of vertices \(V\)
 \(V = source \cup target\)
 the set of edges \(E\)
 \(E = \begin{cases} &\{(source_i, target_i, cost_i) \text{ when } cost >=0 \} \\ \cup &\{(target_i, source_i, cost_i) \text{ when } cost >=0 \} &\quad \text{ if } reverse\_cost = \varnothing \\ \\ &\{(source_i, target_i, cost_i) \text{ when } cost >=0 \} \\ \cup &\{(target_i, source_i, cost_i) \text{ when } cost >=0 \} \\ \cup &\{(target_i, source_i, reverse\_cost_i) \text{ when } reverse\_cost_i >=0)\} \\ \cup &\{(source_i, target_i, reverse\_cost_i) \text{ when } reverse\_cost_i >=0)\} &\quad \text{ if } reverse\_cost \neq \varnothing \\ \end{cases}\)
Given:
Then:
\[\begin{split}\text{pgr_articulationPoints}(sql) =
\begin{cases}
\text{all articulation points } \boldsymbol{\pi} \text{ in } G(V,E) &\quad \text{if } \exists \boldsymbol{\pi} \\
\varnothing &\quad \text{otherwise} \\
\end{cases}\end{split}\]
\(\boldsymbol{\pi} = \{node_i\}\)
 where:
 \(node_i\) is an articulation point.
 The returned values are ordered:
 Example:
 Articulation points are nodes
2
and 6
.
Bridges
A bridge is an edge of an undirected graph whose deletion increases its number
of connected components.
Notice: This problem defines on an undirected graph.
Given the following query:
pgr_bridges(\(sql\))
where \(sql = \{(id_i, source_i, target_i, cost_i, reverse\_cost_i)\}\)
and
 \(source = \bigcup source_i\),
 \(target = \bigcup target_i\),
The graphs are defined as follows:
The weighted undirected graph, \(G(V,E)\), is definied by:
 the set of vertices \(V\)
 \(V = source \cup target\)
 the set of edges \(E\)
 \(E = \begin{cases} &\{(source_i, target_i, cost_i) \text{ when } cost >=0 \} \\ \cup &\{(target_i, source_i, cost_i) \text{ when } cost >=0 \} &\quad \text{ if } reverse\_cost = \varnothing \\ \\ &\{(source_i, target_i, cost_i) \text{ when } cost >=0 \} \\ \cup &\{(target_i, source_i, cost_i) \text{ when } cost >=0 \} \\ \cup &\{(target_i, source_i, reverse\_cost_i) \text{ when } reverse\_cost_i >=0)\} \\ \cup &\{(source_i, target_i, reverse\_cost_i) \text{ when } reverse\_cost_i >=0)\} &\quad \text{ if } reverse\_cost \neq \varnothing \\ \end{cases}\)
Given:
Then:
\[\begin{split}\text{pgr_bridges}(sql) =
\begin{cases}
\text{all bridges } \boldsymbol{\pi} \text{ in } G(V,E) &\quad \text{if } \exists \boldsymbol{\pi} \\
\varnothing &\quad \text{otherwise} \\
\end{cases}\end{split}\]
\(\boldsymbol{\pi} = \{edge_i\}\)
 where:
 \(edge_i\) is an edge.
 The returned values are ordered:
 Example:
 Bridges are edges
5 <> 6
and 6 <> 7
.
Description of the edges_sql query for components functions
edges_sql:  an SQL query, which should return a set of rows with the following columns: 
Column 
Type 
Default 
Description 
id 
ANYINTEGER 

Identifier of the edge. 
source 
ANYINTEGER 

Identifier of the first end point vertex of the edge. 
target 
ANYINTEGER 

Identifier of the second end point vertex of the edge. 
cost 
ANYNUMERICAL 

Weight of the edge (source, target)
 When negative: edge (source, target) does not exist, therefore it’s not part of the graph.

reverse_cost 
ANYNUMERICAL 
1 
Weight of the edge (target, source),
 When negative: edge (target, source) does not exist, therefore it’s not part of the graph.

Where:
ANYINTEGER:  SMALLINT, INTEGER, BIGINT 
ANYNUMERICAL:  SMALLINT, INTEGER, BIGINT, REAL, FLOAT 
Description of the parameters of the signatures
Parameter 
Type 
Default 
Description 
edges_sql 
TEXT 

SQL query as described above. 
Description of the return values for connected components and strongly connected components
Returns set of (seq, component, n_seq, node)
Column 
Type 
Description 
seq 
INT 
Sequential value starting from 1. 
component 
BIGINT 
Component identifier. It is equal to the minimum node identifier in the component. 
n_seq 
INT 
It is a sequential value starting from 1 in a component. 
node 
BIGINT 
Identifier of the vertex. 
Description of the return values for biconnected components, connected components (edge version) and strongly connected components
Returns set of (seq, component, n_seq, edge)
Column 
Type 
Description 
seq 
INT 
Sequential value starting from 1. 
component 
BIGINT 
Component identifier. It is equal to the minimum edge identifier in the component. 
n_seq 
INT 
It is a sequential value starting from 1 in a component. 
edge 
BIGINT 
Identifier of the edge. 
Description of the return values for articulation points
Returns set of (seq, node)
Column 
Type 
Description 
seq 
INT 
Sequential value starting from 1. 
node 
BIGINT 
Identifier of the vertex. 
Description of the return values for bridges
Returns set of (seq, node)
Column 
Type 
Description 
seq 
INT 
Sequential value starting from 1. 
edge 
BIGINT 
Identifier of the edge. 