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

[Jay Mahadeokar]

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?


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.

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/ ??


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



-- 
Regards,
-Jay Mahadeokar
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20110512/870faf4b/attachment.html