D 2018-03-23T22:06:48.547
L VirtualRouting
P 3573a6180c01ce3abf9b9e0a96a7f667949ed3e9
U sandro
W 8644
<a href="https://www.gaia-gis.it/fossil/libspatialite/wiki?name=4.3.0-doc">back</a><hr><br>
<h1>Introduction</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>, a <i>geometric length</i> or a <i>travel speed</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>
<h2>Creating a VirtualRouting Table</h2>
<hr><br>
<a href="https://www.gaia-gis.it/fossil/libspatialite/wiki?name=4.3.0-doc">back</a>
Z 15240fe50805b2f2968e52bae1cd0cd6