[Openstreetmap] maps as graphs

[Matt Amos]

On Monday 21 March 2005 17:26, Hugh Barnard wrote:
> Apologies if this is a bit aslant to the current topics...Jo (I
> think, I read the digest) touched
> on something that will interest me as a 'user':- routes (of all
> kinds) which can be represented
> as graphs...they tend immediately to be directed graphs in cities
> because of one-way systems etc...also, if one edge is (say)
> pedestrian, then that complete route is pedestrian-only etc. etc.

indeed. graphability gives us a number of very useful abilities 
including shortest path routing with Dijkstra's algorithm. 

> So, a certain amount of the ontology discussion is also related to
> a graphability discussion,
> don't know how much...

the graphing stuff is all covered by the node-element-area 
formulation. restricting the intersection of lines to occur only at 
nodes means that all layout, colouring, subdivision, etc... problems 
become graph-theoretic and they've all been solved years ago.

it doesnt solve the ontology issue, which then becomes: "what do we 
call this element? what are its properties?"

since that is language, country and outlook dependent its a Difficult 
Problem and other people can solve it ;-)

> Just to declare interest, I've been working on and off on a
> to-be-GPLed rideshare thing which, at present is postcode based,
> but it would produce more matches if it became more fine grained in
> a 'routey' (ha..) sort of way, another reason for the post.

yep. there are several algorithms for counting the "common path" of 
two walks on a graph. this is the same as the utility of a ride 
share, i guess!

cya,

matt
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 190 bytes
Desc: not available
URL: <http://lists.openstreetmap.org/pipermail/talk/attachments/20050324/ca2c10d3/attachment.pgp>