D 2018-03-23T10:44:26.774
L VirtualRouting
P c22f4645ee5e82326ecc4ce2102752b686bb9170
U sandro
W 6612
<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 be presumably discontinued in future versions.<br>
Using <b>VirtualRouting</b> instead of <b>VirtualNetwirk</b> is warmly reccommended 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>oneway</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 others.<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 recovered by opportunely rearranging the Links' definitions.</li>
<li>A <b>Link</b> may legitimately self-intersect (e.g. forming a loop), as exemplified on 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 where 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, bycicles, cars, lorries and so on).</li>
<li>a pair of <b>boolean flags</b> (<b>from-to</b> and <b>to-from</b>) intendend to specify if the Link can be traversed on both directions or just in one (<b>oneway</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>
And 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>.
All Routing algotithms 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>: both terms <b><i>Routing</i></b> and <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 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>
</ul></li>
<hr><br>
<a href="https://www.gaia-gis.it/fossil/libspatialite/wiki?name=4.3.0-doc">back</a>
Z 196e725c1546203d6edd77967dc8b2dd