Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
| Artifact ID: | c22f4645ee5e82326ecc4ce2102752b686bb9170 |
|---|---|
| Page Name: | VirtualRouting |
| Date: | 2018-03-22 20:49:44 |
| Original User: | sandro |
| Parent: | ca0e52bba6eefb7fdde271847dcf518d219c5efd (diff) |
| Next | 3573a6180c01ce3abf9b9e0a96a7f667949ed3e9 |
Content
Introduction
Previous versions of SpatiaLite traditionally supported a pure SQL routing module that was named VirtualNetwork.Since version 5.0.0 a brand new routing module (more advanced and sophisticated) is now available, that is named VirtualRouting.
The nowadays obsolete VirtualNetwork still continues to be supported by version 5.0.0 so to not cause an abrupt break to already existing applications, but will be presumably suppressed in future versions.
Using VirtualRouting instead of VirtualNetwirk is warmly reccommended for any new development.
Teoretical foundations - an ultra-quick recall
All Routing algorithms (aka Shortest Path algorithms) are based on the mathematics of the Graph theory and more precisely on Weighted Graphs.
A topologically valid Network is a dataset fullfilling the following requirements:
- All items in the dataset are called Links (aks Arcs), and are expected to represent some oriented conection joining two Nodes.
Example: in the above figure Link L3 connects Nodes N2 and N5. - So all Links are always expected to explicitly reference a Start-Node (aka Node-From) and an End-Node (aka Node-To).
- Links are always oriented, and their natural direction is From-To:
- in an unidirectional Network each Link is an oneway connection.
If the connection is available also in the opposite direction a second Link must be explicitly declared.
Example: Link X1 going from Node A to Node B, and Link X2 going from Node B to Node A. - in a bidirectional Network all Links are assumed to establish a connection on both directions.
Definiting an eventual oneway requires some appropriate attribute to be set (see below).
- in an unidirectional Network each Link is an oneway connection.
- The Start- and End-Node could eventually be the same, and in this case we'll have a self-closed Link.
- Network's Links can eventually define a linear Geometry (LINESTRING) going from the Start-Node to the End-Node, but this is an optional feature, not a mandatory requirement.
- What is absolutely mandatory is that each Link must explicitly reference its Nodes.
- Links are always oriented, and their natural direction is From-To:
- A Network supporting Geometries is a Spatial Network; otherwise a Network lacking any geometry is a Logical Network.
- In a Spatial Network all Links must have a corresponding Geometry.
- In a Logical Network all Links are strictly forbidden to have any geometry.
- In a Spatial Network both the StartPoint and EndPoint of each Link's LINESTING are always expected to exactly coincide with the corresponding Nodes.
- All references to the same Node by different Links must exactly coincide.
Example: Node N5 is shared by Links L3, L6, L7, L9 and L10, so all their corresponding LINESTRINGS are expected to have one of the extremity points exactly coincident with all the others.
If such a condition is not satisfied we'll have a topological inconsistency, thus leading to an invalid Network. - Accordingly to the above premise, Nodes are never expected to be explicitly declared just because they can be indirectly recovered from the Links' definitions.
- Links aren't strictly required to be associated with any attribute, but the following attributes are almost universally supported:
- a name identifying the Link.
Examples: the road toponym in a road network, or the river name in an hydrographic network. - one (or even more) appropriate cost value(s).
Example: the time required to traverse the Link (may be discriminating between pedestrians, bycicles, cars, lorries and so on). - a pair of bolean flags (from-to and to-from) intendend to specify if the Link can be traversed on both directions or just in one (oneway).
- a name identifying the Link.
Corollary
Any topologically valid Network (irrespectively if it's of the Spatial or Logical type) is a valid Graph.And a Network allowing to support (directly or indirectly) some appropriate cost value is a valid Weighted Graph, and can consequently support Routing algorithms.