## SpatiaLite 2.3.1          VirtualNetwork

back
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.
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 namedata typemeaning

PK_UIDINTEGERthe primary key identifying each arc
F_NODEINTEGERthe code identifying the arc's start node
T_NODEINTEGERthe code identifying the arc's end node
TypeTEXTthe road category [i.e. highway, primary ...]
SpeedINTEGERthe estimated mean speed [Km/h]
TravelTimeDOUBLEthe estimated arc traversal time [seconds]
this one represents the arc's cost
GeometryLINESTRINGthe 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.

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

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