[GRASS5] Re: Shortest path

[Kjell-Olav Bjerknes]

>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 

The design of the network as Radim here suggested is quite similar to the design I used in the student-work. Having two tables in a RDBMS;
NODE: (nodeid) - (x-pos) - (y-pos)
ARC: (arcid) - (arctype) - (startnode) - (stopnode)

(the arctype was an entry for what kind of road (highway... etc)

As you can see we didnt have any cost attribut, for our simple demo-applet the length of the arc was used as the cost. From this network design different structures can be created... like yours Link_t {}

The network we used was small.... 10-20 arcs!!!! No problems with time there... Using Dijkstra with O(x**) complexity and solving f.ex. TSP with permutation of the selected nodes with O(x!) complexity is a problem in huge networks (like yours). But it should be possible to cut down time by doing som "short-cuts"---> using windows to select possible arcs within an area etc.

On huge network use of a RDBMS like PostgreSQL may help instead of using Grass's flat-filesystem..... but the easiest may be to have all the attributs saved in dig-files! This we can look into after agreeing on network design.

Kjell-Olav

---------------------------------------- 
If you want to unsubscribe from GRASS Development Team mailing list write to:
minordomo at geog.uni-hannover.de with
subject 'unsubscribe grass5'