How to compute the smallest network that connects all points using PostGIS?

Question

I have a set of postgis scripts which generates two tables - one of a set of points and the second a set of roads which surround them. All data is in the same projection and both outputs are stored in postgres 9.2 tables with postgis 2.1

The pgrouting topology of the road network has been created and the points table has a column containing the nearest road segment.

I'd like then to generate a subset of the road network which represents the smallest network that connects all points using something like a minimum spanning tree. The road network is undirected, and costs are simply the route length.

I can do this in QGIS/Grass using the v.net family of modules but ideally I'd like to keep this final step in SQL as well.

I've looked at the new apspWarshall postgis function but I'm at a loss as to how it can be encouraged to focus its energy on connecting the points and not the whole network.

This is the short script I've put together in an attempt to create a framework to solve this but I can't see where its possible to focus the function to start with a subset of the edges.

SELECT seq, id1 AS node, id2 AS edge, cost, the_geom
FROM   pgr_apspWarshall('SELECT gid AS id, 
                                source, 
                                target, 
                                st_length(the_geom) AS cost 
                         FROM   road_network
                        ',
                        false, false
                       ) AS tree
JOIN   road_network As roads
ON     tree.id2 = roads.gid

In single path shortest path problems the function asks for the start and end but apparently not in the all points problems. Equally in Grass the v.net.spanningtree and v.net.steiner expect a set of points and lines as a combined network to work with.

Does anyone have an suggestions for how to do this in PostGIS?

Answer 1

This answer is not complete or tested, but try something like this:

according to questions/39210:

with index_query as (
SELECT
        ,ST_Distance(i.geom, i.b_geom) AS dist
        ,ST_MakeLine(i.geom, i.b_geom) as geom
FROM(
SELECT
        ,a.geom
        ,b.geom AS b_geom
        ,rank() OVER (PARTITION BY a.id ORDER BY ST_Distance(a.centroid_geom, b.the_geom)) AS pos
FROM points a, points b 
WHERE a.id <> b.id) i
WHERE pos = 1
) select ST_Union(geom) from index_query;

i think this is not very efficient.

Answer 2

@Adrian, I am really unfamiliar with the pgrouting results, however the documentation is very detailed. My answer is based on a two-step function, which will be very inneficient in SQL but [likely] produces the results. This [untested] solution will NOT optimize which is the best starting point, but will reduce the entire route network to only the edges which connect all stops, then routes efficiently to all stops.

Step 1 (sub-selection of a road network subset which connects all stops) This uses the multiple-destination (K Dijkstr path) routing function to return a collection of paths that (when cost <> -1) actually do connect all of your stops.

SELECT id1 as path, st_astext(st_linemerge(st_union(b.the_geom))) as the_geom
FROM pgr_kdijkstraPath(
’SELECT id, source, target, cost FROM edge_table’,
min(all_your_stop_ids), [array_of_all_your_stop_ids], false, false
) a,
edge_table b
WHERE a.id3=b.id
GROUP by id1
ORDER by id1

The problem I have here is the syntax for assembling an array from your stop table, as it wasn't really described in the question. However, let's assume that SQL syntax can assemble that array and that the minimum id stop should be the starting point for all the K paths to the remaining target stops.

Step 2 (final selection of the minimum paths based on the above subset road network paths which connect all stops) This is essentially what you started with, but I propose that you equa-join your road network to the initial result on id1 (path) so that only the subset of roads is used in the final Field-Warshal routing:

SELECT seq, id1 AS node, id2 AS edge, cost, the_geom
FROM   pgr_apspWarshall('SELECT R.gid AS id, 
                                R.source, 
                                R.target, 
                                st_length(R.the_geom) AS cost 
             FROM   road_network AS R JOIN
                   (SELECT id1 as path
                     FROM pgr_kdijkstraPath(
                            ’SELECT id, source, target, cost FROM edge_table’,
                            min(all_your_stop_ids), 
                            [array_of_all_your_stop_ids], false, false
                           ) a,
                     edge_table b
                    WHERE a.id3=b.id
                    GROUP by id1
                    ORDER by id1
                        ',
                        false, false
                  ) AS  Just_K_Paths
         on R.id1 = just_K_paths.id1',       /* this join reduces R down to K paths */
         false, false
        ) AS tree
  JOIN   road_network As roads
  ON     tree.id2 = roads.gid

So, in summary...the inner k_dijkstra_path routing query reduces the total road network to only the paths connecting all your stops, then the outer fField_Warshal routing uses only those edge ids to solve the path-optimization query....maybe.