SpatiaLite 2.3.0          VirtualNetwork


back
The VirtualNetwork module enables SpatiaLite to support routing directly in SQL.
Routing is strongly based on the graph theory, and VirtualNetwork implements the well-known Dijkstra's Shortest Path algorithm.
If all this sounds quite unfamiliar to you, you can get some useful information at:
http://en.wikipedia.org/wiki/Graph_(mathematics)
http://en.wikipedia.org/wiki/Dijkstra's_algorithm


Building a Network

The first step requires building a Network, i.e. a peculiar data set representing a graph.
In order to accomplish this step you have to start from some raw data set [i.e. DB table] satisfying the following prerequisites: You can download the test-network-2.3.sqlite sample DB required by following examples.
This actually represents the Italy's national road network [based on the Digital Chart of the World data].

The raw data are contained into the table named Roads [some 4,000 rows aka arcs].
The column layout for this Roads tables is:
column namedata typemeaning

PK_UIDINTEGERthe primary key identifying each arc
F_NODEINTEGERthe code identifying the arc's start node
T_NODEINTEGERthe code identifying the arc's end node
TypeTEXTthe road category [i.e. highway, primary ...]
SpeedINTEGERthe estimated mean speed [Km/h]
TravelTimeDOUBLEthe estimated arc traversal time [seconds]
this one represents the arc's cost
GeometryLINESTRINGthe arc's geometry
Let us try this SQL query in order to better understand what is the real meaning of the term topological consistency:
SELECT PK_UID, F_NODE, T_NODE,
    X(StartPoint(Geometry)), Y(StartPoint(Geometry)), X(EndPoint(Geometry)), Y(EndPoint(Geometry))
FROM Roads
WHERE F_NODE = 500 OR T_NODE = 500;

PK_UIDF_NODET_NODE X(StartPoint(Geometry))Y(StartPoint(Geometry))X(EndPoint(Geometry))Y(EndPoint(Geometry))

590500493451431.3329135035043.807065460761.5959515035818.198275
591406500450462.2689795051471.872834451431.3329135035043.807065
686569500431913.2354655026366.215484451431.3329135035043.807065
719500591451431.3329135035043.807065453777.6987175019713.609391

The node identified by value 500 is referred by four different arcs, both as a start or end node.
Anyway, the spatial coordinates for this node remains always identical, thus satisfying any topological consistency requirement.

network-1
We can now build a Network aka graph quite easily using the ad hoc tool supported by spatialite-gui.
After performing this task we can notice that: Using your own data, it's very alike that your supposed-to-be Network will fail to satisfy all the constraints required, for one reason or another.
In such an occurrence the user friendly spatialite-gui can offer you a very little help, because it simply reports some error and refuses to build the Network corresponding to your own data.
Don't fall in panic; you can now use the spatialite_network CLI tool; this latter implements a strong diagnostic tool, and will help you in identifying and correcting any error.

spatialite_network -d test_network-2.3.sqlite -T Roads \
    -f F_NODE -t T_NODE -c TravelTime -g Geometry

SQLite version: 3.6.12
SpatiaLite version: 2.3.0
Step I - checking for table and columns existence

spatialite-network-validator

==================================================================
   SpatiaLite db: test_network-2.3.sqlite
validating table: Roads

columns layout
==================================================================
FromNode: F_NODE
  ToNode: T_NODE
    Cost: TravelTime
Geometry: Geometry

assuming arcs to to be BIDIRECTIONAL

simple validation required
[NETWORK-DATA table creation is disabled]
==================================================================

Step  II - checking value types consistency
Step III - checking topological consistency
Step  IV - final evaluation

Statistics
==================================================================
        # Arcs : 8270
        # Nodes: 3186
        Node max  incoming arcs: 7
        Node max outcoming arcs: 7
        # Nodes   cardinality=1: 490 [terminal nodes]
        # Nodes   cardinality=2: 828 [meaningless, pass-through]
==================================================================


OK: network passed validation
        you can apply this configuration to build a valid VirtualNetwork
OK: validation passed



Using Routing

All right, now we have built a valid Network, and we are finally ready to discover Routing.
Just to recapitulate:
SELECT *
FROM Roads_net
WHERE NodeFrom = 1 AND NodeTo = 512;

ArcRowidNodeFromNodeToCostGeometry

NULL151222021.995764BLOB sz=3376 GEOMETRY
1143366.262555NULL
114161418.458904NULL
151620868.499405NULL
212025623.616463NULL
222524186.070230NULL
3524381825.020686NULL
493853705.591126NULL
6753662053.355052NULL
121661141490.480401NULL
1831141691201.464297NULL
225169207907.687669NULL
2712072401552.639653NULL
27024024285.475589NULL
310242281394.516028NULL
3632813201692.810841NULL
6083205123650.046865NULL


back