How to easily remove loose/isolated edges from pgRouting network?

Question

I wondered if there's an easy way to 'clean up' a pgRouting network by removing those edges that do not connect with the global network. Otherwise you risk to end up with cost values of -1, meaning there exists no path between the given source and target (pgr_kdijkstra).

I handled the osm.pbf file with osm2po (v4.8.8) and imported the network into a spatial database with the generated SQL script.

---

Getting back to my question, I found it lacked a bit of context :-) So...

I had generated a set of points as the centroids of a polygon layer. Eventually I want to use these centroids as start/end nodes to calculate shortest paths. As these points do not belong to a network, I cannot use them directly for routing. Therefore I searched for the nodes that are closest to the set of centroids by means of Vector > Analysis Tools > Distance matrix in QGIS. The problem, however, is that it is possible these 'corresponding' nodes are unreachable from the global network. When calculating shortest paths, they are indicated with a cost of -1.

As @Carsten noted, commenting out the following line in the config file of osm2po

postp.1.class = de.cm.osm2po.plugins.PgVertexWriter

will detect all dead ends or 'dangles'. As such you are able to filter them out from the whole set of nodes. But then, the problem indeed is that if an isolated mini-network consists of more than 1 segment, the vertices in the middle are not filtered out as these vertices are no dead ends. The figure from above represents the 'ideal' situation of an isolated mini-network of 1 segment and thus 2 dead ends. Eliminating those nodes results in eliminating the whole mini-network, which is nice.

So in fact, my question should have been 'How to eliminate (or detect) nodes and segments that are not connected to the global network'? That requires a little more (post)processing, as it is not incorporated as a preprocessing step which @Carsten also mentions in a related question.

Answer 1

In PgRouting 2.0 there is a pgr_analyzeGraph function that will identify isolated segments. Isolated segments will have a dead-end at each end so a query like this against your network and vertices tables:

SELECT *
    FROM mytab a, mytab_vertices_pgr b, mytab_vertices_pgr c
    WHERE a.source=b.id AND b.cnt=1 AND a.target=c.id AND c.cnt=1;

will identify the segments you want.

See http://docs.pgrouting.org/2.0/en/doc/src/tutorial/analytics.html for more information.

Answer 2

If instead single isolated segments, you need to identify sub-graphs that are isolated from the rest of the graph, then using pg_routing pgr_connectedComponents() function will separate all nodes into connected sub-groups (components).

You can then see which component represents the bigger sub-group of the graph (hopefully component=1), and see what is going on with the rest of the sub-groups.

You can create a query to get all the nodes, their components and geometry.

CREATE OR REPLACE VIEW osm.nos_conexos as
SELECT
    n.id,
    c.component,
    n.the_geom
FROM pgr_connectedComponents('SELECT id, source, target, cost FROM osm.roads_pt_routing') AS c 
JOIN osm.ROADS_PT_ROUTING_VERTICES_PGR AS n ON c.node = n.id;

In QGIS, load the view and use categorized symbols to show the subgroups of nodes.

Answer 3

Hmmm... no answers here ... Ok... look for this line inside the config and comment it out:

postp.1.class = de.cm.osm2po.plugins.PgVertexWriter

This will give you an additional table of vertices. Look for the ref_count-column. A value of "0" indicates dead ends or "no crossing". But what are you going to interpret in your example above if it's composed of two or more sections?

Answer 4

Since you mentioned using QGIS, I had a similar problem, so I developed a QGIS plugin which is now available in the official QGIS plugins repository and can be found in the QGIS menu: Plugins / Manage and Install Plugins... and search for Disconnected Islands.

http://plugins.qgis.org/plugins/disconnected-islands/

This plugin runs on a polyline layer, building up a road (or rail, etc.) network graph of connected links. It then analyses connected subgraphs, ones that are connected to each other, but not connected to isolated or floating links. It creates an additional attribute containing the group ID of the subgraph. This can then be used to style the layer with Categorised styles, or Zoom to selection. The disconnected links (everything with a group ID <> 0) can then be fixed or removed.

Source code can be forked from: https://github.com/AfriGIS-South-Africa/disconnected-islands

Answer 5

I've ran into a similar problem with a large network (~400k edges). Peter's plugin works, but took many hours and all my RAM, probably because it partitions edges using their geometries when all I cared about was their topology.

So I've made my own script in python, that directly removes all minor groups, considering as "minor" the ones that have less than 10% of the edges in the network. It solved my problem in less than 10 seconds.

Answer 6

If you have one "global" network which is strongly connected and want to delete all islands, you could approach it the following way. The CTE returns the strongest component by grouping by component and limiting by 1. Afterwards all edges should be removed for which source or target are not part of this component.

WITH scc AS (
    SELECT array_agg(node) AS v_ids
    FROM pgr_strongComponents(
        'SELECT gid AS id, source, target, cost FROM edges'
    ) 
    GROUP BY component
    ORDER BY COUNT(component) DESC
    LIMIT 1
)
DELETE FROM edges
WHERE source::bigint NOT IN (
    SELECT unnest(v_ids) 
    FROM scc
)
AND target::bigint NOT IN (
    SELECT unnest(v_ids) 
    FROM scc
);