[GRASS5] Re: shortest path

[Radim Blazek]

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
> ------------------------------
>           total
>
> Maybe 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 at geog.uni-hannover.de with
subject 'unsubscribe grass5'