Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
| Artifact ID: | 661cc94986b9e03b4c542fcae483050d37517292 |
|---|---|
| Page Name: | VirtualRouting |
| Date: | 2018-03-23 22:06:48 |
| Original User: | sandro |
| Parent: | 3573a6180c01ce3abf9b9e0a96a7f667949ed3e9 (diff) |
| Next | eb4769d3b31190e5253b0df56d0661ff076d744a |
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 available, that is called VirtualRouting.
The now obsolete VirtualNetwork is still supported by version 5.0.0 so as to not cause an abrupt break to already existing applications, but will presumably be discontinued in future versions.
Using VirtualRouting instead of VirtualNetwirk is warmly recommended for any new development.
Theoretical foundations - an ultra-quick recall
All Routing algorithms (aka Shortest Path algorithms) are based on the mathematics of the Graph theory or to be more precise: on Weighted Graphs.
A topologically valid Network is a dataset that fulfills the following requirements:
- All items in the dataset are called Links (aka Arcs), and are expected to represent some oriented connection 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 one-way connection.
If the connection is available in the opposite direction a second Link must be explicitly declared.
Example: Link X1 goes from Node A to Node B, and Link X2 goes from Node B to Node A. - in a bidirectional Network all Links are assumed to establish a connection in both directions.
Definiting an one-way connection requires an appropriate attribute to be set (see below).
- in an unidirectional Network each Link is an one-way 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 LINESTRING are always expected to exactly coincide with the corresponding Nodes.
- In a Spatial Network all references to the same Node by different Links must be an exact match.
Example: Node N5 is shared by Links L3, L6, L7, L9 and L10, so all their corresponding LINESTRINGS are expected to have the corresponding extremity (Start- or End-, depending on the orientation) points that must exactly match the other.
A topological inconsistency exists if any of these conditions are not satisfied, which leads to an invalid Network. - In a Spatial Network two
- Accordingly to the above premises, Nodes are never expected to be explicitly declared in a separate Table.
Just a single Table declaring all Links is required in order to fully define a topologically valid Network.
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.
If any mismatch is detected this surely means that the Network is invalid. - A Link may legitimately self-intersect itself (e.g. forming a loop), as shown in the above figure by Link L15 (orange spot).
- Two Links may legitimately intersect where no Node exists, as exemplified on the above figure by Links L4 and L7 (green spot).
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). - Links aren't strictly required to be associated with any specific 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 distinguished between pedestrians, bicycles, cars, lorries and so on). - a pair of boolean flags (from-to and to-from) are intendend to specify if the Link can be traversed on both directions or just in one (one-way).
- a name identifying the Link.
Logical conclusions
Any topologically valid Network (irrespective of whether it is a Spatial or Logical type) is a valid Graph.A Network allowing the support (direct or indirect) of some appropriate cost value is a valid Weighted Graph, and can consequently support Routing algorithms.
All Routing algorithms are intended to identify the Shortest Path solution connecting two Nodes in a weighted graph (aka Network).
Note: the term Shortest Path can be easily misunderstood.
Due to historical reasons the most common application field for Routing algorithms is related to Road Networks, but also many other kinds of Networks exist:
- Hydrographic Networks.
- Gas / Water / Oil Networks.
- Electrical Networks.
- Telecomunication Networks.
- Social or Economical Networks representing relationships between individuals or companies.
- Epidemiological Networks representing the propagation of infective diseases between individuals or groups.
In all the above cases we certainly have valid Networks supporting Routing algorithns, but not all of them can imply something like a spatial distance, a geometric length or a travel speed.
In the most general acception costs can be represented by any reasonable physical quantity.
So a more generalized definition is assuming that Routing algorithms are intended to identify lesser cost solutions on a weighted graph.
The exact interpretation of the involved costs (aka weights) strictly depends on the very specific nature of each Network.
The Dijkstra's algorithm
This well known algorithm isn't necessarily the fastest one, but it always ensures full correctness:- Any Node-to-Node connection identified by Dijkstra's is certainly ensured to be optimal.
In other words, no connetction presenting a lower cost can conceptually exist. - When Dijsjtra's fails to identify a solution this surely means that no solution is possible.
The A* algorithm
Many alternative Routing algorithms have been invented during the years.All them are based on heuristic assumptions and are intended to be faster than Dijkstra's, but none of them can ensure full correctness as Dijkstra's does.
The A* algorithm applies a mild heuristic optimization, and can be a realistic alternative to Dijkstra's in many cases.