D 2018-04-01T19:53:48.949
L VirtualRouting
P eb4769d3b31190e5253b0df56d0661ff076d744a
U sandro
W 22831
<a href="https://www.gaia-gis.it/fossil/libspatialite/wiki?name=4.3.0-doc">back</a><hr><br>
<h1>Table of Contents</h1>
1 - <a href="#intro">Introduction</a><br>
2 - <a href="#sample">The sample/test DB</a><br>
3 - <a href="#create">Creating VirtualRouting Tables</a><br>
<br><hr>
<h1><a name="intro">1 -Introduction</a></h1>
Previous versions of SpatiaLite traditionally supported a <b>pure SQL routing module</b> that was named <a href="https://www.gaia-gis.it/fossil/libspatialite/wiki?name=VirtualNetwork+reloaded">VirtualNetwork</a>.<br><br>
Since version <b>5.0.0</b> a brand new <b>routing module</b> (more advanced and sophisticated) is available, that is called <b>VirtualRouting</b>.<br>
The now obsolete <b>VirtualNetwork</b> is still supported by version <b>5.0.0</b> so as to not cause an abrupt break to already existing applications, but will presumably be discontinued in future versions.<br>
Using <b>VirtualRouting</b> instead of <b>VirtualNetwirk</b> is warmly recommended for any new development.
<h2>Theoretical foundations - an ultra-quick recall</h2>
All <b>Routing algorithms</b> (<i>aka</i> <b>Shortest Path</b> algorithms) are based on the mathematics of the <a href="https://en.wikipedia.org/wiki/Graph_theory">Graph theory</a> or to be more precise: on <b>Weighted Graphs</b>.
<br>
<img src="http://www.gaia-gis.it/gaia-sins/network.png" alt="network">
<br>
A topologically valid <b>Network</b> is a dataset that fulfills the following requirements:
<ul>
<li>All items in the dataset are called <b>Links</b> (<i>aka</i> <b>Arcs</b>), and are expected to represent some oriented connection joining two <b>Nodes</b>.<br>
<u>Example</u>: in the above figure Link <b>L3</b> connects Nodes <b>N2</b> and <b>N5</b>.</li>
<li>So all <b>Links</b> are always expected to explicitly reference a <b>Start-Node</b> (<i>aka</i> <b>Node-From</b>) and an <b>End-Node</b> (<i>aka</i> <b>Node-To</b>).
<ul>
<li>Links are always <b>oriented</b>, and their natural direction is <b>From-To</b>:
<ul>
<li>in an <b>unidirectional</b> Network each Link is an <b>one-way</b> connection.<br>
If the connection is available in the opposite direction a second Link must be explicitly declared.<br>
<u>Example</u>: Link <b>X1</b> goes from Node <b>A</b> to Node <b>B</b>, and Link <b>X2</b> goes from Node <b>B</b> to Node <b>A</b>.</li>
<li>in a <b>bidirectional</b> Network all Links are assumed to establish a connection in both directions.<br>
Definiting an <b>one-way connection</b> requires an appropriate attribute to be set (see below).</li>
</ul></li>
<li>The <b>Start-</b> and <b>End-Node</b> could eventually be the same, and in this case we'll have a <b>self-closed</b> Link.</li>
<li>Network's Links <b>can</b> eventually define a linear Geometry (<b>LINESTRING</b>) going from the <b>Start-Node</b> to the <b>End-Node</b>, but this is an optional feature, not a mandatory requirement.</li>
<li>What is absolutely mandatory is that each <b>Link</b> must explicitly reference its <b>Nodes</b>.</li>
</ul></li>
<li>A Network supporting Geometries is a <b>Spatial Network</b>; otherwise a Network lacking any Geometry is a <b>Logical Network</b>.
<ul>
<li>In a <b>Spatial Network</b> all Links <b>must</b> have a corresponding Geometry.</li>
<li>In a <b>Logical Network</b> all Links <b>are strictly forbidden</b> to have any Geometry.</li>
<li>In a <b>Spatial Network</b> both the <b>StartPoint</b> and <b>EndPoint</b> of each Link's <b>LINESTRING</b> are always expected to exactly coincide with the corresponding <b>Nodes</b>.</li>
</ul></li>
<li>In a <b>Spatial Network</b> all references to the same <b>Node</b> by different Links <b>must</b> be an exact match.<br>
<u>Example</u>: Node <b>N5</b> is shared by Links <b>L3</b>, <b>L6</b>, <b>L7</b>, <b>L9</b> and <b>L10</b>, so all their corresponding LINESTRINGS are expected to have the corresponding extremity (<b>Start-</b> or <b>End-</b>, depending on the orientation) points that must exactly match the other.<br>
A <b>topological inconsistency</b> exists if any of these conditions are not satisfied, which leads to an <b>invalid</b> Network.</li>
<li>In a <b>Spatial Network</b> two
<li>Accordingly to the above premises, <b>Nodes</b> are never expected to be explicitly declared in a separate Table.<br>
Just a single Table declaring all <b>Links</b> is required in order to fully define a topologically valid Network.<br>
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.<br>
If any mismatch is detected this surely means that the Network is invalid.</li>
<li>A <b>Link</b> may legitimately self-intersect itself (e.g. forming a loop), as shown in the above figure by Link <b>L15</b> (orange spot).</li>
<li>Two <b>Links</b> may legitimately intersect where no Node exists, as exemplified on the above figure by Links <b>L4</b> and <b>L7</b> (green spot).<br>
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).</li>
<li><b>Links</b> aren't strictly required to be associated with any specific attribute, but the following attributes are almost universally supported:
<ul>
<li>a <b>name</b> identifying the Link.<br>
<u>Examples</u>: the <i>road toponym</i> in a <b>road network</b>, or the <i>river name</i> in an <b>hydrographic network</b>.</li>
<li>one (or even more) appropriate <b>cost value</b>(s).<br>
<u>Example</u>: the <i>time</i> required to traverse the Link (may be distinguished between pedestrians, bicycles, cars, lorries and so on).</li>
<li>a pair of <b>boolean flags</b> (<b>from-to</b> and <b>to-from</b>) are intendend to specify if the Link can be traversed on both directions or just in one (<b>one-way</b>).</li>
</ul></li>
</ul>
<h4>Logical conclusions</h4>
Any topologically valid <b>Network</b> (irrespective of whether it is a <b>Spatial</b> or <b>Logical</b> type) is a valid <b>Graph</b>.<br>
A Network allowing the support (direct or indirect) of some appropriate <b>cost value</b> is a valid <b>Weighted Graph</b>, and can consequently support <b>Routing algorithms</b>.<br>
All Routing algorithms are intended to identify the <b>Shortest Path</b> solution connecting two <b>Nodes</b> in a <b>weighted graph</b> (<i>aka</i> <b>Network</b>).<br><br>
<b><u>Note</u></b>: the term <b><i>Shortest Path</i></b> can be easily misunderstood.<br>
Due to historical reasons the most common application field for Routing algorithms is related to <b>Road Networks</b>, but also many other kinds of Networks exist:
<ul>
<li>Hydrographic Networks.</li>
<li>Gas / Water / Oil Networks.</li>
<li>Electrical Networks.</li>
<li>Telecomunication Networks.</li>
<li>Social or Economical Networks representing relationships between individuals or companies.</li>
<li>Epidemiological Networks representing the propagation of infective diseases between individuals or groups.</li>
</ul></li>
<br>
In all the above cases we certainly have valid Networks supporting Routing algorithns, but not all of them can imply something like a <i>spatial distance</i> (<i>geometric length</i>) or a <i>travel time</i>.<br>
In the most general acception <b>costs</b> can be represented by any reasonable physical quantity.<br>
So a more generalized definition is assuming that Routing algorithms are intended to identify <b>lesser cost</b> solutions on a <b>weighted graph</b>.<br>
The exact interpretation of the involved <b>costs</b> (<i>aka</i> <b>weights</b>) strictly depends on the very specific nature of each Network.
<h3>The Dijkstra's algorithm</h3>
This well known <a href="https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm">algorithm</a> isn't necessarily the fastest one, but it always ensures <b>full correctness</b>:
<ul>
<li>Any Node-to-Node connection identified by Dijkstra's is certainly ensured to be <b>optimal</b>.<br>
In other words, no connetction presenting a lower cost can conceptually exist.</li>
<li>When Dijsjtra's fails to identify a solution this surely means that no solution is possible.</li>
</ul>
<h3>The A* algorithm</h3>
Many alternative Routing algorithms have been invented during the years.<br>
All them are based on heuristic assumptions and are intended to be faster than Dijkstra's, but none of them can ensure <b>full correctness</b> as Dijkstra's does.<br>
The <a href="https://en.wikipedia.org/wiki/A*_search_algorithm">A* algorithm</a> applies a mild heuristic optimization, and can be a realistic alternative to Dijkstra's in many cases.<br><br>
<hr>
<h1>2 - The sample/test DB</h1>
You are expected to follow the current tutorial about <b>VirtualRouting</b> by directly testing all SQL queries discussed below on behalf of the <a href="https://www.gaia-gis.it/gaia-sins/routing-sample-5.0.0.7z">sample/test DB that you can download from here</a><br><br>
The sample DB contains the full <b>road network</b> of <b>Tuscany Region (Italy)</b> (<a href="http://www502.regione.toscana.it/geoscopio/download/grafo_stradale/iternet.zip">Iter.Net dataset</a>) kindly released under the <b>CC-BY-SA 4.0</b> licence terms.<br>
The contents stored into the sample database were opportunely rearranged, and are still subject to the initial <b>CC-BY-SA 4.0</b> clauses (<i>derived work</i>).
<br><br>
<ul>
<li>all road names are stored within the <b>toponyms</b> Table.<br>
the same road name could be used in different Municipalities, so the <b>toponyms</b> Table relationally references the <b>municipalities</b> Table (via <b>PRIMARY</b> / <b>FOREIGN KEY</b> relationships).</li>
<li>the <b>roads</b> Spatial Table contains about <b>380,000</b> Links, and has the following columns:
<ul>
<li><b>id</b>: unique identifier of each Link (<b>PRIMARY KEY</b>).</li>
<li><b>node_from</b> and <b>node_to</b>: Node identifiers.
The original Iter.Net dataset adopts very long an complex alphanumeric Node codes; the integer Node IDs were obtained by calling the <b>CreateRoutingNodes()</b> SQL function discussed in a following section.</li>
<li><b>id_toponym</b>: relational reference to the corresponding road name contained into the <b>toponyms</b> Table (<b>FOREIGN KEY</b>).</li>
<li><b>speed_kmh</b>: the estimated average speed supported by the Link, expressed in <b>km/h</b>.<br>
<u>Note</u>: <b>negative</b> speeds intend a forbidden Link.</li>
<li><b>oneway_fromto</b> and <b>oneway_tofrom</b>: boolean flags intended to state if a Link can be traversed in both directions or just in a single direction (<b>one-way</b>).<br>
<u>Note</u>: all Links declaring <b>oneway_fromto=0</b> and <b>oneway_tofrom=0</b> are intended to be always forbidden.</li>
<li><b>cost</b>: the <b>time</b> expressed in <b>seconds</b> required to traverse each Link.<br>
<u>Note #1</u> all costs were calculated accordingly to the following formula: <b>cost = ((ST_Length(geom) / 1000.0) / speed_kmh) * 3600.0</b><br>
<u>Note #2</u> all <b>86,400.0</b> cost values (equivalent to 1 day) approximate an <b>infinitive cost</b> thus intending a <b>forbidden</b> Link.</li>
<li><b>geom</b>: a <b>3D Linestring</b> representing the Geometry of each Link.<br>
<u>Note</u>: the original <b>Iter.Net</b> dataset is just <b>2D</b>; elevations (<b>Z</b> coordinates) were interpolated by draping the dataset over an <a href="http://www502.regione.toscana.it/geoscopio/download/altimetria/da_ctr10k/gb/DTM_Orografico.7z">orographic DEM (10m X 10m cells)</a></li>
</ul></li>
<li>the <b>roads_vw</b> Spatial View is just intended to fully resolve all relational references between <b>roads</b>, <b>toponyms</b> and <b>municipalities</b>, thus allowing for easier SQL queries.</li>
<li>the <b>house_nr</b> Spatial Table contains about <b>1,480,000</b> House Numbers, and has the following columns:
<ul>
<li><b>id</b>: unique identifier of each House Number (<b>PRIMARY KEY</b>).</li>
<li><b>id_road</b>: relational reference to the corresponding Link contained into the <b>roads</b> Table (<b>FOREIGN KEY</b>).</li>
<li><b>label</b>: the textual label fully qualifying each House Number.</li>
<li><b>geom</b>: a <b>3D Point</b> representing the Geometry of each House Number.<br>
<u>Note #1</u>: also in this case all elevations (<b>Z</b> coordinates) were interpolated by draping the dataset over the same DEM as above.<br>
<u>Note #2</u>: 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.</li>
</ul></li>
<li>the <b>house_nr_vw</b> Spatial View is just intended to fully resolve all relational references between <b>house_nr</b>, <b>roads</b>, <b>toponyms</b> and <b>municipalities</b>, thus allowing for easier SQL queries.</li>
</ul>
<br>
<hr>
<h1><a name="create">3 - Creating VirtualRouting Tables</a></h1>
All VirtualRouting queries are based on some <b>VirtualRouting Table</b>, and in turn any VirtualRouting Table is based on some appropriate <b>Binary Data Table</b> supporting an efficient representation of the underlying Network.<br>
So we'll start first by creating such tables.<br><br>
The old and now superseded <b>VirtualNetwork</b> required using a separate CLI tool (<b>spatialite_network</b>) in order to properly initialize a VirtualNetwork Table and its companion Binary Data Table;
alternatively <b>spatialite_gui</b> supported a <b>GUI wizard</b> for the same task. Since version <b>5.0.0</b> now SpatiaLite directly supports a specific <b>CreateRouting()</b> SQL function.
<verbatim>
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
</verbatim>
<u>Note</u>: this first query contains an intended error causing <b>CreateRouting()</b> to fail raising an exception.<br>
CreateRouting() can fail for multiple reasons, and by calling <b>CreateRouting_GetLastError()</b> you can easily identify the exact reason why the most recent call to CreateRouting() failed.<br>
<verbatim>
SELECT CreateRouting('byfoot_data', 'byfoot', 'roads_vw', 'node_from', 'node_to', 'geom', NULL);
-------------
1
SELECT CreateRouting_GetLastError();
------------------------------------
NULL
</verbatim>
This second attempt if finally successful, and now CreateRouting() returns <b>1</b> (<i>aka</i> <b>TRUE</b>), and as you can easily check now the Database contains two new Tables: <b>byfoot</b> and <b>byfoot_data</b>.<br>
<u>Note</u>: after a successful call to CreateRouting() <b>CreateRouting_GetLastError()</b> will always return <b>NULL</b>.<br><br>
You've just used the <i>reduced form</i> of CreateRouting(); let's see in more depth all the arguments and their meaning:
<ol>
<li><i>byfoot_data</i>: the name of the Network Binary Data Table to be created.</li>
<li><i>byfoot</i>: the name of the VirtualRouting Table to be created.</li>
<li><i>roads_vw</i>: the name of the <b>Spatial Table</b> or <b>Spatial View</b> representing the underlying Network.<br>
<u>Note</u>: in this case we actually used a Spatial View.</li>
<li><i>node_from</i>: name of the column (in the above Table or View) expected to contain <b>node-from</b> values.</li>
<li><i>node_to</i>: name of the column (in the above Table or View) expected to contain <b>node-to</b> values.</li>
<li><i>geom</i>: name of the column (in the above Table or View) expected to contain <b>Linestrings</b>.<br>
We could have legitimately passed a <b>NULL</b> value for this argument in the case of a <b>Logical Network</b>.</li>
<li><i>NULL</i>: name of the column (in the above Table or View) expected to contain <b>cost</b> values.<br>
In this case we have passed a <b>NULL</b> value, and consequently the <b>cost</b> of each Link will be assumed to be represented by the <b>geometric length</b> of the corresponding Linestring.<br>
<u>Note #1</u>: in the case of Networks based on <b>longitudes</b> and <b>latitudes</b> (<i>aka</i> <b>geographic</b> Reference Systems) the geometry length of all Linestrings will be precisely <b>measured on the ellipsoid</b> by applying the most accurate <b>geodesic formulae</b> and will be consequently expressed in <b>meters</b>. In any other case (<b>projected</b> Reference Systems) lengths will be expressed in the <b>measure unit</b> defined by the Reference System (e.g. <b>meters</b> for <b>UTM</b> projections and <b>feet</b> for <b>NAD-ft</b> projections).<br>
<u>Note #2</u>: the <b>geom-column</b> and <b>cost-column</b> arguments are never allowed to be <b>NULL</b> at the same time.</li>
</ol>
<table bgcolor="#c0ffc0" cellspacing="10" cellpadding="6"><tr><td>
<h3>Technical note</h3>
The internal encoding adopted by the <b>Binary Data Table</b> is unchanged and is the same for both <b>VirtualNetwok</b> and <b>VirtualRouting</b>.<br>
You can safely base a <b>VirtualRouting Table</b> on any existing Binary Data
Table created by the <b>spatialite-network</b> CLI tool, exactly as you can base a <b>VirtualNetwork Table</b> on any Binary Data Table created by the <b>CreateRouting()</b> SQL function.
<verbatim>
CREATE VIRTUAL TABLE test_network USING VirtualNetwork('some_data_table');
CREATE VIRTUAL TABLE test_routing USING VirtualRouting('some_data_table');
</verbatim>
In order to manually create your Virtual Tables you just have to execute an appropriate <b>CREATE VIRTUAL TABLE ... USING Virtual... (...)</b> statement.
<h4>Warning</h4>
In the case of <b>Spatial Networks</b> based on any <b>geographic</b> Reference System (using <b>longitudes</b> and <b>latitudes</b>) there is an important difference between Binary Data Tables created by the <b>spatialite_network</b> GUI tool and Binary Data Tables created by the <b>CreateRouting()</b> SQL function when <b>costs</b> are implicitly based on the geometric length of the Link's Linestring:
<ul>
<li>the <b>spatialite_network</b> CLI tool (and the <b>GUI wizard</b> implemented by previous versions of <b>spatialite_gui</b>) compute the Linestring's length as an <b>angular distance</b> expressed in <b>degrees</b>.</li>
<li>the <b>CreateRouting()</b> SQL function computes the Linestring's length as a <b>linear distance</b> expressed in <b>metres</b> by applying the most accurate <b>geodesic formulae</b> on the ellipsoid.</li>
</ul>
</td></tr></table><br><br>
<verbatim>
SELECT CreateRouting('bycar_data', 'bycar', 'roads_vw', 'node_from', 'node_to', 'geom', 'cost', 'toponym', 1, 1, 'oneway_fromto', 'oneway_tofrom', 0);
--------------------
1
</verbatim>
After calling yet another time <b>CreateRouting()</b> now the Database contains two further Tables: <b>bycar</b> and <b>bycar_data</b>.<br>
This time you've used the <i>complete form</i> of CreateRouting(); let's see in more depth all the arguments and their meaning:
<ol>
<li><i>bycar_data</i>: same as above.</li>
<li><i>bycar</i>: same as above.</li>
<li><i>roads_vw</i>: same as above.</li>
<li><i>node_from</i>: same as above.</li>
<li><i>node_to</i>: same as above.</li>
<li><i>geom</i>: same as above.</li>
<li><i>cost</i>: same as above.
In this case we have referenced a column preloaded with values corresponding to the <b>time</b> measured in <b>seconds</b> required to traverse each Link.</li>
<li><i>toponym</i>: name of the column (in the above Table or View) expected to contain <b>road-name</b> values.<br>
It could be legitimately set to <b>NULL</b> if all Links are anonymous.</li>
<li><i>1</i>: a boolean flag intended to specify if the Network must support the <b>A* algorithm</b> or not (set to <b>TRUE</b> by default).</li>
<li><i>1</i>: a boolean flag intended to specify if all Network's Links are assumed to be <b>bidirectional</b> or not (assumed to be <b>TRUE</b> by default).</li>
<li><i>oneway_fromto</i>: name of the column (in the above Table or View) expected to contain boolean flags specifying if each Link can be traversed in the <b>from-to</b> direction or not.</li>
<li><i>oneway_tofrom</i>: name of the column (in the above Table or View) expected to contain boolean flags specifying if each Link can be traversed in the <b>to-from</b> direction or not.<br>
<u>Note #1</u>: both <b>from-to</b> and <b>to-from</b> column names can be legitimately set as <b>NULL</b> if no <b>one-way</b> restrictions apply to the current Network.<br>
<u>Note #2</u>: Networks of the <b>unidirectional</b> type are never enabled to reference <b>one-way</b> columns (they should always be set to <b>NULL</b>).</li>
<li><i>0</i>: a boolean flag intending an <b>overwrite authorization</b>.
<ul>
<li>If set to <b>FALSE</b> an exception will be raised if the <b>Binary Data Table</b> and/or the <b>VirtualRouting Table</b> do already exist.</li>
<li>If set to <b>TRUE</b> eventually existing Tables will be preventively dropped immediately before starting the execution of <b>CreateRouting()</b>.</li>
</ul></li>
</ol>
<h3>Automatically setting NodeFrom and NodeTo IDs</h3>
Sometimes it could eventually happen to encounter some <b>Spatial Network</b> representation being fully topologically consistent but completely lacking any definition about <b>NodeFrom</b> and <b>NodeTo</b> identifiers.<br>
In this specific case you can successfully recover a perfectly valid Network by calling the <b>CreateRoutingNodes()</b> SQL function.
<verbatim>
SELECT CreateRoutingNodes(NULL, 'table_name', 'geom', 'node_from', 'node_to');
_________________________
1
</verbatim>
Let's examine all arguments and their meaning:
<ol>
<li><i>NULL</i>: name of the <b>Attached-DB</b> containing the Spatial Table.<br>
It can be legitimately set to <b>NULL</b>, and in this case the <b>MAIN</b> DB is assumed.</li>
<li><i>table_name</i>: name of the Spatial Table.</li>
<li><i>geom</li>: name of the column ((in the above Table) containing <b>Linestrings</b>.</li>
<li><i>node_from</i>: name of the column to be added to the above Table and populated with appropriate <b>NodeFrom</b> IDs.</li>
<li><i>node_to</i>: name of the column to be added to the above Table and populated with appropriate <b>NodeTo</b> IDs.<br>
<u>Note</u>: both <b>NodeFrom</b> and <b>NodeTo</b> columns should not be already defined in the above Table.</li>
</ol>
<b>CreateRoutingNodes()</b> will return <b>1</b> (<i>aka</i> <b>TRUE</b>) on success; an exception will be raised on failure.<br>
<u>Note</u>: you can call <b>CreateRouting_GetLastError()</b> so to precisely identify the cause accounting for failure.
<hr><br>
<a href="https://www.gaia-gis.it/fossil/libspatialite/wiki?name=4.3.0-doc">back</a>
Z cbc2fd8c29c74aca4113ea0abda5e392