<div class="gmail_quote">Hi,<br><div><br>I studied the boost implementation of dijkstra. <a href="http://www.boost.org/doc/libs/1_46_1/boost/graph/dijkstra_shortest_paths.hpp" target="_blank">http://www.boost.org/doc/libs/1_46_1/boost/graph/dijkstra_shortest_paths.hpp</a><br>
<br>At its core, it uses dijkstraVisitorConcept which is extension of bfsVisitorConcept (<a href="http://www.boost.org/doc/libs/1_46_1/boost/graph/breadth_first_search.hpp">http://www.boost.org/doc/libs/1_46_1/boost/graph/breadth_first_search.hpp</a> ) so as to perform dijkstra search.<br>
<br>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:<br>
1. grey_target() - is called when target of the edge currently being considered was already discovered <br> It also calls dijkstra_queue_update, if we discover better shortest path to target vertex.<br>
2. tree_edge() - is called when the target of edge currently considered is seen for first time<br><br>Both functions call the relax function(<a href="http://www.boost.org/doc/libs/1_46_1/boost/graph/relax.hpp">http://www.boost.org/doc/libs/1_46_1/boost/graph/relax.hpp</a>) which uses the static WeightMap to relax the edge being considered.<br>
<br>Now, we need to supply dynamic weights instead of the static weight map. So, an alternative implementation of the WeightMap will be required.<br><br><b>Few thoughts regarding implementation:</b><br><br>Most important detail which needs to be finalised is the implementation of dynamic weight map. <br>
<br>1. Now, since the weight is function of time, the weight map is now like:<br><br>Key: (Edge , Time) - Since edge and time will form a unique key.<br>Value: weight<br></div></div><br>Is this interpretation reasonable? <br>
<br><br>2. When do we populate the weightMap data structure?<br><br><ul><li>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).</li>
<li>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.</li><li>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.<br>
</li></ul>3. Many things related to design will need to be considered like:<br><br><ul><li>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?</li>
<li>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?</li><li>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?</li>
<li>Other design issues/ ??<br></li></ul><br>I have no prior experience with designing such functionality. So, I will wait for other opinions. Any reference books that might be helpful here?<br><br><br><br>-- <br>Regards,<br>
-Jay Mahadeokar<br><br>