D 2018-03-22T20:49:44.740
L VirtualRouting
P ca0e52bba6eefb7fdde271847dcf518d219c5efd
U sandro
W 5216
<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 now available, that is named <b>VirtualRouting</b>.<br>
The nowadays obsolete <b>VirtualNetwork</b> still continues to be supported by version <b>5.0.0</b> so to not cause an abrupt break to already existing applications, but will be presumably suppressed in future versions.<br>
Using <b>VirtualRouting</b> instead of <b>VirtualNetwirk</b> is warmly reccommended for any new development.
<h2>Teoretical 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> and more precisely 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 fullfilling the following requirements:
<ul>
<li>All items in the dataset are called <b>Links</b> (<i>aks</i> <b>Arcs</b>), and are expected to represent some oriented conection 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 also in the opposite direction a second Link must be explicitly declared.<br>
<u>Example</u>: Link <b>X1</b> going from Node <b>A</b> to Node <b>B</b>, and Link <b>X2</b> going 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 on both directions.<br>
Definiting an eventual <b>oneway</b> requires some 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>LINESTING</b> are always expected to exactly coincide with the corresponding <b>Nodes</b>.</li>
</ul></li>
<li>All references to the same <b>Node</b> by different Links <b>must</b> exactly coincide.<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 one of the extremity points exactly coincident with all the others.<br>
If such a condition is not satisfied we'll have a <b>topological inconsistency</b>, thus leading to an <b>invalid</b> Network.</li>
<li>Accordingly to the above premise, <b>Nodes</b> are never expected to be explicitly declared just because they can be indirectly recovered from the Links' definitions.</li>
<li><b>Links</b> aren't strictly required to be associated with any 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 discriminating between pedestrians, bycicles, cars, lorries and so on).</li>
<li>a pair of <b>bolean 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>Corollary</h4>
Any topologically valid <b>Network</b> (irrespectively if it's of the <b>Spatial</b> or <b>Logical</b> type) is a valid <b>Graph</b>.<br>
And a Network allowing to support (directly or indirectly) some appropriate <b>cost value</b> is a valid <b>Weighted Graph</b>, and can consequently support <b>Routing algorithms</b>.
<hr><br>
<a href="https://www.gaia-gis.it/fossil/libspatialite/wiki?name=4.3.0-doc">back</a>
Z 94b721bc12557199ca1e32b6559b45f2