[GRASS5] Re: Shortest path

[Roberto Micarelli]

Kjell-Olav Bjerknes wrote:
> 
> >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
> 

Ok for shortcuts, but what if my window is huge too?
Tell me if I'm wrong: when we get to calculating the path we need select groups of arcs sharing
from_node, and link that node with relative to_nodes.
This means O(#from_node). What if I have to perform 100.000 select?
I've tried something with Postgres: my city map on paper gives faster result :(
I suggest topology/geometry into digs, as Radim and you say, and tools for vect to graph transformation:

$ v.net option=vect2graph in=vector out=graph f_catn=1001 t_catn=1002 c_catn=1003 u_catn=1004

f_catn: from node category
t_catn: to node category
c_catn: cost category
u_catn: user category to be output by SP routines (ie. ArcId)


Roberto

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