Re: [Rails-devel] Tile Database API & route calculation

[John A. T. <ja...@ja...>]

Erik Vos wrote:

>I was under the impression, that your pseudocode would work with
>the track/junction objects themselves, without need for separate 
>structures (a.k.a. different connectivity graphs).
>Which would mean, that for different purposes you would have 
>different algorithms working with the same data structure
>(which indeed is how I would do it). 
>Did I misunderstand that?
>  
>
The pseudocode was just to illustrate the idea of the algorithm, not 
tied to any particular data structure.  The references to the 
connectivity graph is in connectionJunctionExit(junction,exit) which 
iterates over all the junction exits reachable from a particular 
junction exit.  It could do that by traversing pointers between objects 
or by looking at a bitvector, or indeed many other implementations.

Looking at Iain's code, there is a different way of solving the problem 
-- rather than splitting the junctions into a subgraph of nodes so you 
can track which connections to other junctions/edges share the same 
track, you can simply keep a list of which edges in the graph are 
mutually exclusive.  I will look at it some over the weekend to see if 
that will work better for our purposes.  It has the benefit of removing 
the subdivision of junctions, but adding another datastructure that has 
to be looked up during each route aggregation step.

-- 
John A. Tamplin					ja...@ja...
770/436-5387 HOME				4116 Manson Ave
                		 		Smyrna, GA  30082-3723