SpatiaLite: VirtualNetwork reloaded

Introduction

Several relevant changes directly affecting the VirtualNetwork aka Routing module have been recently introduced (starting since version 4.2.1).
The present Wiki page is intended to be a comprehensive documentation about all relevant aspects.

optimization: several speed enhancements have been introduced
more flexibility: now a Geometry column is no longer required in order to get full Routing support
new features: VirtualNetwork tables aren't simply able to return Shortest Path solutions.
They can now return the full list of all Nodes directly connected to some Origin Node and not exceeding a given Connection Cost.

Such changes affects both the VirtualNetwork driver and the related supporting tools: spatialite_network and the equivalent dialog box available on spatialite_gui.
We'll now individually examine each single aspect one by one for the sake of clarity.

about No-Geometry Networks

There is no strict requirement dictating that every Network should necessarily include Geometries supporting both Nodes and Arcs.
A Network effectively supporting Geometries will surely get richer informations, will support a full Topological validation and will be able to represent each Shortest Path Solution as a Linestring.
Such features are surely welcome on every GIS/GeoSpatial platform.
Anyway they are not mandatory requisites imposed neither by the mathematical foundations of the Graph Theory nor by the Dijkstra's algorithm.
Supporting Geometries for a Network is more an optional bonus than a requirement.

A No-Geometry Network simply is a Network as any other but completely lacking any Geometry support.
It can safely support Shortest Path queries, with no other consequence except in that no graphical representation corresponding to the optimal Solution will be produced.
Just the Total Cost and the ordered list of all traversed Arcs will be returned in this case.

Corollary: a No-Geometry Network can just support the Dijkstra's algorithm, but not the spatially-oriented A* algorithm.

spatialite_network

Syntax:

usage: spatialite_network ARGLIST
==============================================================
-h or --help                      print this help message
-d or --db-path pathname          the SpatiaLite db path
-T or --table table_name          the db table to be validated
-f or --from-column col_name      the column for FromNode
-t or --to-column col_name        the column for ToNode
-g or --geometry-column col_name  the column for Geometry
-c or --cost-column col_name      the column for Cost
                                  if omitted, GLength(g)
                                  will be used by default

you can specify the following options as well:
----------------------------------------------
--a-star-supported                *default*
--a-star-excluded
-n or --name-column col_name      the column for RoadName
--bidirectional                   *default*
--unidirectional

if *bidirectional* each arc connecting FromNode to ToNode is
implicitly connecting ToNode to FromNode as well; in this case
you can select the following further options:
--oneway-tofrom col_name
--oneway-fromto col_name
both columns are expected to contain BOOLEAN values [1-0];
1 means that the arc connection in the given direction is
valid, otherwise 0 means a forbidden connection

in order to create a permanent NETWORK-DATA table
you can select the following options:
-o or --output-table table_name
-v or --virtual-table table_name
--overwrite-output

Relevant changes (since 4.2.1):

a new argument -v table_name or --virtual-table table_name is now supported: and it's intended to immediately create a VirtualNetwork table.
The previous version was simply capable to create the binary data table (-o table_name or --output-table table_name) but not the VirtualNetwork table itself; this further step previously required to execute a separate SQL statement.
the -g col_name or --geometry-column col_name argument now supports an extended semantic.
By specifying a NULL, NONE or NO column name a No-Geometry Network will then be assumed.

Example #1: creating a Geometry-based Network

$ spatialite_network -d tuscany_roads.sqlite -T road_arcs -f node_from \
      -t node_to -g geometry -c transit_time --oneway-fromto oneway_ft \
      --oneway-tofrom oneway_tf -n name -o roads_data -v roads_net \
      --overwrite-output
SQLite version: 3.8.7.1
SpatiaLite version: 4.2.1-rc0
Step   I - checking for table and columns existence

spatialite-network

==================================================================
   SpatiaLite db: tuscany_roads.sqlite
validating table: road_arcs

columns layout
==================================================================
FromNode: node_from
  ToNode: node_to
    Cost: transit_time
    Name: name
Geometry: geometry

assuming arcs to be BIDIRECTIONAL
OneWay To->From: oneway_tf
OneWay From->To: oneway_ft

NETWORK-DATA table creation required: 'roads_data'

VirtualNetwork table creation required: 'roads_net'
Overwrite allowed if table already exists
==================================================================

Step  II - checking value types consistency
Step III - checking topological consistency
Step  IV - final evaluation

Statistics
==================================================================
        # Arcs : 825633
        # Nodes: 381074
        Node max  incoming arcs: 15
        Node max outcoming arcs: 8
        # Nodes   cardinality=1: 92494 [terminal nodes]
        # Nodes   cardinality=2: 95226 [meaningless, pass-through]
==================================================================


OK: network passed validation
        you can apply this configuration to build a valid VirtualNetwork
OK: validation passed


OK: NETWORK-DATA table 'roads_data' successfully created
OK: table 'roads_data' successfully created
OK: table 'roads_net' successfully created
$

In this example we'll directly reuse the same DB-file created by spatialite_osm_overpass in this previous step
We'll now create a Network fully supporting Geometries; let's examine all the invocation arguments one by one and their corresponding meaning:

-d tuscany_roads.sqlite: path of the target DB-file.
-T road_arcs: name of the DB table containing the Arcs of the Graph.
-f node_from: name of the column identifying the From Node for each Arc.
-t node_to: name of the column identifying the To Node for each Arc.
-g geometry: name of the column containing the Geometry representing each Arc.
-c transit_time: name of the column containing the Cost corresponding to each Arc.
Please note: this is an optional argument. If not specified then the geometric Length of the Arc would be implicitly assumed to represent the Cost.
--oneway-fromto oneway_ft: name of the column containing a boolean switch stating if the corresponding Arc can be traversed in the normal direction.
--oneway-tofrom oneway_tf: name of the column containing a boolean switch stating if the corresponding Arc can be traversed in the reverse direction.
-o roads_data: name of the DB Table to be created (after successful validation) and intended to store binary data supporting the Network.
-v roads_net: name of the VirtualNetwork Table to be created after successful validation of the Graph.
--overwrite-output: an optional switch explicitly authorizing to eventually overwrite already existing Tables.

Example #2: creating a No-Geometry Network

$ spatialite_network -d tuscany_roads.sqlite -T road_arcs -f node_from \
      -t node_to -g NULL -c transit_time --oneway-fromto oneway_ft \
       --oneway-tofrom oneway_tf -n name -o roads_data_ng -v roads_net_ng \
       --overwrite-output

WARNING: a NO-GEOMETRY graph would be processed
the A* algorithm will be consequently disabled.

SQLite version: 3.8.7.1
SpatiaLite version: 4.2.1-rc0
Step   I - checking for table and columns existence

spatialite-network

==================================================================
   SpatiaLite db: tuscany_roads.sqlite
validating table: road_arcs

columns layout
==================================================================
FromNode: node_from
  ToNode: node_to
    Cost: transit_time
    Name: name
Geometry: *** unsupported ***

assuming arcs to be BIDIRECTIONAL
OneWay To->From: oneway_tf
OneWay From->To: oneway_ft

NETWORK-DATA table creation required: 'roads_data_ng'

VirtualNetwork table creation required: 'roads_net_ng'
Overwrite allowed if table already exists
==================================================================

Step  II - checking value types consistency
Step III - checking topological consistency
Step  IV - final evaluation

Statistics
==================================================================
        # Arcs : 825633
        # Nodes: 381074
        Node max  incoming arcs: 15
        Node max outcoming arcs: 8
        # Nodes   cardinality=1: 92494 [terminal nodes]
        # Nodes   cardinality=2: 95226 [meaningless, pass-through]
==================================================================


OK: network passed validation
        you can apply this configuration to build a valid VirtualNetwork
OK: validation passed


OK: NETWORK-DATA table 'roads_data_ng' successfully created
OK: table 'roads_data_ng' successfully created
OK: table 'roads_net_ng' successfully created
$

In this second example we'll use yet another time the previous DB-file.
This time we'll create an alternative No-Geometry Network; we'll examine just the relevant changes:

-g NULL: this is the special declaration specifically intended to request a No-Geometry Network.
-c transit_time: this is now a mandatory argument; a Cost column must be always declared for every No-Geometry Network.
-o roads_data_ng and -o roads_data_ng: names of the DB Tables to be created (after successful validation) and respectively intended as the binary data supporting the Network and the related VirtualNetwork.

building a Network using spatialite_gui

Starting since version 1.8.0 the dialog box allowing to create a Network now fully supports both Geometry-based and No-Geometry Networks.
And the user is finally free to set both names respectively identifying the binary data Table and the VirtualNetwork Table to be created.

VirtualNetwork SQL queries

Example #1: Shortest Path query (Geometry-based Network)

SELECT *
FROM roads_net
WHERE NodeFrom = 269352357 AND NodeTo = 269297531;
---------------------------------------------------------------------------------------------------------------------
Algorithm   ArcRowid     NodeFrom          NodeTo           Cost        Geometry                Name
---------------------------------------------------------------------------------------------------------------------
Dijkstra	NULL	269352357	269297531      33.499650	BLOB sz=160 GEOMETRY	NULL
Dijkstra      299120	269352357      2952899197	0.449321	NULL	                Via del Barco
Dijkstra      299121   2952899197	271849628	7.150417	NULL	                Via del Barco
Dijkstra      299122	271849628	269298255	7.863612	NULL	                Via del Barco
Dijkstra      311991	269298255	  8436031	5.330489	NULL	                Via Francesco Baracca
Dijkstra      311992	  8436031	269297718	7.425424	NULL	                Via Francesco Baracca
Dijkstra      311993	269297718	269297531	5.280386	NULL	                Via Francesco Baracca

This first example exactly corresponds to the conventional Routing SQL query as it was already supported by any earlier version:

WHERE NodeFrom = a and NodeTo = b: this clause is intended to select both the origin and the destination Nodes.
the first row of the returned resultset has a special meaning: it represents the overall Routing solution and contains the Total Cost and a Linestring graphically representing the Shortest Path.
the following rows of the returned resultset (excepting the first one) contain the ordered list of all Arcs to be traversed in order to connect the origin and the destination.

Example #2: Shortest Path query (No-Geometry Network)

SELECT *
FROM roads_net_ng
WHERE NodeFrom = 269352357 AND NodeTo = 269297531;
----------------------------------------------------------------------------------------------------------
Algorithm   ArcRowid     NodeFrom          NodeTo           Cost        Geometry    Name
----------------------------------------------------------------------------------------------------------
Dijkstra	NULL	269352357	269297531      33.499650	NULL   	    NULL
Dijkstra      299120	269352357      2952899197	0.449321	NULL	    Via del Barco
Dijkstra      299121   2952899197	271849628	7.150417	NULL	    Via del Barco
Dijkstra      299122	271849628	269298255	7.863612	NULL	    Via del Barco
Dijkstra      311991	269298255	  8436031	5.330489	NULL	    Via Francesco Baracca
Dijkstra      311992	  8436031	269297718	7.425424	NULL	    Via Francesco Baracca
Dijkstra      311993	269297718	269297531	5.280386	NULL	    Via Francesco Baracca

When executing the same SQL query on behalf of some No-Geometry Network just a single change will happen: in this case the Linestring in the first row of the returned resultset will be simply replaced by a NULL.

Example #3: displaying the Graphical Path (Geometry-based Network)

CREATE TABLE siena_viterbo AS
SELECT Geometry
FROM roads_net
WHERE NodeFrom = 681429057 AND NodeTo = 267162806
LIMIT 1;

SELECT RecoverGeometryColumn('siena_viterbo', 'geometry', 4326, 'LINESTRING', 'XY');

This is the graphical representation of a Routing Solution connecting the two towns of Siena and Viterbo as shown by QGIS (thick green line).
Please note: this Routing Solution clearly isn't the one presenting the shortest geometric length (thin pink line).
This is not surprising because in the previous steps we've set up a Cost parameter based on the estimated travel time once considered the expected average speeds accordingly to the functional classification of the Roads (aka Arcs).
Consequently the optimal Routing Solution is mainly based on Motorways; a faster connection is always preferred to any other shorter but slower alternative.

Example #4: Isochrone query (Geometry-based Network)

new feature: starting since 4.2.1

The Dijkstra's Shortest Path Algorithm internally works by repeatedly exploring all Nodes starting from the origin until the destination is finally reached; the available connections (aka Arcs) are always explored one after the other by strictly respecting a minimum Cost criterion and this ensures that any Dijkstra's Routing Solution is always an optimal solution.
Anyway the Dijkstra's Algorithm implicitly ensures a second interesting feature; it allows to identify all Nodes connected to some origin and requiring a Total Connection Cost not exceeding a given threshold.
This alternative capability intrinsically supported by the Dijkstra's Algorithm is usually referenced as isochrone analysis (aka isochrone map).
Starting since version 4.2.1 the VirtualNetwork module is now able to support this second option, as shown in the following example:

SELECT *
FROM roads_net
WHERE NodeFrom = 681429057 AND Cost <= 900;
----------------------------------------------------------------------------------------------------
Algorithm   ArcRowid     NodeFrom          NodeTo           Cost        Geometry                Name
----------------------------------------------------------------------------------------------------
Dijkstra	NULL	681429057	  6719364      830.557913	BLOB sz=60 GEOMETRY	NULL
Dijkstra	NULL	681429057	  6719364      830.557913	BLOB sz=60 GEOMETRY	NULL
....            ...           ...             ...             ...       ...                     ...
Dijkstra	NULL	681429057      3166959013      672.054002	BLOB sz=60 GEOMETRY	NULL
Dijkstra	NULL	681429057      3166959016      671.511763	BLOB sz=60 GEOMETRY	NULL

WHERE NodeFrom = a and Cost <= b: this clause is intended to select both the origin Node and the maximum Cost threshold.
all rows in the returned resultset contain a destination Node connected to the origin Node and the corresponding total connection Cost.

Example #5: Isochrone query (No-Geometry Network)

SELECT *
FROM roads_net_ng
WHERE NodeFrom = 681429057 AND Cost <= 900;
---------------------------------------------------------------------------------------
Algorithm   ArcRowid     NodeFrom          NodeTo           Cost        Geometry   Name
---------------------------------------------------------------------------------------
Dijkstra	NULL	681429057	  6719364      830.557913	NULL	   NULL
Dijkstra	NULL	681429057	  6719364      830.557913	NULL	   NULL
....            ...           ...             ...             ...       ...        ...
Dijkstra	NULL	681429057      3166959013      672.054002	NULL	   NULL
Dijkstra	NULL	681429057      3166959016      671.511763	NULL	   NULL

When executing the same SQL query on behalf of some No-Geometry Network just a single change will happen: in this case any Point Geometry corresponding to the position of each Node will be simply replaced by a NULL in the returned resultset.

Example #6: displaying an Isochrone Map (Geometry-based Network)

CREATE TABLE min_15 AS
SELECT NodeTo AS NodeId, Geometry
FROM roads_net
WHERE NodeFrom = 681429057 AND Cost <= 900;
SELECT RecoverGeometryColumn('min_15', 'geometry', 4326, 'POINT', 'XY');

CREATE TABLE min_30 AS
SELECT NodeTo AS NodeId, Geometry
FROM roads_net
WHERE NodeFrom = 681429057 AND Cost <= 1800;
SELECT RecoverGeometryColumn('min_30', 'geometry', 4326, 'POINT', 'XY');

CREATE TABLE min_45 AS
SELECT NodeTo AS NodeId, Geometry
FROM roads_net
WHERE NodeFrom = 681429057 AND Cost <= 2700;
SELECT RecoverGeometryColumn('min_45', 'geometry', 4326, 'POINT', 'XY');

CREATE TABLE min_60 AS
SELECT NodeTo AS NodeId, Geometry
FROM roads_net
WHERE NodeFrom = 681429057 AND Cost <= 3600;
SELECT RecoverGeometryColumn('min_60', 'geometry', 4326, 'POINT', 'XY');

This is the graphical representation of an Isochrone Map as shown by QGIS. The origin Node is located in the center town of Siena.

all Nodes within a 15 minutes travel time are shown as green circles.
within 30 minutes: purple circles.
within 45 minutes: orange circles.
within 60 minutes: magenta circles.

back