roberto micarelli wrote:
I thing that we should discuss format for network first. Or is it
clear for you? Points + lines in dig file?No, so far it is not clear to me. I think that we need a different format for storing
the network. I'm wondering how could it be:Link_t
{
Nodeid, #links, (To0, To1, ..., ToN),
(Cost0, Cost1, ..., CostN),
(ArcId0, ArcId1, ..., ArcIdN)
}This is a way to represent a directed graph in a file, that will
then be a stream of Link_t records.The 'to' fields are references to further nodes.
The 'cost' fields are the cost to travel from this node to the
relative 'to' node.The algorithm must output the path list as:
Step Arc Distance FromNode ToNode
-------------------------------------
0 Id cost Id Id
1 Id cost Id Id
...
N Id cost Id Id
------------------------------
totalMaybe we could withdraw ArcId from the graph, one should
then be able to retrieve it from the FromNode/ToNode couple
in order (for example) to plot the path.What I'm designing is a -graph- read only file, that one must generate from
its topology. The same network can be generated in different flavours, and
optimized for different navigation parameters.
Dijkstra has O('#node'**) complexity, and I've seen around navigable layers of more than
300.000 arcs. What performance can we expect if we use a RDBMS to perform (300.000)**
selects ?
Thus the 'to' fields must be direct seek values in the file that are transformed
in memory-addresses when the graph comes to fit into memory for calculations.
I would like to have this program running on 'low cost' hw.The geometry portion of the network can still reside in dig files ...
Make me know what do you think about this idea.
I think that network may be saved and maitained in dig file (ver. 5.0 with multicategory support,
available in few weeks) in this way: Nodes written as points, arc as lines. Each node has
one category for unique nodeid. Each arc has one category for arcid, one category for cost and two
categories for from_node and to_node. From_node and to_node are not maintained by hand.
On this dig could be run module like
v.net option=build map=net from_catn=1001 to_catn=1002
which would fill from_node and to_node (saved in categories with numbers 1001, 1002)
by appropriate nodeids.
Net saved in dig file may be edit by standard GRASS modules like v.digit and read to structure
Link_t {} which you suggested with minimum HW requirements.
Radim
----------------------------------------
If you want to unsubscribe from GRASS Development Team mailing list write to:
minordomo@geog.uni-hannover.de with
subject 'unsubscribe grass5'