D 2018-04-02T17:38:40.479 L VirtualRouting P 977ae572d10fbb11743df9410e4f4dad5599aeb6 U sandro W 39315 back

1 - Introduction
2 - The sample/test DB
3 - Creating VirtualRouting Tables
4 - Solving classic Shortest Path problems

1 - Introduction

Previous versions of SpatiaLite traditionally supported a pure SQL routing module that was named VirtualNetwork.

Since version 5.0.0 a brand new routing module (more advanced and sophisticated) is available, that is called VirtualRouting.
The now obsolete VirtualNetwork is still supported by version 5.0.0 so as to not cause an abrupt break to already existing applications, but will presumably be discontinued in future versions.
Using VirtualRouting instead of VirtualNetwirk is warmly recommended for any new development.

Theoretical foundations - an ultra-quick recall

All Routing algorithms (aka Shortest Path algorithms) are based on the mathematics of the Graph theory or to be more precise: on Weighted Graphs.
network

A topologically valid Network is a dataset that fulfills the following requirements:

All items in the dataset are called Links (aka Arcs), and are expected to represent some oriented connection joining two Nodes.
Example: in the above figure Link L3 connects Nodes N2 and N5.
So all Links are always expected to explicitly reference a Start-Node (aka Node-From) and an End-Node (aka Node-To).
- Links are always oriented, and their natural direction is From-To:
  - in an unidirectional Network each Link is an one-way connection.
    If the connection is available in the opposite direction a second Link must be explicitly declared.
    Example: Link X1 goes from Node A to Node B, and Link X2 goes from Node B to Node A.
  - in a bidirectional Network all Links are assumed to establish a connection in both directions.
    Definiting an one-way connection requires an appropriate attribute to be set (see below).
- The Start- and End-Node could eventually be the same, and in this case we'll have a self-closed Link.
- Network's Links can eventually define a linear Geometry (LINESTRING) going from the Start-Node to the End-Node, but this is an optional feature, not a mandatory requirement.
- What is absolutely mandatory is that each Link must explicitly reference its Nodes.
A Network supporting Geometries is a Spatial Network; otherwise a Network lacking any Geometry is a Logical Network.
- In a Spatial Network all Links must have a corresponding Geometry.
- In a Logical Network all Links are strictly forbidden to have any Geometry.
- In a Spatial Network both the StartPoint and EndPoint of each Link's LINESTRING are always expected to exactly coincide with the corresponding Nodes.
In a Spatial Network all references to the same Node by different Links must be an exact match.
Example: Node N5 is shared by Links L3, L6, L7, L9 and L10, so all their corresponding LINESTRINGS are expected to have the corresponding extremity (Start- or End-, depending on the orientation) points that must exactly match the other.
A topological inconsistency exists if any of these conditions are not satisfied, which leads to an invalid Network.
In a Spatial Network two
Accordingly to the above premises, Nodes are never expected to be explicitly declared in a separate Table.
Just a single Table declaring all Links is required in order to fully define a topologically valid Network.
All the Nodes can then be easily extracted from the Links' definitions and the coordinates for each Node can be directly set by extracting the extreme Point of the corresponding Linestrings.
If any mismatch is detected this surely means that the Network is invalid.
A Link may legitimately self-intersect itself (e.g. forming a loop), as shown in the above figure by Link L15 (orange spot).
Two Links may legitimately intersect where no Node exists, as exemplified on the above figure by Links L4 and L7 (green spot).
This usually happens when one of the two Links overpasses the other, or where some technical restriction exists (e.g. two insulated wires in an Electrical Network).
Links aren't strictly required to be associated with any specific attribute, but the following attributes are almost universally supported:
- a name identifying the Link.
  Examples: the road toponym in a road network, or the river name in an hydrographic network.
- one (or even more) appropriate cost value(s).
  Example: the time required to traverse the Link (may be distinguished between pedestrians, bicycles, cars, lorries and so on).
- a pair of boolean flags (from-to and to-from) are intendend to specify if the Link can be traversed on both directions or just in one (one-way).

Logical conclusions

Any topologically valid Network (irrespective of whether it is a Spatial or Logical type) is a valid Graph.
A Network allowing the support (direct or indirect) of some appropriate cost value is a valid Weighted Graph, and can consequently support Routing algorithms.
All Routing algorithms are intended to identify the Shortest Path solution connecting two Nodes in a weighted graph (aka Network).

Note: the term Shortest Path can be easily misunderstood.
Due to historical reasons the most common application field for Routing algorithms is related to Road Networks, but also many other kinds of Networks exist:

Hydrographic Networks.
Gas / Water / Oil Networks.
Electrical Networks.
Telecomunication Networks.
Social or Economical Networks representing relationships between individuals or companies.
Epidemiological Networks representing the propagation of infective diseases between individuals or groups.

In all the above cases we certainly have valid Networks supporting Routing algorithns, but not all of them can imply something like a spatial distance (geometric length) or a travel time.
In the most general acception costs can be represented by any reasonable physical quantity.
So a more generalized definition is assuming that Routing algorithms are intended to identify lesser cost solutions on a weighted graph.
The exact interpretation of the involved costs (aka weights) strictly depends on the very specific nature of each Network.

The Dijkstra's algorithm

This well known algorithm isn't necessarily the fastest one, but it always ensures full correctness:

Any Node-to-Node connection identified by Dijkstra's is certainly ensured to be optimal.
In other words, no connetction presenting a lower cost can conceptually exist.
When Dijsjtra's fails to identify a solution this surely means that no solution is possible.

The A* algorithm

Many alternative Routing algorithms have been invented during the years.
All them are based on heuristic assumptions and are intended to be faster than Dijkstra's, but none of them can ensure full correctness as Dijkstra's does.
The A* algorithm applies a mild heuristic optimization, and can be a realistic alternative to Dijkstra's in many cases.

2 - The sample/test DB

You are expected to follow the current tutorial about VirtualRouting by directly testing all SQL queries discussed below on behalf of the sample/test DB that you can download from here

The sample DB contains the full road network of Tuscany Region (Italy) (Iter.Net dataset) kindly released under the CC-BY-SA 4.0 licence terms.
The contents stored into the sample database were opportunely rearranged, and are still subject to the initial CC-BY-SA 4.0 clauses (derived work).

all road names are stored within the toponyms Table.
the same road name could be used in different Municipalities, so the toponyms Table relationally references the municipalities Table (via PRIMARY / FOREIGN KEY relationships).
the roads Spatial Table contains about 380,000 Links, and has the following columns:
- id: unique identifier of each Link (PRIMARY KEY).
- node_from and node_to: Node identifiers. The original Iter.Net dataset adopts very long an complex alphanumeric Node codes; the integer Node IDs were obtained by calling the CreateRoutingNodes() SQL function discussed in a following section.
- id_toponym: relational reference to the corresponding road name contained into the toponyms Table (FOREIGN KEY).
- speed_kmh: the estimated average speed supported by the Link, expressed in km/h.
  Note: negative speeds intend a forbidden Link.
- oneway_fromto and oneway_tofrom: boolean flags intended to state if a Link can be traversed in both directions or just in a single direction (one-way).
  Note: all Links declaring oneway_fromto=0 and oneway_tofrom=0 are intended to be always forbidden.
- cost: the time expressed in seconds required to traverse each Link.
  Note #1 all costs were calculated accordingly to the following formula: cost = ((ST_Length(geom) / 1000.0) / speed_kmh) * 3600.0
  Note #2 all 86,400.0 cost values (equivalent to 1 day) approximate an infinitive cost thus intending a forbidden Link.
- geom: a 3D Linestring representing the Geometry of each Link.
  Note: the original Iter.Net dataset is just 2D; elevations (Z coordinates) were interpolated by draping the dataset over an orographic DEM (10m X 10m cells)
the roads_vw Spatial View is just intended to fully resolve all relational references between roads, toponyms and municipalities, thus allowing for easier SQL queries.
the house_nr Spatial Table contains about 1,480,000 House Numbers, and has the following columns:
- id: unique identifier of each House Number (PRIMARY KEY).
- id_road: relational reference to the corresponding Link contained into the roads Table (FOREIGN KEY).
- label: the textual label fully qualifying each House Number.
- geom: a 3D Point representing the Geometry of each House Number.
  Note #1: also in this case all elevations (Z coordinates) were interpolated by draping the dataset over the same DEM as above.
  Note #2: strictly specking the House Numbers are not part of the Road Network; they are include into the sample/test database just because they'll be useful in some of the examples explained in below paragraphs.
the house_nr_vw Spatial View is just intended to fully resolve all relational references between house_nr, roads, toponyms and municipalities, thus allowing for easier SQL queries.

3 - Creating VirtualRouting Tables

All VirtualRouting queries are based on some VirtualRouting Table, and in turn any VirtualRouting Table is based on some appropriate Binary Data Table supporting an efficient representation of the underlying Network.
So we'll start first by creating such tables.

The old and now superseded VirtualNetwork required using a separate CLI tool (spatialite_network) in order to properly initialize a VirtualNetwork Table and its companion Binary Data Table; alternatively spatialite_gui supported a GUI wizard for the same task. Since version 5.0.0 now SpatiaLite directly supports a specific CreateRouting() SQL function. SELECT CreateRouting('byfoot_data', 'byfoot', 'roads_vw', 'node_from', 'nodeto', 'geom', NULL); SELECT CreateRouting_GetLastError(); ------------------------------------ ToNode Column "nodeto" is not defined in the Input Table Note: this first query contains an intended error causing CreateRouting() to fail raising an exception.
CreateRouting() can fail for multiple reasons, and by calling CreateRouting_GetLastError() you can easily identify the exact reason why the most recent call to CreateRouting() failed.
SELECT CreateRouting('byfoot_data', 'byfoot', 'roads_vw', 'node_from', 'node_to', 'geom', NULL); ------------- 1 SELECT CreateRouting_GetLastError(); ------------------------------------ NULL This second attempt if finally successful, and now CreateRouting() returns 1 (aka TRUE), and as you can easily check now the Database contains two new Tables: byfoot and byfoot_data.
Note: after a successful call to CreateRouting() CreateRouting_GetLastError() will always return NULL.

You've just used the reduced form of CreateRouting(); let's see in more depth all the arguments and their meaning:

byfoot_data: the name of the Network Binary Data Table to be created.
byfoot: the name of the VirtualRouting Table to be created.
roads_vw: the name of the Spatial Table or Spatial View representing the underlying Network.
Note: in this case we actually used a Spatial View.
node_from: name of the column (in the above Table or View) expected to contain node-from values.
node_to: name of the column (in the above Table or View) expected to contain node-to values.
geom: name of the column (in the above Table or View) expected to contain Linestrings.
We could have legitimately passed a NULL value for this argument in the case of a Logical Network.
NULL: name of the column (in the above Table or View) expected to contain cost values.
In this case we have passed a NULL value, and consequently the cost of each Link will be assumed to be represented by the geometric length of the corresponding Linestring.
Note #1: in the case of Networks based on longitudes and latitudes (aka geographic Reference Systems) the geometry length of all Linestrings will be precisely measured on the ellipsoid by applying the most accurate geodesic formulae and will be consequently expressed in meters. In any other case (projected Reference Systems) lengths will be expressed in the measure unit defined by the Reference System (e.g. meters for UTM projections and feet for NAD-ft projections).
Note #2: the geom-column and cost-column arguments are never allowed to be NULL at the same time.

Technical note

The internal encoding adopted by the Binary Data Table is unchanged and is the same for both VirtualNetwok and VirtualRouting.
You can safely base a VirtualRouting Table on any existing Binary Data Table created by the spatialite-network CLI tool, exactly as you can base a VirtualNetwork Table on any Binary Data Table created by the CreateRouting() SQL function. CREATE VIRTUAL TABLE test_network USING VirtualNetwork('some_data_table'); CREATE VIRTUAL TABLE test_routing USING VirtualRouting('some_data_table'); In order to manually create your Virtual Tables you just have to execute an appropriate CREATE VIRTUAL TABLE ... USING Virtual... (...) statement.

Warning

In the case of Spatial Networks based on any geographic Reference System (using longitudes and latitudes) there is an important difference between Binary Data Tables created by the spatialite_network GUI tool and Binary Data Tables created by the CreateRouting() SQL function when costs are implicitly based on the geometric length of the Link's Linestring:

the spatialite_network CLI tool (and the GUI wizard implemented by previous versions of spatialite_gui) compute the Linestring's length as an angular distance expressed in degrees.
the CreateRouting() SQL function computes the Linestring's length as a linear distance expressed in metres by applying the most accurate geodesic formulae on the ellipsoid.

SELECT CreateRouting('bycar_data', 'bycar', 'roads_vw', 'node_from', 'node_to', 'geom', 'cost', 'toponym', 1, 1, 'oneway_fromto', 'oneway_tofrom', 0); -------------------- 1 After calling yet another time CreateRouting() now the Database contains two further Tables: bycar and bycar_data.
This time you've used the complete form of CreateRouting(); let's see in more depth all the arguments and their meaning:

bycar_data: same as above.
bycar: same as above.
roads_vw: same as above.
node_from: same as above.
node_to: same as above.
geom: same as above.
cost: same as above. In this case we have referenced a column preloaded with values corresponding to the time measured in seconds required to traverse each Link.
toponym: name of the column (in the above Table or View) expected to contain road-name values.
It could be legitimately set to NULL if all Links are anonymous.
1: a boolean flag intended to specify if the Network must support the A* algorithm or not (set to TRUE by default).
1: a boolean flag intended to specify if all Network's Links are assumed to be bidirectional or not (assumed to be TRUE by default).
oneway_fromto: name of the column (in the above Table or View) expected to contain boolean flags specifying if each Link can be traversed in the from-to direction or not.
oneway_tofrom: name of the column (in the above Table or View) expected to contain boolean flags specifying if each Link can be traversed in the to-from direction or not.
Note #1: both from-to and to-from column names can be legitimately set as NULL if no one-way restrictions apply to the current Network.
Note #2: Networks of the unidirectional type are never enabled to reference one-way columns (they should always be set to NULL).
0: a boolean flag intending an overwrite authorization.
- If set to FALSE an exception will be raised if the Binary Data Table and/or the VirtualRouting Table do already exist.
- If set to TRUE eventually existing Tables will be preventively dropped immediately before starting the execution of CreateRouting().

Highlight: where you are

You've just created two VirtualRouting Tables based on different settings; both them are perfectly valid and reasonable, but they are intended for different purposes:

byfoot is specifically intended for pedestrians:
- all Links are always assumed to be accessible in both directions; there are no one-ways and no forbidden Links.
- the cost of each Link is directly represented by its geometric length, which is consistent with the assumption of an almost constant speed substantially immune from adverse road conditions and traffic congestion.
bycar is specifically intended for motor vehicles:
- many Links are expected to be accessible in both directions but others could easily be subject to one-way restrictions or even be completely forbidden.
- the cost of each Link is expressed as an estimated travel time, because the expected speeds can greatly vary accordingly to specific road conditions, traffic congestion and legal regulations.

Conclusion: a single VirtualRouting Table can't be able to adequately support support the specific requirements and expectations of different users.
Defining more Routing Tables with different settings for the same Network usually is a good design choice leading to more realistic results.

Utility function for automatically setting NodeFrom and NodeTo IDs

Sometimes it could eventually happen to encounter some Spatial Network representation being fully topologically consistent but completely lacking any definition about NodeFrom and NodeTo identifiers.
In this specific case you can successfully recover a perfectly valid Network by calling the CreateRoutingNodes() SQL function. SELECT CreateRoutingNodes(NULL, 'table_name', 'geom', 'node_from', 'node_to'); _________________________ 1 Let's examine all arguments and their meaning:

NULL: name of the Attached-DB containing the Spatial Table.
It can be legitimately set to NULL, and in this case the MAIN DB is assumed.
table_name: name of the Spatial Table.
geom

: name of the column ((in the above Table) containing Linestrings.
node_from: name of the column to be added to the above Table and populated with appropriate NodeFrom IDs.

node_to: name of the column to be added to the above Table and populated with appropriate NodeTo IDs.
Note: both NodeFrom and NodeTo columns should not be already defined in the above Table.

CreateRoutingNodes() will return 1 (aka TRUE) on success; an exception will be raised on failure.
Note: you can call CreateRouting_GetLastError() so to precisely identify the cause accounting for failure.

Handling dynamic Networks
Sometimes it happens that a Network could be subject to rather frequent changes: some new Links require to be added, obsolete Links require to be removed, other Links may assume a different Cost, one-ways could be reversed, the discipline of pedestrian areas could be modified and so on.
A VirtualRouting Table is always based on a companion Binary Data Table, that is intrinsically static, and consequently you are required to re-create both them from time to time in order to support all recent changes affecting the underlaying Network.
The optimal frequency for cyclically refreshing the Routing Tables strictly depends on specific requirements, but the two overall approaches are commonly adopted:

low frequency refresh: best fit for slowly evolving Networks.
In this case re-creating the Network Tables once a month / week / day could be reasonably enough. Recreating the Tables from scratch usually requires several seconds (or even less, depending on the number of Links).
The refresh activities could be opportunely planned at low traffic hours (e.g. during the night), and CreateRouting() could be usefully called by enabling the overwrite option.

medium-high frequency refresh: best fit for quickly evolving Networks.
Re-creating the Network Tables once per hour (or even more frequently) could be strictly required, and frequent out of service periods while waiting for the refresh process to complete could easily be unacceptable.
In this case you could usefully adopt a multi-threaded strategy:

thread #1 (the reader): this first thread is intended to service any incoming Routing request. It will be always active, and will target a well known VirtualRouting Table (e.g. my_routing based on my_routing_data).

thread #2 (the writer): this second thread is just intended to re-create both Network Tables at predefined intervals, and it will sleep between an interval and the other.
When this thread awakens will re-create both Network Tables by using different names, and will overwrite the standard ones just at the very end of the process (activating a semaphore during this short-timed last step is highly recommended).
Something like this pseudo-code exemplifies: SELECT CreateRouting('new_my_routing_data', 'new_my_routing', ...); --> start the semaphore so to lock the other thread BEGIN; DROP TABLE my_routing; DROP TABLE my_routing_data; SELECT CloneTable('MAIN', 'new_my_routing_data', 'my_routing_data', 0); CREATE VIRTUAL TABLE my_routing USING VirtualRouting('my_routing_data'); DROP TABLE new_my_routing; DROP TABLE new_my_routing_data; COMMIT; --> remove the semaphore Note: strictly respecting the above sequence of SQL operations is absolutely required.

Warning: how to correctly drop Network Tables
When dropping a VirtualRouting Table and its companion Binary Data Table following the correct sequence of SQL commands is paramount.
Failing to strictly respect the expected sequence will surely cause you several troubles and severe headaches, and will possibly lead to an irremediably corrupted database.

you are always expected to DROP first the VirtualRouting Table.

you can safely DROP the companion Binary Data Table only once it's no longer referenced by the VirtualRouting Table.

by following the reverse sequence you'll directly create an orphan VirtualRouting Table that cannot be accessed any longer, and that will consequently refuse to be dropped.
Be warned !!

4 - Solving classic Shortest Path problems
The most classic Shortest Path problem requires to identify the optimal connection between an Origin Node and a Destination Node.
We can easily translate such a problem into a simple SQL query targeting some VirtualRouting Table. SELECT * FROM byfoot WHERE NodeFrom = 178731 AND NodeTo = 183286;

Algorithm Request Options Delimiter RouteId RouteRow Role LinkRowid NodeFrom NodeTo PointFrom PointTo Tolerance Cost Geometry Name

Dijkstra Shortest Path Full , [dec=44, hex=2c] 0 0 Route NULL 178731 183286 NULL NULL NULL 300.912208 BLOB sz=272 GEOMETRY NULL

NULL NULL NULL NULL 0 1 Link 224014 178731 182885 NULL NULL NULL 94.812424 NULL VIA PIETRO ARETINO

NULL NULL NULL NULL 0 2 Link 224446 182885 178880 NULL NULL NULL 69.727726 NULL VIA MARGARITONE

NULL NULL NULL NULL 0 3 Link 224414 178880 183286 NULL NULL NULL 136.372057 NULL VIA MARGARITONE

SELECT RouteRow, Role, LinkRowid, NodeFrom, NodeTo, Cost, Geometry, Name FROM byfoot WHERE NodeTo = 178731 AND NodeFrom = 183286;

RouteRow Role LinkRowid NodeFrom NodeTo Cost Geometry Name

0 Route NULL 183286 178731 300.912208 BLOB sz=272 GEOMETRY NULL

1 Link 224414 183286 178880 136.372057 NULL VIA MARGARITONE

2 Link 224446 178880 182885 69.727726 NULL VIA MARGARITONE

3 Link 224014 182885 178731 94.812424 NULL VIA PIETRO ARETINO

SELECT RouteRow, Role, LinkRowid, NodeFrom, NodeTo, Cost, Geometry, Name FROM bycar WHERE NodeFrom = 178731 AND NodeTo = 183286;

RouteRow Role LinkRowid NodeFrom NodeTo Cost Geometry Name

0 Route NULL 178731 183286 101.815552 BLOB sz=2032 GEOMETRY NULL

1 Link 224014 178731 182885 13.127874 NULL VIA PIETRO ARETINO

2 Link 224446 182885 178880 9.654608 NULL VIA MARGARITONE

3 Link 219171 178880 178732 7.809952 NULL VIA FRANCESCO CRISPI

4 Link 219058 178732 178754 12.445626 NULL VIA FRANCESCO CRISPI

5 Link 225888 178754 183461 1.599865 NULL VIA FRANCESCO CRISPI

6 Link 225887 183461 182800 3.300590 NULL VIA FRANCESCO CRISPI

7 Link 223935 182800 182799 6.688786 NULL VIALE LUCA SIGNORELLI

8 Link 226038 182799 183456 1.294017 NULL VIALE LUCA SIGNORELLI

9 Link 225832 183456 183444 2.385486 NULL VIALE LUCA SIGNORELLI

10 Link 225831 183444 183554 3.160662 NULL VIALE LUCA SIGNORELLI

11 Link 225765 183554 183954 7.469917 NULL VIALE LUCA SIGNORELLI

12 Link 225766 183954 183905 3.236389 NULL VIALE LUCA SIGNORELLI

13 Link 225979 183905 183626 13.983629 NULL STRADA SENZA NOME

14 Link 224905 183626 183128 5.627358 NULL STRADA SENZA NOME

15 Link 224897 183128 183286 10.030792 NULL VIA MARGARITONE

SELECT RouteRow, Role, LinkRowid, NodeFrom, NodeTo, Cost, Geometry, Name FROM bycar WHERE NodeTo = 178731 AND NodeFrom = 183286;

RouteRow Role LinkRowid NodeFrom NodeTo Cost Geometry Name

0 Route NULL 183286 178731 103.305259 BLOB sz=944 GEOMETRY NULL

1 Link 224414 183286 178880 18.882285 NULL VIA MARGARITONE

2 Link 219171 178880 178732 7.809952 NULL VIA FRANCESCO CRISPI

3 Link 219058 178732 178754 12.445626 NULL VIA FRANCESCO CRISPI

4 Link 224538 178754 181972 7.047784 NULL VIA ANTONIO GUADAGNOLI

5 Link 222575 181972 181971 1.852283 NULL VIA ANTONIO GUADAGNOLI

6 Link 224967 181971 182891 14.273185 NULL VIA ANTONIO GUADAGNOLI

7 Link 224168 182891 183057 6.643309 NULL VIA MACALLE'

8 Link 224167 183057 183056 3.151272 NULL VIA MACALLE'

9 Link 224174 183056 182941 7.966870 NULL VIA RODI

10 Link 224059 182941 182001 6.393747 NULL VIA RODI

11 Link 222637 182001 182000 2.475538 NULL VIA PIETRO ARETINO

12 Link 222636 182000 178731 14.363408 NULL VIA PIETRO ARETINO

back Z 217758f04e2669b07f85d096a2aa3a57

Algorithm	Request	Options	Delimiter	RouteRow	Role	LinkRowid	NodeFrom	NodeTo	PointFrom	PointTo	Tolerance	Cost	Geometry	Name
Dijkstra	Shortest Path	Full	, [dec=44, hex=2c]	0	Route	NULL	178731	183286	NULL	NULL	NULL	300.912208	BLOB sz=272 GEOMETRY	NULL
NULL	NULL	NULL	NULL	1	Link	224014	178731	182885	NULL	NULL	NULL	94.812424	NULL	VIA PIETRO ARETINO
NULL	NULL	NULL	NULL	2	Link	224446	182885	178880	NULL	NULL	NULL	69.727726	NULL	VIA MARGARITONE
NULL	NULL	NULL	NULL	3	Link	224414	178880	183286	NULL	NULL	NULL	136.372057	NULL	VIA MARGARITONE

Table of Contents