back

The

Routing is strongly based on the

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

In order to accomplish this step you have to start from some

- each entity identifies a single
**arc**, so has to be represented as a**Linestring**geometry.

Then no entity is allowed to have a*NULL*geometry. - each
**arc**has to explicitly identify [using some kind of*coding*] its**start node**and**end node**.

Arcs may be**unidirectional**or**bidirectional**as well; we'll see better this later ...

For now we'll assume they are anyway__unidirectional__, i.e. each arc can be traversed only following the*start-end*direction. - a strong
**topological consistency**is absolutely required.

i.e. any**arc**-point identifying the same**node**has to use exactly the same identical**(x,y)**coordinates.

And each arc has to be drawn following its*start-end*direction. - each arc requires to be associated with some meaningful
**cost**; this may be represented by an explicit value, e.g. indicating the time required to traverse the arc.

As a*default*, the*geometry length*may be used as a*cost*value related to each arc.

This actually represents the

The

The column layout for this Roads tables is:

column name | data type | meaning |
---|---|---|

PK_UID | INTEGER | the primary key identifying each arc |

F_NODE | INTEGER | the code identifying the arc's start node |

T_NODE | INTEGER | the code identifying the arc's end node |

Type | TEXT | the road category [i.e. highway, primary ...] |

Speed | INTEGER | the estimated mean speed [Km/h] |

TravelTime | DOUBLE | the estimated arc traversal time [seconds]this one represents the arc's cost |

Geometry | LINESTRING | the arc's geometry |

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_UID | F_NODE | T_NODE | X(StartPoint(Geometry)) | Y(StartPoint(Geometry)) | X(EndPoint(Geometry)) | Y(EndPoint(Geometry)) |
---|---|---|---|---|---|---|

590 | 500 | 493 | 451431.332913 | 5035043.807065 | 460761.595951 | 5035818.198275 |

591 | 406 | 500 | 450462.268979 | 5051471.872834 | 451431.332913 | 5035043.807065 |

686 | 569 | 500 | 431913.235465 | 5026366.215484 | 451431.332913 | 5035043.807065 |

719 | 500 | 591 | 451431.332913 | 5035043.807065 | 453777.698717 | 5019713.609391 |

Anyway, the spatial coordinates for this node remains always identical, thus satisfying any topological consistency requirement.

We can now build a

After performing this task we can notice that:

- now the database contains a new table, named
**Roads_net_data**

and this table seems to contain quite meaningless binary data [*aka*BLOBs]. - there is also a VirtualTable named
**Roads_net**; and this one is an apparently empty table. - we'll see later how to use them; be a little more patient.

In such an occurrence the

Don't fall in panic; you can now use the

-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

Just to recapitulate:

- we initially started form some
*raw data*contained into a table name**Roads** - then we've built a corresponding Network: this actually consists in:
- a physical
**Roads_net_data**table containing*binary data* - a VirtualTable named
**Roads_net**which is apparently empty

- a physical
- now we can go a little more in-depth, and discover that:
- the
**Roads_net_data**actually contains a pre-build static [*frozen*]**graph**corresponding to our raw data.

if the raw data change someway, then the static graph needs to be updated, but rebuilding again the network is a simple and quick task. - the
**Roads_net**VirtualTable simply implements an*ad hoc*interface supporting Routing queries.

- the

SELECT *
FROM Roads_net WHERE NodeFrom = 1 AND NodeTo = 512; | ||||||

ArcRowid | NodeFrom | NodeTo | Cost | Geometry | ||
---|---|---|---|---|---|---|

NULL | 1 | 512 | 22021.995764 | BLOB sz=3376 GEOMETRY | ||

1 | 1 | 4 | 3366.262555 | NULL | ||

11 | 4 | 16 | 1418.458904 | NULL | ||

15 | 16 | 20 | 868.499405 | NULL | ||

21 | 20 | 25 | 623.616463 | NULL | ||

22 | 25 | 24 | 186.070230 | NULL | ||

35 | 24 | 38 | 1825.020686 | NULL | ||

49 | 38 | 53 | 705.591126 | NULL | ||

67 | 53 | 66 | 2053.355052 | NULL | ||

121 | 66 | 114 | 1490.480401 | NULL | ||

183 | 114 | 169 | 1201.464297 | NULL | ||

225 | 169 | 207 | 907.687669 | NULL | ||

271 | 207 | 240 | 1552.639653 | NULL | ||

270 | 240 | 242 | 85.475589 | NULL | ||

310 | 242 | 281 | 394.516028 | NULL | ||

363 | 281 | 320 | 1692.810841 | NULL | ||

608 | 320 | 512 | 3650.046865 | NULL | ||

- the only meaningful query you can perform on a
**VirtualNetwork**table has the canonical form:

**SELECT ... FROM***prefix***_net WHERE NodeFrom =***node1_id***AND NodeTo =***node2_id* - this will return a
*result set*representing the**routing solution**[i.e. the*shortest path*] connecting the required**start**and**end nodes**.

if such a connection doesn't exists, then an__empty result set__will be returned. - the
**first row**in the result set is a special one, and represents the**whole travel solution**, this including a corresponding Geometry. - then any following row identifies a single
**arc**used by the travel solution, following the travel sequence. - you can easily distinguish between them because:
- the
**whole solution**special row has*ArcRowid = NULL*and*Geometry <> NULL* - any plain
**arc**row has*ArcRowid <> NULL*and*Geometry = NULL*

- the

back