7

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 GRASS 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.

Image showing disconnected regions in different colours

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. But how do I do this easily?

Other tools, like ArcGIS, have a "Find Disconnected" tool. But I am looking for a QGIS solution, please. An alternative might be the pgrouting.org extension for PostGIS.

  • This post might be helpful. I posted a Python script to identify roads that are not connected to anything. – ArMoraer Mar 10 '16 at 13:21
  • This is very useful plugin. But I fail running it. It returns an error "AttributeError: 'Graph' object has no attribute 'edges_iter'". I have NetworkX 2 installed. Tested with the provided sample data. I'd appreciate any suggestion. Thanks. – user8851509 Nov 30 '17 at 19:05
  • @user8851509 I see that NetworkX v2.0 is quite different from v1.x: see migration guide, so until l can update the plugin to work with both versions, a solution could be to downgrade NetworkX to v1. Please contact me via the plugin repo for help. – Peter Dec 1 '17 at 8:20
  • @user8851509, the latest version of the Disconnected Islands plugin has been released and is available for QGIS v3 (as well as an older version for QGIS v2 that uses the newer NetworkX v2.0 - this one fixes your problem above.) See <plugins.qgis.org/plugins/disconnected-islands> or the official QGIS Plugins repo. – Peter Dec 4 '18 at 7:17
10

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

4

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):

enter image description here

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
  • Thank you Detlev. This was a real help, and I have developed a QGIS plugin based on your answer. I will upload it to plugins.qgis.org as soon as I can, but for now it is available at github.com/petersmythe/disconnected-islands. – Peter Mar 18 '16 at 10:07
  • Just one enhancement to your code was necessary: tolerance = 0.000001 ... G.add_edges_from([((int(line[i][0]/tolerance), int(line[i][1]/tolerance)), (int(line[i+1][0]/tolerance), int(line[i+1][1]/tolerance)), {'fid': feat.id()})]) I found it necessary to first scale by tolerance, then convert to an integer. Before doing this, there were problems with the networkx library and floats not being exactly equal, thus creating disconnects that weren't actually there. – Peter Mar 18 '16 at 10:12
  • You are right. I have used rounding to some digits. That is the reason for asking: are your sure the data has valid topology? A problem arises if geometry should not be changed if actually a change is not necessary, or the segments have to keep in place. – Detlev Mar 18 '16 at 10:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.