[pgrouting-users] Can pgr_connectedComponents be used to find isolated vertices?

pgRouting pgrouting-users
1

Dear fellow pgRouting users,

As per the description of pgr_connectedComponents, it runs a breadth-first search to find sets of vertices “that are all reachable from each other”.

Does that mean that if pgr_connectedComponents results in more than one connected component, some vertices are definitely not reachable from each other?

Can this be a way to guarantee that with more than 1 connected component it is guaranteed that algorithms like pgr_dijkstra will definitely fail on some pairs of vertices?

Thank you.

GP

2

I would say yes. If you have multiple components, then those components are not reachable from each other.

Note this is only considering an undirected graph.

If you have a directed graph, use pgr_strongComponents instead https://docs.pgrouting.org/latest/en/pgr_strongComponents.html

From: Pgrouting-users [mailto:pgrouting-users-bounces@lists.osgeo.org] On Behalf Of glad.pen2421@fastmail.com
Sent: Wednesday, August 2, 2023 12:40 PM
To: pgrouting-users@lists.osgeo.org
Subject: [pgrouting-users] Can pgr_connectedComponents be used to find isolated vertices?

Dear fellow pgRouting users,

As per the description of pgr_connectedComponents, it runs a breadth-first search to find sets of vertices “that are all reachable from each other”.

Does that mean that if pgr_connectedComponents results in more than one connected component, some vertices are definitely not reachable from each other?

Can this be a way to guarantee that with more than 1 connected component it is guaranteed that algorithms like pgr_dijkstra will definitely fail on some pairs of vertices?

Thank you.

GP

3

Thank you Regina, noted!

/GP

On Wed, 2 Aug 2023, at 19:56, Regina Obe wrote:

I would say yes. If you have multiple components, then those components are not reachable from each other.

Note this is only considering an undirected graph.

If you have a directed graph, use pgr_strongComponents instead https://docs.pgrouting.org/latest/en/pgr_strongComponents.html

From: Pgrouting-users [mailto:pgrouting-users-bounces@lists.osgeo.org] On Behalf Of glad.pen2421@fastmail.com
Sent: Wednesday, August 2, 2023 12:40 PM
To: pgrouting-users@lists.osgeo.org
Subject: [pgrouting-users] Can pgr_connectedComponents be used to find isolated vertices?

Dear fellow pgRouting users,

As per the description of pgr_connectedComponents, it runs a breadth-first search to find sets of vertices “that are all reachable from each other”.

Does that mean that if pgr_connectedComponents results in more than one connected component, some vertices are definitely not reachable from each other?

Can this be a way to guarantee that with more than 1 connected component it is guaranteed that algorithms like pgr_dijkstra will definitely fail on some pairs of vertices?

Thank you.

GP

Pgrouting-users mailing list

Pgrouting-users@lists.osgeo.org

https://lists.osgeo.org/mailman/listinfo/pgrouting-users