[GRASS5] Re: shortest path

[Roberto Micarelli]

Radim Blazek wrote:
> 
> roberto micarelli wrote:
> >
> > Angus Carr wrote:
> > >
> > > I, too, have thought that this would be a useful program. The network has
> > > topology, so you should be able to do something with it. A feature request
> > > for you- please allow the reporting of the nodes/segments taken. I want to
> > > do a traffic analysis, and I need a log of all vehicles that pass through
> > > any given node, and along any given vector, assuming they took the shortest
> > > path from point to point. Given the list of nodes and edges between any two
> > > points (Dijkstra), I can then do the traffic analysis.
> > >
> > > One other possibility for you is to develop a network API and library for
> > > GRASS. That way, others can easily build on your work. It makes the
> > > development of your code quite modular, too, which is always a good thing.
> > >
> > > Thanks for the idea, and I will be happy to help with testing when it comes
> > > time. If you want other help, I can provide some, as needed.
> > >
> > > Angus Carr.
> >
> > Thanks to you for the help. I agree with your suggestions. We can switch to the
> > developer list or private mail for details.
> >
> > Ciao.
> 
> I would like listen to the following discussion about network also.
> I thing that we should discuss format for network first. Or is it
> clear for you? Points + lines in dig file?
> 
> Radim

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.

Ciao.

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