Finding disconnected islands in road network layer using QGIS

Question

I have a road network layer that can't route from one side of the layer to the other. Topologically, there is no connectivity between the start and end nodes, probably due to missing links. This creates disconnected "islands" in the network graph.

How can I use QGIS or a python plugin to analyse my road network, perhaps traversing it from the starting node, to the extents of the connected links?

The output can either be a group column, where all connected links will all have the same ID, and the number of distinct IDs will be the number of disconnected islands, or a colour coded equivalent, like the one below, produced by TransCAD.

I am using QGIS 2.14.0-Essen. I have tried Topology Checker, Processing modules (formerly Sextante toolbox), GRASS v.net, v.clean, etc, and PyQGIS Developer Cookbook (http://docs.qgis.org/testing/en/docs/pyqgis_developer_cookbook/network_analysis.html#areas-of-availability)

The next step is to try and iterate, from the starting node, all "touching" links, adding them to a selection set, until there are no further ones to add. Label these as group 1 and then move onto another link that has not been selected and repeat for group 2, and so on, until there are no more unselected links.

Other tools, like ArcGIS, have a "Find Disconnected" tool but I am looking for a QGIS solution.

Answer 1

Based on Detlev's answer, I have developed a QGIS plugin which should allow others to solve similar problems easily. It is 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 line 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 can then be fixed.

Sample data to test this plugin can be found in your plugins directory: ~/.qgis2/python/plugins/disconnected-islands/sample-data/islands.zip

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

Answer 2

You can use Python module networkx for this.

The following script reads the polyline layers and creates an undirected graph. Networkx function connected_component_subgraphs() determines to which component each edge belongs to. Then all edges are written to a dict with feature id as key and component id as value. So duplicates are automatically removed. Last step is to write this dict to csv file.

You can load this csv file are join it on fid with your road network, and use categorical or rues based renderer to symbolize according comp_id.

import networkx as nx
import csv

# get the network
aLayer = qgis.utils.iface.activeLayer()
G = nx.Graph()

# construct undirected graph
for feat in aLayer.getFeatures():
    line = feat.geometry().asPolyline()
    for i in range(len(line)-1):
        G.add_edges_from([((line[i][0], line[i][1]), (line[i+1][0], line[i+1][1]), 
                          {'fid': feat.id()})])

# evaluate on connected components
connected_components = list(nx.connected_component_subgraphs(G))

# gather edges and components to which they belong
fid_comp = {}
for i, graph in enumerate(connected_components):
   for edge in graph.edges_iter(data=True):
       fid_comp[edge[2].get('fid', None)] = i

# write output to csv file
with open('E:/Temp/Components.csv', 'wb') as f:
    w = csv.DictWriter(f, fieldnames=['fid', 'comp_id'])
    w.writeheader()
    for row in fid_comp.items():
        w.writerow({'fid': row[0], 'comp_id': row[1]})

The test case (hint: line 10 overlaps line 5):

Resulting file Components.csv:

fid,comp_id
1,0
2,0
3,0
4,0
5,0
6,0
7,1
8,1
9,1
10,2