SpatiaLite VirtualNetwork

SpatiaLite 2.3.1 VirtualNetwork

The VirtualNetwork module enables SpatiaLite to support routing directly in SQL.
Routing is strongly based on the graph theory, and VirtualNetwork implements the well-known Dijkstra's Shortest Path algorithm.
If all this sounds quite unfamiliar to you, you can get some useful information at:
http://en.wikipedia.org/wiki/Graph_(mathematics)
http://en.wikipedia.org/wiki/Dijkstra's_algorithm

Building a Network

The first step requires building a Network, i.e. a peculiar data set representing a graph.
In order to accomplish this step you have to start from some raw data set [i.e. DB table] satisfying the following prerequisites:

each entity identifies a single arc, so has to be represented as a Linestring geometry.
Then no entity is allowed to have a NULL geometry.
each arc has to explicitly identify [using some kind of coding] its start node and end node.
Arcs may be unidirectional or bidirectional as well; we'll see better this later ...
For now we'll assume they are anyway unidirectional, i.e. each arc can be traversed only following the start-end direction.
a strong topological consistency is absolutely required.
i.e. any arc-point identifying the same node has to use exactly the same identical (x,y) coordinates.
And each arc has to be drawn following its start-end direction.
each arc requires to be associated with some meaningful cost; this may be represented by an explicit value, e.g. indicating the time required to traverse the arc.
As a default, the geometry length may be used as a cost value related to each arc.

You can download the test-network-2.3.sqlite sample DB required by following examples.
This actually represents the Italy's national road network [based on the Digital Chart of the World data].

The raw data are contained into the table named Roads [some 4,000 rows aka arcs].
The column layout for this Roads tables is:

column name	data type	meaning

PK_UID	INTEGER	the primary key identifying each arc
F_NODE	INTEGER	the code identifying the arc's start node
T_NODE	INTEGER	the code identifying the arc's end node
Type	TEXT	the road category [i.e. highway, primary ...]
Speed	INTEGER	the estimated mean speed [Km/h]
TravelTime	DOUBLE	the estimated arc traversal time [seconds] this one represents the arc's cost
Geometry	LINESTRING	the arc's geometry

Let us try this SQL query in order to better understand what is the real meaning of the term topological consistency:

PK_UID	F_NODE	T_NODE	X(StartPoint(Geometry))	Y(StartPoint(Geometry))	X(EndPoint(Geometry))	Y(EndPoint(Geometry))
SELECT PK_UID, F_NODE, T_NODE, X(StartPoint(Geometry)), Y(StartPoint(Geometry)), X(EndPoint(Geometry)), Y(EndPoint(Geometry)) FROM Roads WHERE F_NODE = 500 OR T_NODE = 500;


590	500	493	451431.332913	5035043.807065	460761.595951	5035818.198275
591	406	500	450462.268979	5051471.872834	451431.332913	5035043.807065
686	569	500	431913.235465	5026366.215484	451431.332913	5035043.807065
719	500	591	451431.332913	5035043.807065	453777.698717	5019713.609391

The node identified by value 500 is referred by four different arcs, both as a start or end node.
Anyway, the spatial coordinates for this node remains always identical, thus satisfying any topological consistency requirement.

network-1

We can now build a Network aka graph quite easily using the ad hoc tool supported by spatialite-gui.
After performing this task we can notice that:

now the database contains a new table, named Roads_net_data
and this table seems to contain quite meaningless binary data [aka BLOBs].
there is also a VirtualTable named Roads_net; and this one is an apparently empty table.
we'll see later how to use them; be a little more patient.

Using your own data, it's very alike that your supposed-to-be Network will fail to satisfy all the constraints required, for one reason or another.
In such an occurrence the user friendly spatialite-gui can offer you a very little help, because it simply reports some error and refuses to build the Network corresponding to your own data.
Don't fall in panic; you can now use the spatialite_network CLI tool; this latter implements a strong diagnostic tool, and will help you in identifying and correcting any error.

spatialite_network -d test_network-2.3.sqlite -T Roads \ -f F_NODE -t T_NODE -c TravelTime -g Geometry SQLite version: 3.6.12 SpatiaLite version: 2.3.0 Step I - checking for table and columns existence spatialite-network-validator ================================================================== SpatiaLite db: test_network-2.3.sqlite validating table: Roads columns layout ================================================================== FromNode: F_NODE ToNode: T_NODE Cost: TravelTime Geometry: Geometry assuming arcs to to be BIDIRECTIONAL simple validation required [NETWORK-DATA table creation is disabled] ================================================================== Step II - checking value types consistency Step III - checking topological consistency Step IV - final evaluation Statistics ================================================================== # Arcs : 8270 # Nodes: 3186 Node max incoming arcs: 7 Node max outcoming arcs: 7 # Nodes cardinality=1: 490 [terminal nodes] # Nodes cardinality=2: 828 [meaningless, pass-through] ================================================================== OK: network passed validation you can apply this configuration to build a valid VirtualNetwork OK: validation passed

Using Routing

All right, now we have built a valid Network, and we are finally ready to discover Routing.
Just to recapitulate:

we initially started form some raw data contained into a table name Roads
then we've built a corresponding Network: this actually consists in:
- a physical Roads_net_data table containing binary data
- a VirtualTable named Roads_net which is apparently empty
now we can go a little more in-depth, and discover that:
- the Roads_net_data actually contains a pre-build static [frozen] graph corresponding to our raw data.
  if the raw data change someway, then the static graph needs to be updated, but rebuilding again the network is a simple and quick task.
- the Roads_net VirtualTable simply implements an ad hoc interface supporting Routing queries.

ArcRowid	NodeFrom	NodeTo	Cost	Geometry
SELECT * FROM Roads_net WHERE NodeFrom = 1 AND NodeTo = 512;


NULL	1	512	22021.995764	BLOB sz=3376 GEOMETRY
1	1	4	3366.262555	NULL
11	4	16	1418.458904	NULL
15	16	20	868.499405	NULL
21	20	25	623.616463	NULL
22	25	24	186.070230	NULL
35	24	38	1825.020686	NULL
49	38	53	705.591126	NULL
67	53	66	2053.355052	NULL
121	66	114	1490.480401	NULL
183	114	169	1201.464297	NULL
225	169	207	907.687669	NULL
271	207	240	1552.639653	NULL
270	240	242	85.475589	NULL
310	242	281	394.516028	NULL
363	281	320	1692.810841	NULL
608	320	512	3650.046865	NULL

the only meaningful query you can perform on a VirtualNetwork table has the canonical form:
SELECT ... FROM prefix_net WHERE NodeFrom = node1_id AND NodeTo = node2_id
this will return a result set representing the routing solution [i.e. the shortest path] connecting the required start and end nodes.
if such a connection doesn't exists, then an empty result set will be returned.
the first row in the result set is a special one, and represents the whole travel solution, this including a corresponding Geometry.
then any following row identifies a single arc used by the travel solution, following the travel sequence.
you can easily distinguish between them because:
- the whole solution special row has ArcRowid = NULL and Geometry <> NULL
- any plain arc row has ArcRowid <> NULL and Geometry = NULL

back