Warning

This page is obsolete and contains outdated information. It's still available only to preserve full historical record.

 Fine dining experience: Chez Dijkstra 2011 January 28

 SpatiaLite supports an internal routing module called VirtualNetwork Starting from an arbitrary network this module allows to identify shortest path connections using simple SQL queries. The VirtualNetwork module supports sophisticated and highly optimized algorithms, so it's really fast and very efficient even using huge sized networks.

 Network foundations You cannot assume that any generic road layer corresponds to a network. A real network must satisfy several specific prerequisites, i.e. it has to be a graph. Graph theory is a wide and complex branch of mathematics; if you are interested in this, here you can get some further details: Graph Theory Shortest Path Problem Dijkstra's Algorithm A* Algorithm Very shortly explained: a network is a collection of arcs each single arc connects two nodes each arc has an unique direction: i.e. the arc going from A-node to B-node is not necessarily the same one going from B to A each arc has a well known cost (e.g. length, travel time, capacity, ...) both arcs and nodes must expose some explicitly defined unique identifier. geometries of arcs and nodes must satisfy a strong topological consistency. Starting from a network aka graph both Dijkstra's and A* algorithms can then identify the shortest path (minimal cost connection) connecting any arbitrary couple of nodes.

 There are several sources distributing network-like data. One of the most renowned and widely used is OSM [Open Street Map], a completely free worldwide dataset. There are several download sites distributing OSM; just to mention the main ones: Anyway in the following example we'll download the required OSM dataset from: www.gfoss.it Most precisely we'll download the TOSCANA.osm.bz2 dataset.

Step 1: you must uncompress the OSM dataset.
This file is compressed using the bzip2 algorithm, widely supported by many open source tools.
e.g. you can use 7-zip to unzip this file. www.7-zip.org

Step 2: any OSM dataset simply is an XML file
(you can open this file using any ordinary text editor at your choice).
SpatiaLite supports a specific CLI tool allowing to load an OSM dataset into a DB: spatialite_osm_net

Very briefly explained:
• -o TOSCANA.osm selects the input OSM dataset to be loaded.
• -d tuscany.sqlite selects the output DB to be created and populated.
• -T tuscany will create the Geometry Table storing the OSM dataset
• -m an in-memory database will be used, so to perform data import in the shortest time.
 SELECT * FROM tuscany;

 id osm_id class node_from node_to name oneway_from_to oneway_to_from length cost geometry ... ... ... ... ... ... ... ... ... ... ... 2393 8079944 tertiary 659024545 659024546 Via Cavour 1 1 7.468047 0.537699 BLOB sz=80 GEOMETRY 2394 8079944 tertiary 659024546 156643876 Via Cavour 1 1 12.009911 0.864714 BLOB sz=96 GEOMETRY 2395 8083989 motorway 31527668 319386487 Autostrada del Sole 1 0 424.174893 13.882087 BLOB sz=80 GEOMETRY 2396 8083990 motorway 31527665 31527668 Autostrada del Sole 1 0 130.545183 4.272388 BLOB sz=112 GEOMETRY ... ... ... ... ... ... ... ... ... ... ...
Just a quick check:
• a single Tuscany table exists into the DB created by spatialite_osm_net
• each row in this table corresponds to a single network arc
• the nodes connected by each arc are identified by node_from and node_to
• oneway_from_to and oneway_to_from determine if the arc can be walked in both directions or not.
• length is the geometric length of the arc (measured in meters).
• cost is the estimated travel time (expressed in seconds).
• geometry is the LINESTRING representation corresponding to the arc.
Please note #1: there is no separate representation for nodes, simply because they can be indirectly retrieved starting from the corresponding arcs.

Please note #2: this one surely is a real network, but in this form cannot yet support routing queries.
A further step is still required, i.e. creating a VirtualNetwork table.

We'll use spatialite_gui to create the VirtualNetwork table.
Anyway the same operation is supported as well by the spatialite_network CLI tool
(and this CLI tool supports an extended diagnostic capability, useful to identify any eventual problem).

 SELECT * FROM tuscany_net WHERE NodeFrom = 267209305   AND NodeTo = 267209702;

 Algorithm ArcRowid NodeFrom NodeTo Cost Geometry Name Dijkstra NULL 267209305 267209702 79.253170 BLOB sz=272 GEOMETRY NULL Dijkstra 11815 267209305 250254381 11.170037 NULL Via Guelfa Dijkstra 11816 250254381 250254382 8.583739 NULL Via Guelfa Dijkstra 11817 250254382 250254383 12.465016 NULL Via Guelfa Dijkstra 16344 250254383 256636073 15.638407 NULL Via Cavour Dijkstra 67535 256636073 270862435 3.147105 NULL Piazza San Marco Dijkstra 25104 270862435 271344268 5.175379 NULL Piazza San Marco Dijkstra 25105 271344268 82591712 3.188657 NULL Piazza San Marco Dijkstra 11802 82591712 267209666 4.978328 NULL Piazza San Marco Dijkstra 20773 267209666 267209702 14.906501 NULL Via Giorgio La Pira
And finally you can now test your first routing query:
• you simply have to set the WHERE NodeFrom = ... AND NodeTo = ... clause.
• and a result-set representing the shortest path solution will be returned.
• the first row of this result-set summarizes the whole path, and contains the corresponding geometry.
• any subsequent row represents a single arc to be traversed, following the appropriate sequence, so to go from origin to destination.
 UPDATE tuscany_net SET Algorithm = 'A*'; UPDATE tuscany_net SET Algorithm = 'Dijkstra';
SpatiaLite's VirtualNetwork tables support two alternative algorithms:
• Dijkstra's shortest path is a classic routing algorithm, based on thorough mathematical assumptions, and will surely identify the optimal solution.
• A* is an alternative algorithm based on heuristic assumptions:
it is usually faster than Dijkstra's, but under some odd condition may eventually fail, or may return a sub-optimal solution.
• anyway switching from the one to the other is really simple.
• using the Dijksta's algorithm is the default selection.
 A VirtualNetwork table simply represents a staticized snapshot of the underlying network. This allows to adopt an highly efficient binary representation (in other words, allows to produce solutions in a very quick time), but obviously doesn't supports dynamic changes. Each time the underlying network changes the corresponding VirtualNetwork must be DROPped and then created again, so to correctly reflect the latest network state. In many cases this isn't an issue at all: but on some highly dynamic scenario this may be a big annoyance. Be well conscious of this limitation.

 Author: Alessandro Furieri a.furieri@lqt.it This work is licensed under the Attribution-ShareAlike 3.0 Unported (CC BY-SA 3.0) license. Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.3 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts.