[GRASS5] Re: Shortest path

GRASS GRASS developer
1

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

2

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 :frowning:
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@geog.uni-hannover.de with
subject 'unsubscribe grass5'

3

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 :frowning:
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

OK.

Radim

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

4

At 13:40 05.10.2000 +0200, you wrote:

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 looked through my Java-code, and the Dijkstra algorithm loaded all the nodes in the network in an array and the cost from the startnode to each other node was recorded as the algorithm worked through the network. Since we only had a small network this worked fine. I dont know how fast Grass could work on arrays containing 100 000's nodes, maybe these arrays must be saved in RDBMS? Beside of this cost array, we also used two other arrays. One keeping the shortest path for a node to the start node. The last array marked the nodes "visited" as the alogrithm worked its way to the goal! The algortihm stoped when the stop node was marked visited!

Our arrays were build every time the application was run. This doesnt have to be the case. The arrays/tables in RDBMS needs only to be created when the network has been updated.! Constructing a command that does this after updating the network should be an easy task and would save some time!

Kjell-Olav

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

5

Kjell-Olav Bjerknes wrote:

At 13:40 05.10.2000 +0200, you wrote:
>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 looked through my Java-code, and the Dijkstra algorithm loaded all the
nodes in the network in an array and the cost from the startnode to each
other node was recorded as the algorithm worked through the network. Since
we only had a small network this worked fine. I dont know how fast Grass
could work on arrays containing 100 000's nodes, maybe these arrays must be
saved in RDBMS? Beside of this cost array, we also used two other arrays.
One keeping the shortest path for a node to the start node. The last array
marked the nodes "visited" as the alogrithm worked its way to the goal! The
algortihm stoped when the stop node was marked visited!

Our arrays were build every time the application was run. This doesnt have
to be the case. The arrays/tables in RDBMS needs only to be created when
the network has been updated.! Constructing a command that does this after
updating the network should be an easy task and would save some time!

Kjell-Olav

Ok. Now I'm writing my version of the graph library, I need it apart from Grass
but hope it will be useful in there too. Don't apologize me for not to listen to
your suggestions, I'm doing that. But I also must start to stay into planned time.
I'm using an 'offset method' to address nodes both into the memory array and/or
in the database file. So when I block-read the graph in memory I have ready to
use memory offsets.
Dijkstra has to exhaust nodes before giving up with the best path. If you stop
it the first time you reach the target, nobody can tell you that it's really the
best way. I'm thinking to some smart short-cuts expecially oriented to vehicle
navigation ...
Didn't you use a min-heap for costs?
I'm going to send to people interested in my work a copy, as soon as it is in
a suitable aspect. It is C code developed/compiled under Linux. I'll
need to test it for porting on other OS. When it will be enought stable I'll wrap
it to Grass and propose for adoption to this community.

Is your Java application available for reading?

Roberto

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

6

At 15:13 06.10.2000 +0200, you wrote:

Is your Java application available for reading?

The java applet was programmed with norwegian text! ......

The link to the project is:

http://nlhgis.nlh.no/~geodbstud/stig/prosjekt/

and the source is:

http://nlhgis.nlh.no/~geodbstud/stig/javadoc/kildekode.html

but it is all in norwegian...and the applet is not working because the network is deleted from the RDBMS......... sorry...... I planned to set it up on my web-server, for demonstration... but I rather use my spare time on Grass - network analyzies if we could make this work!

Let me know if you want me to do a fast translation !

Kjell-Olav

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