[pgrouting-dev] Re: Implementation of core Time Dependent Dijkstra function

[Stephen Woodbridge]

On 5/12/2011 5:02 AM, Jay Mahadeokar wrote:
> Hi,
>
> I studied the boost implementation of dijkstra.
> http://www.boost.org/doc/libs/1_46_1/boost/graph/dijkstra_shortest_paths.hpp
>
> At its core, it uses dijkstraVisitorConcept which is extension of
> bfsVisitorConcept
> (http://www.boost.org/doc/libs/1_46_1/boost/graph/breadth_first_search.hpp
> )  so as to perform dijkstra search.
>
> As expected it assumes a static WeightMap which gives the static weights
> of the edges. During bfs search, priority queue is used. When minimum
> vertex is removed, the outbound edges are examined and following
> functions are called:
> 1. grey_target() - is called when target of the edge currently being
> considered was already discovered
>                           It also calls dijkstra_queue_update, if we
> discover better shortest path to target vertex.
> 2. tree_edge() - is called when the target of edge currently considered
> is seen for first time
>
> Both functions call the relax
> function(http://www.boost.org/doc/libs/1_46_1/boost/graph/relax.hpp)
> which uses the static WeightMap to relax the edge being considered.
>
> Now, we need to supply dynamic weights instead of the static weight map.
> So, an alternative implementation of the WeightMap will be required.
>
> *Few thoughts regarding implementation:*
>
> Most important detail which needs to be finalised is the implementation
> of dynamic weight map.
>
> 1. Now, since the weight is function of time, the weight map is now like:
>
> Key: (Edge , Time)  - Since edge and time will form a unique key.
> Value: weight
>
> Is this interpretation reasonable?

This seems reasonable. The only extension to this that would be valuable 
would to add a "class" to the key to allow filtering by traveler class. 
So something like Key: (Class, Edge, Time) where the default class is 
"Any". Hmmm, on second thought, it might be a better abstraction to use 
the Boost Filtered Graph to do this and keep your code simple because it 
is working in a tighter loop.

> 2. When do we populate the weightMap data structure?
>
>     * One approach would be to scan all the (edge,time) values in
>       database available for all edges under consideration and pass this
>       to the core function. This will increase the space complexity
>       which will be greater, as the data precision increases (i.e data
>       is available between finer time intervals).
>     * Another approach would be to query the database each time to get
>       the value for (edge,time) key. This will lead to considerable
>       increase in the time complexity.
>     * A better approach would be to query only few (edge,time) values
>       such that time is in particular range from the start_time. We can
>       also have this as a parameter which user can supply (according to
>       the estimated distance to target, available space / time
>       constraints). This will provide functionality like bounding box in
>       simple pgRouting dijkstra implementation. This can be initialised
>       before calling the core algorithm.  If during search, the entries
>       are not available in the map then we can again query the database
>       and retrieve more entries.

I like your idea of a sliding window. You query for weights between Time 
and Time+Delta, as you approach Time+Delta, you update the window and 
load new data. All entries older than current time can get purged or 
overwritten like a circular buffer.

> 3. Many things related to design will need to be considered like:
>
>     * Do, we create our own timeDependentDijkstraConcept,
>       TimeDependentDijkstraVisitor etc on lines of boost's
>       dijkstra_visitor, or we simply extend the boosts dijkstraVisitor
>       and override the required functions?
>     * The relax() function will also need to be altered. Boost has kept
>       it in separate file(mainly because it is required by other
>       functions also) Should we follow same approach?
>     * It would be nice to keep the function which retrieves the dynamic
>       weights independent of the core algorithm. In static dijkstra, we
>       simply populate whole distanceMap at start. Here, the edgeWeight
>       query might happen during dijkstra search. How do we design the
>       dynamic weight query interface so that above abstraction is achieved?
>     * Other design issues/ ??

These are really good questions. I think that the best place to ask 
these Boost Graph questions is on Boost mailing list.

http://lists.boost.org/mailman/listinfo.cgi/boost-users

Jeremiah Willcock and others are very helpful when people ask questions.

> I have no prior experience with designing such functionality. So, I will
> wait for other opinions. Any reference books that might be helpful here?

I am a C programmer. I understand some of the basic C++ concepts, but 
that is about it, so again, I think the Boost mailing list is a good 
place to start.

-Steve