[GRASS5] Re: shortest path

[Roberto Micarelli]

Angus Carr wrote:
> 
> If we are going to go the route of saving a graph for a vector file (I suggest
> the command n.build...) then perhaps we should follow the same convention as
> the Graph Template Library (http://www.fmi.uni-passau.de/Graphlet/GTL/ ) and
> use an existing on-disk format. They use the GML - Graph Modelling Language.
> There is a parser for GML available at
> http://www.infosun.fmi.uni-passau.de/Graphlet/GML/index.html, written in C.
> 
> I'm not suggesting that we go to a C++ program and just use the GTL, but we
> could use a common format, with an existing parser library.
> 
> Angus.

I didn't know about GTL, thank you. It is a nice interface, supporting a wide range
of algorithms. On this side my work is still poor.
In any case there are two choises I made when started the design: C language
(eventually adding a C++ wrapper in a second phase), and a binary file format
(to reduce in/out band requirements and higher overall execution speed).
To achieve this I use binary trees while loading/updating the graph, but before
to start calculation I have to 'flatten' it and translate all relations between
nodes into memory (or file) offsets.
So far only shortest path algorithm has been implemented. The first performance
tests are giving excellent results: it took me 1 second to find least cost path in
a 100.000 nodes / 360.000 edges graph. This must be added 3 sec to load the graph
from disk if not yet cached (speaking in PIII/IDE terms). If I had the same in ASCII
and I had to reconstruct the internal structure while loading I would have spent
minutes.
At this point I'm investigating my approach, comparing it to GTL. My work is enought
young to get eventually stopped and reconverted. I need to try GTL performances on
large datastores, as the GIS graphs usually are.

For sure, we can at least export/import GML graphs.

Regards.

P.S.: n.build (n.*) sounds good. Radim's point of view appreciated

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