Hello,
I have a graph and I want to find all the the disconnected nodes, and by “disconnected” I mean all the nodes that have no path to node A. There is a case where A can be more then 1 node, and I need to find out if there is a path to at least one of them.
My first idea is just to route to A from each node, easy to implement, but if I will have many nodes this will prove problematic.
Any ideas how to do this more efficiently inside PostgreSQL ?
Best Regards,
Iacovlev Pavel
On 4/16/2013 10:49 AM, Pavel Iacovlev wrote:
Hello,
I have a graph and I want to find all the the disconnected nodes, and by
"disconnected" I mean all the nodes that have no path to node A. There
is a case where A can be more then 1 node, and I need to find out if
there is a path to at least one of them.My first idea is just to route to A from each node, easy to implement,
but if I will have many nodes this will prove problematic.Any ideas how to do this more efficiently inside PostgreSQL ?
If you check out the sew-devel-2_0 branch in github you will find some graph analysis code that does this in src/common/sql/
This can probably just copy the sql and use it. Or at least look at it for how it works. Ask if you have questions.
This branch is stable at the moment if you want to clone it and build it and give it a test run. It installs on pg 9.1+ as an extension:
create extension pgrouting;
-Steve
Thank you, taking a look
On 16 Apr 2013 18:02, “Stephen Woodbridge” <woodbri@swoodbridge.com> wrote:
On 4/16/2013 10:49 AM, Pavel Iacovlev wrote:
Hello,
I have a graph and I want to find all the the disconnected nodes, and by
“disconnected” I mean all the nodes that have no path to node A. There
is a case where A can be more then 1 node, and I need to find out if
there is a path to at least one of them.My first idea is just to route to A from each node, easy to implement,
but if I will have many nodes this will prove problematic.Any ideas how to do this more efficiently inside PostgreSQL ?
If you check out the sew-devel-2_0 branch in github you will find some graph analysis code that does this in src/common/sql/
This can probably just copy the sql and use it. Or at least look at it for how it works. Ask if you have questions.
This branch is stable at the moment if you want to clone it and build it and give it a test run. It installs on pg 9.1+ as an extension:
create extension pgrouting;
-Steve
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users