Modifying Dijkstra's Shortest Paths algorithm in Boost::Graph to not relax certain edges
Hi, I am using Boost::Graph and DSP which comes with it to work out shortest paths around my graph. The problem is there is a certain exceptional situation when certain vertices can become unreachable along certain paths. I.e. although there is a valid distance value for edge B ? C, the same edge can become invalid if B is reached along a specific path. If this happens, I want DSP to reject that edge. I attempted to create a list of visitors. EdgeRelaxed records how vertices in the DSP queue were reached. EdgeExamined checks for the exceptional situation and if it's detected, it temporarily changes the distance value of the edge in question to infinity. EdgeNotRelaxed then restores the distance value to it's original. Unfortunately this approach doesn't seem to work, I think the reason for this is because dijkstras_shortest_paths() function gets information about distances from the weight_map which is passed to it. Is there any way I can modify the values inside the weight_map in between DSP stages to invalidate certain paths which will result in them being rejected for relaxation? Or perhaps there is an easier and tidier way of achieving the same result? Thanks in advance, Arty
Is there any way I can modify the values inside the weight_map in between DSP stages to invalidate certain paths which will result in them being rejected for relaxation? Or perhaps there is an easier and tidier way of achieving the same result?
You probably don't want to modify the edge weights - that might have some weird side effects. You might want to look at providing new distance_compare and distance_combine functions for the Dijkstra algorithm. Andrew Sutton andrew.n.sutton@gmail.com
Hi Andrew, Thanks for your reply. I am still learning the library so I don't know the source very well. How would one provide new functions to DSP? Is there some sort of internal mechanism to allow for this? Arty Andrew Sutton wrote:
Is there any way I can modify the values inside the weight_map in between DSP stages to invalidate certain paths which will result in them being rejected for relaxation? Or perhaps there is an easier and tidier way of achieving the same result?
You probably don't want to modify the edge weights - that might have some weird side effects. You might want to look at providing new distance_compare and distance_combine functions for the Dijkstra algorithm.
Andrew Sutton andrew.n.sutton@gmail.com <mailto:andrew.n.sutton@gmail.com>
------------------------------------------------------------------------
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Thanks for your reply. I am still learning the library so I don't know the source very well. How would one provide new functions to DSP? Is there some sort of internal mechanism to allow for this?
Sorry... I was in a hurry when I wrote last. The DSP algorithm takes function objects as parameters that can be used to change the default behavior of distance comparison and combination. It's mentioned here, but I doubt that there are any good examples. http://www.boost.org/doc/libs/1_38_0/libs/graph/doc/dijkstra_shortest_paths.... For example, you might call it as: dijkstra_shortest_paths(g, v, weight_map(weights). distance_map(results). distance_compare(my_compare)); Where my_compare is a BinaryPredicate (like std::less), taking the value_type of the weights. You might also look at ways using or modifying the color_map, which is also an optional parameter. Hope that's more clear. Andrew Sutton andrew.n.sutton@gmail.com
Artyom wrote:
Hi,
I am using Boost::Graph and DSP which comes with it to work out shortest paths around my graph. The problem is there is a certain exceptional situation when certain vertices can become unreachable along certain paths. I.e. although there is a valid distance value for edge B → C, the same edge can become invalid if B is reached along a specific path. If this happens, I want DSP to reject that edge. I attempted to create a list of visitors. EdgeRelaxed records how vertices in the DSP queue were reached. EdgeExamined checks for the exceptional situation and if it's detected, it temporarily changes the distance value of the edge in question to infinity. EdgeNotRelaxed then restores the distance value to it's original.
Unfortunately this approach doesn't seem to work, I think the reason for this is because dijkstras_shortest_paths() function gets information about distances from the weight_map which is passed to it.
Is there any way I can modify the values inside the weight_map in between DSP stages to invalidate certain paths which will result in them being rejected for relaxation? Or perhaps there is an easier and tidier way of achieving the same result?
Thanks in advance, Arty
Arty, I think the following trick may help. You can create a "dynamic bundled_property_map" such that given a map "pm" and an edge descriptor "e" the construction "pm[e]" is actually a call of member function from the Bundle class. See attached example. Good luck, Dmitry
participants (2)
-
Andrew Sutton -
Artyom -
Artyom Arabadji
-
Dmitry Bufistov