Disconnected road links algorithm

DRL is a C++ algorithm designed to identify disconnected road links from Digiroad data. It analyzes the road network to detect nodes that are not properly connected, helping improve routing accuracy. DRL is a component of the routing-api system.

Build instructions

Building locally

On mac use the ./buildmac.sh

On linux use g++

Building using Docker

DRL is automatically built as part of the routing-api when using Docker.

Testing

DRL does currently not contain any tests.

CLI usage

DRL program takes no command line arguments. Instead, the node and way data are sent via standard input in the following format.

Input

Data types

Type	Size (bytes)
double	8
bool	1
int	4
string	4 + length of text

Header

Name	Type
min_dist	double
max_dist	double
same_name	bool

Nodes

Name	Type
node_count	int

Name	Type
node_id	int
lat	int
lon	int

Ways

Name	Type
way_count	int

Name	Type
way_id	int
way_node_count	int
node_id[]	int
way_name	string
way_highway	string
way_city_code	int

Output

The output prints each disconnection as a single line in the following comma-separated format:

data1,data2,data3,...,data10\n

After all disconnection lines are printed, a double colon :: is printed once on its own line.

Position	Field	Type
1	start_node_id	int
2	start_node_way_name	string
3	start_node_lat	int
4	start_node_lon	int
5	end_node_id	int
6	end_node_way_name	string
7	end_node_lat	int
8	end_node_lon	int
9	distance	double
10	city_code	int

Time complexity

Input Reading

• Reading N nodes and W ways is O(N + W * M), where M is the average number of nodes per way.

Graph Construction

• Constructing adjacency sets for each way involves iterating over each node in the ways, so O(W * M).

Spatial Binning

• Assigning each way to a geographic bin is O(W * M) due to averaging node coordinates per way.

BFS Connectivity Checks

• For each dead-end node (up to D), the program performs BFS searches:
  • Each BFS worst-case explores all nodes in the connected component, O(N + E), where E is number of edges.
  • The BFS calls happen inside nested loops iterating over neighboring bins and ways, approximately O(D * B * W' * BFS), where:
    • B = number of neighboring bins checked (constant, 9 in this case)
    • W' = average number of ways per bin
    • BFS = cost per BFS search (worst case O(N + E))

Overall Complexity

• The dominant cost lies in the BFS searches combined with binning iterations, roughly: O(N + W * M + D * B * W' * (N + E))

• In practice, spatial binning and filtering (e.g., same_name flag, excluding ways connected to the last way) reduce W' and BFS calls, improving performance.

Notes

• BFS complexity depends heavily on graph connectivity; sparse graphs yield faster BFS.
• Further optimization can reduce BFS calls or limit search depth.