Boost Graph Library: Dijkstra Shortest Path ignores color_map in named parameters?
I am trying to use the dijkstra_shortest_path algorithm with named parameters. It worked well, until I wanted to pass the color map as an argument. Despite providing my own color_map, the algorithm ends up creating its own two_bit_color_map. I am using the following code: template<class TGraph, class TVisitor> int myDijkstra(TGraph& graph, TVisitor& visitor, int source) { bool earlyExit = false; const int nVertices =boost::num_vertices(graph); std::vector<double> distances(nVertices); std::vector<typename TGraph::vertex_descriptor> predecessors(nVertices); std::vector<boost::default_color_type> colors(nVertices); try { boost::dijkstra_shortest_paths<TSubGraph, TVisitor >( graph, source, boost::predecessor_map( &predecessors[0] ) .distance_map( &distances[0] ) .visitor( visitor ) .color_map( &colors[0] ) ); } catch( EarlyExitByVisitor ) { earlyExit = true; } return earlyExit ? CountBlackVertices(colors) : nVertices; } The code compiles and runs, but the vector of colors is never modified (I can initialize it with different colors, makes no difference). The predecessor and distance maps are fine. Tracing what happens in the source code (boost version 1.43). I notice that the Named Parameter Variant (line 466) gets the distance, weight and index from the named parameter object. It then passes on to the dijkstra_dispatch1 (line 443) that adds the default for the distance map. It passes on to dijkstra_dispatch2 (line 413) that sets even more parameters, but not the color map. Finally it calls dijkstra_shortest_paths variant with default color_map (line 342), which ignores the named parameter object and provides its own color map. (all of the line numbers are in file dijkstra_shortest_paths.hpp). My question is: is this a bug? Can I use named parameters if I want to provide my own color_map? How? Any help is appreciated. -- Alex Hagen-Zanker
On Thu, 1 Jul 2010, Alex Hagen-Zanker wrote:
I am trying to use the dijkstra_shortest_path algorithm with named parameters. It worked well, until I wanted to pass the color map as an argument.
Despite providing my own color_map, the algorithm ends up creating its own two_bit_color_map.
It appears that dijkstra_shortest_paths assumes that it will create the color map, rather than you creating it. Is there a reason you need your own? If you want to know whether vertices have been visited, check their distances against the infinity value that you passed in to the algorithm. -- Jeremiah Willcock
It appears that dijkstra_shortest_paths assumes that it will create the color map, rather than you creating it.
That's what it looks like, but is not what I'd expect from the documentation. Also it means that the named parameters variant behaves differently from the plain variant.
Is there a reason you need your own?
Yes, what I really want is to interupt the algorithm once a criterion is met. For instance all vertices within a given distance are found, or all vertices from a list of targets are found. Then, I want to do further computations (traffic modelling) on the black vertices only. Finally, I would like to be able to resume the interupted algorithm, but that is a spearate matter (and I am starting to think that to solve that neatly, I will need to use breath_first_search() directly, because that allows specifying the priority queue as well).
If you want to know whether vertices have been visited, check their distances against the infinity value that you passed in to the algorithm.
Thanks, it's a good tip, but not exactly what I need. It would tell me which veritces have been visited, but not whether their distance value is tentative (gray vertices) or final (black vertices). My workaround is to not use named parameters. It makes the code less concise, but the results are correct. I replaced the following: boost::dijkstra_shortest_paths<TSubGraph, TVisitor >( graph, source, boost::predecessor_map( &predecessors[0] ) .distance_map( &distances[0] ) .visitor( visitor ) .color_map( &colors[0]) ); With this: boost::dijkstra_shortest_paths<TSubGraph, TVisitor >( graph, // Graph& source // vertex_descriptor s, &predecessors[0], // PredecessorMap &distances[0], // DistanceMap, boost::get(boost::edge_weight, graph), // WeightMap boost::get(boost::vertex_index, graph), // VertexIndexMap std::less<double>(), // CompareFunction boost::closed_plus<double>(), // CombineFunction std::numeric_limits<double>::max(), // DistInf (double) 0.0, // DistZero visitor, // DijkstraVisitor &colors[0] // ColorMap ); -- Alex Hagen-Zanker
On Fri, 2 Jul 2010, Alex Hagen-Zanker wrote:
It appears that dijkstra_shortest_paths assumes that it will create the
color map, rather than you creating it. That's what it looks like, but is not what I'd expect from the documentation. Also it means that the named parameters variant behaves differently from the plain variant.
OK.
Is there a reason you need your own?
Yes, what I really want is to interupt the algorithm once a criterion is met. For instance all vertices within a given distance are found, or all vertices from a list of targets are found. Then, I want to do further computations (traffic modelling) on the black vertices only. Finally, I would like to be able to resume the interupted algorithm, but that is a spearate matter (and I am starting to think that to solve that neatly, I will need to use breath_first_search() directly, because that allows specifying the priority queue as well).
That will be nasty, but will probably work (assuming you get the priority queue and visitor code correct; it is complicated). You might want to also try dijkstra_shortest_paths_no_color_map(), although you would still need to hack out the queue creation code. Another way to do things is to do the traffic modeling within your visitor; returning from the visitor then continues the algorithm.
If you want to know whether vertices have been visited, check their distances against the infinity value that you passed in to the algorithm.
Thanks, it's a good tip, but not exactly what I need. It would tell me which veritces have been visited, but not whether their distance value is tentative (gray vertices) or final (black vertices).
One way to do that is to hook examine_vertex(); anything whose distance is less than or equal to the distance of the vertex being examined is final. Since your description suggest that you are doing that hook anyway to know when to stop, finding black vertices is easy even without a color map.
My workaround is to not use named parameters. It makes the code less concise, but the results are correct.
I replaced the following:
boost::dijkstra_shortest_paths<TSubGraph, TVisitor >( graph, source, boost::predecessor_map( &predecessors[0] ) .distance_map( &distances[0] ) .visitor( visitor ) .color_map( &colors[0]) );
With this:
boost::dijkstra_shortest_paths<TSubGraph, TVisitor >( graph, // Graph& source // vertex_descriptor s, &predecessors[0], // PredecessorMap &distances[0], // DistanceMap, boost::get(boost::edge_weight, graph), // WeightMap boost::get(boost::vertex_index, graph), // VertexIndexMap std::less<double>(), // CompareFunction boost::closed_plus<double>(), // CombineFunction std::numeric_limits<double>::max(), // DistInf (double) 0.0, // DistZero visitor, // DijkstraVisitor &colors[0] // ColorMap );
That is complicated, and adding your own priority queue will make it even worse. If you think the things I suggested above aren't enough, I am willing to adapt the algorithm so that you can have your own color map and/or queue, even in the named parameter versions. -- Jeremiah Willcock
If you think the things I suggested above aren't enough, I am willing to adapt the algorithm so that you can have your own color map and/or queue, even in the named parameter versions.
Your suggestions fully take care of the problem of the color_map, thank you very much. For the problem of resuming, I now employ another solution that is not very elegant; I make a copy of the graph that I am working on and delete from it all the edges between black cells, while inserting edges from the origin to the gray cells with the appropriate distance. I am making a superfluous copy of my graph and create too many overheads and complications. It works now, but I think it would still be very useful if BGL could offer better support for resuming calculations. The function dijkstra_shortest_path_no_init() seems to be ideal for the purpose of resuming an interrupted dijkstra_shortest_path(). I see some issues that would need to be addressed: (1) The priority queue should not be initialized from scratch in dijkstra_shortest_path_no_init(). It could possibly be initialized from the color map or be supplied be the user as a parameter. (2). The source vertice is a parameter to dijkstra_shortest_path_no_init(). The source vertex only seems relevant to the initialization. It is a clue for the initialization of the distance map (d[s] = 0), the color map (c[s] = gray), and the priority queue (Q.assign(1, s)). (3) The same problem goes for the breadth_first_visit(). It is contradictary to supply both the initialized priority queue and the source vertex, because the source vertex is used to initialize the queue. It is not correct to start the breadth_first_visit by inserting the source vertex into the queue map and coloring it gray. (it could be black already). In practice it might not be much of an issue as processing the source vertex one more time is not too costly, but still it could be cause for errors. My proposed solution: 1. Initialize the priority queue already in dijkstra_shortest_path() 2. Don't take the source vertex as a parameter in dijkstra_shortest_path_no_init() 3. Don't take the source vertex as a parameter in breadth_first_search() 4. Add the priority queue as a parameter for dijkstra_shortest_path_no_init() 5. Provide helper functions to initialize a priority queue from: (a) single source vertex (b) color_map + distance_map. I know I see these issues from my particular user-perspective, so please take the "should's", "must's", "issues", and "incorrect's" with a grain of salt. -- Alex Hagen-Zanker -- Alex Hagen-Zanker
The problem of resuming a dijkstra_shortest_path calculation is solved and I thought to share the solution here. It works now without making a copy of the input graph and without permanently modifying the graph as I wrote earlier. The color map is used to make a list of gray vertices (i.e. those vertices in the queue). Before resuming using dijkstra_shortest_path_no_init edges are inserted that connect the source to the gray vertices (i.e. they will be lined up to be put in the queue again). The distance of these edges is the same as the vertex distance of the gray vertices. Subsequently the gray vertices are colored white (i.e. marked as if not in the queue yet). The effect of these actions is that the gray vertices will be inserted into the priority queue by the breadth_first_visit() at their appropriate distance. After the dijkstra_shortest_path_no_init, it is necessary to clean up the introduced edges. There is some overhead to deal with the case that there are already edges between the gray vertices and the origin. Also there is some overhead to make sure that tentative distances and predecessors are not retained, but that is not essential. My code is below, it is not as generic as the BGL though. Jeremiah, Thanks for your help! template<class TGraph> class ResumableDijkstra { public: typedef typename TGraph::vertex_descriptor TVertex; typedef typename TGraph::edge_property_type::value_type TEdge; // EDGE PROPERTY, NOT DESCRIPTOR ResumableDijkstra() : m_Graph(NULL), m_Predecessors(NULL), m_Distances(NULL), m_Colors(NULL), m_GrayVertexDistances(NULL) { m_Predecessors = new std::vector<TVertex>; m_Distances = new std::vector<double>; m_Colors = new std::vector<boost::default_color_type>; m_GrayVertices = new std::vector<TVertex>; m_GrayVertexDistances = new std::vector<double>; } ~ResumableDijkstra() { delete m_Predecessors; delete m_Distances; delete m_Colors; delete m_GrayVertices; delete m_GrayVertexDistances; } void Initialize(TGraph& graph, TVertex origin) { m_Origin = origin; m_Graph = &graph; const int nVertices = boost::num_vertices(graph); m_Distances->assign(nVertices, std::numeric_limits<double>::max()); (*m_Distances)[m_Origin] = 0; m_Colors->assign(nVertices, boost::color_traits<boost::default_color_type>::white()); m_Predecessors->resize(nVertices); for(int i = 0; i < nVertices; i++) { (*m_Predecessors)[i] = (TVertex) i; } } template<class TVis> bool Expand(const TVis& visitor) { bool finished = true; std::vector<TEdge*> restoreEdges; ModifyGraph(restoreEdges); try { boost::dijkstra_shortest_paths_no_init<TGraph, TVis>( *m_Graph, m_Origin, &((*m_Predecessors)[0]), &((*m_Distances)[0]), boost::get(&TEdge::m_Cost, *m_Graph), boost::get(boost::vertex_index, *m_Graph), std::less<double>(), boost::closed_plus<double>(), (double) 0.0, visitor, &((*m_Colors)[0]) ); } catch(AxExit) { finished = false; } RestoreGraph(restoreEdges); if(!finished) { ListGrayVertices(); } return finished; } void ModifyGraph(std::vector<TEdge*>& restoreEdges) { const int n = m_GrayVertices->size(); restoreEdges.assign(n, NULL); for(int i = 0; i < n; ++i) { if( boost::edge(m_Origin, (*m_GrayVertices)[i], *m_Graph).second ) { TEdge* e = new TEdge; *e = (*m_Graph)[boost::edge(m_Origin, (*m_GrayVertices)[i], *m_Graph).first]; boost::remove_edge(m_Origin, (*m_GrayVertices)[i], *m_Graph); restoreEdges[i] = e; } TEdge edge; edge.m_Cost =(*m_GrayVertexDistances)[i]; boost::add_edge(m_Origin, (*m_GrayVertices)[i], edge, *m_Graph); } } void RestoreGraph(std::vector<TEdge*>& restoreEdges) { const int n = (int) m_GrayVertices->size(); assert(n == (int)restoreEdges.size() ); for(int i = 0; i < n; ++i) { boost::remove_edge(m_Origin, (*m_GrayVertices)[i], *m_Graph); if( restoreEdges[i] != NULL) { boost::add_edge(m_Origin, (*m_GrayVertices)[i], *(restoreEdges[i]), *m_Graph); delete restoreEdges[i]; restoreEdges[i] = NULL; } } m_GrayVertices->clear(); m_GrayVertexDistances->clear(); restoreEdges.clear(); } void ListGrayVertices() { m_GrayVertices->clear(); m_GrayVertexDistances->clear(); const int nVertices = m_Colors->size(); for(int j = 0; j < nVertices; j++) { if((*m_Colors)[j] == boost::color_traits<boost::default_color_type>::gray() && j != m_Origin) { m_GrayVertices->push_back(j); m_GrayVertexDistances->push_back((*m_Distances)[j] ); (*m_Distances)[j] = std::numeric_limits<double>::max(); (*m_Predecessors)[j] = j; (*m_Colors)[j] = boost::color_traits<boost::default_color_type>::white(); } } } TGraph* m_Graph; std::vector<TVertex>* m_Predecessors; std::vector<double>* m_Distances; std::vector<boost::default_color_type>* m_Colors; std::vector<TVertex>* m_GrayVertices; std::vector<double>* m_GrayVertexDistances; TVertex m_Origin; };
On Tue, 6 Jul 2010, Alex Hagen-Zanker wrote:
The problem of resuming a dijkstra_shortest_path calculation is solved and I thought to share the solution here.
It works now without making a copy of the input graph and without permanently modifying the graph as I wrote earlier.
The color map is used to make a list of gray vertices (i.e. those vertices in the queue). Before resuming using dijkstra_shortest_path_no_init edges are inserted that connect the source to the gray vertices (i.e. they will be lined up to be put in the queue again). The distance of these edges is the same as the vertex distance of the gray vertices. Subsequently the gray vertices are colored white (i.e. marked as if not in the queue yet).
The effect of these actions is that the gray vertices will be inserted into the priority queue by the breadth_first_visit() at their appropriate distance.
After the dijkstra_shortest_path_no_init, it is necessary to clean up the introduced edges. There is some overhead to deal with the case that there are already edges between the gray vertices and the origin. Also there is some overhead to make sure that tentative distances and predecessors are not retained, but that is not essential.
My code is below, it is not as generic as the BGL though.
That seems like it's a complicated workaround. Did the ideas of just doing your work in a Dijkstra visitor callback (and the algorithm then resuming automatically) or using a separate thread not work for you? Those would seem to be much simpler than what you're doing. Otherwise, we don't have a good way to resume algorithms, although it has been on the TODO list for a long time. I might be able to put something simple together for you that works more directly for resumption. -- Jeremiah Willcock
On Tue, 6 Jul 2010, Alex Hagen-Zanker wrote:
The problem of resuming a dijkstra_shortest_path calculation is solved and I thought to share the solution here. That seems like it's a complicated workaround. Did the ideas of just doing your work in a Dijkstra visitor callback (and the algorithm then resuming automatically) or using a separate thread not work for you? Those would seem to be much simpler than what you're doing. No, it would not work for me. In my case, I have to do a large number (say 2000) of dijkstra shortest path calculations, then I do some
Those would seem to be much simpler than what you're doing. They would also be more correct. One problem with my solution is that it introduces pseudo-edges from the source to the gray vertices. It works fine for me because all my hooks are vertex-based. Edge-based hooks however would need to know about the pseude-edges somehow in order to ignore them. Otherwise, we don't have a good way to resume algorithms, although it has been on the TODO list for a long time. I might be able to put something simple together for you that works more directly for resumption. -- Jeremiah Willcock It seems that the pair of functions: algorithm() and algorithm_no_init() is ideal for resuming algorithms. The only caveat is that algorithm_no_init() should live up to its name and not do any initialization from scratch. It should be OK to initialize from
Jeremiah Willcock wrote: traffic modelling on them, and based on the results I need to go back to the 2000 dijkstra's and resume them. Doing this in a visitor call-back would (to my understanding) require a recursive approach where each visitor, except number 2000, invokes another dijkstra + visitor. It would probably be possible, but more complicated than my current solution. I have considered putting the dijkstra calculations in separate threads, but don't understand enought about threads to know if it is acceptable to create 2000 threads on a desktop computer. Another problem was that I run out of memory and one way of managing it is to store the state of the dijkstra algorithm to hard disk after a calculation and load the state from disk again upon resumption. This requires me to explicitly know the state, and to be able to clear it and overwrite it. This would not be possible in the thread solution, nor in the recursion solution. parameters that duplicate information, e.g. initialize the priority queue from the color map. It could entail the following: Initialize Q from color map in dijkstra_shortest_paths_no_init() by inserting the following after declaring Q typedef typename property_traits<ColorMap>::value_type ColorValue; typedef color_traits<ColorValue> Color; typename graph_traits<VertexListGraph>::vertex_iterator vi, vi_end; for (tie(vi, vi_end) = vertices(g); ui != vi_end; ++vi) if(get(color, *vi) == Color::gray()) Q.push(*vi); Call breadth_first_visit_no_init() instead of breadth_first_visit() from dijkstra_shortest_paths_no_init(). Create breadth_first_visit_no_init() as a copy of breadth_first_visit(), but remove the following lines. put(color, s, Color::gray()); vis.discover_vertex(s, g); Q.push(s); Also it is no longer necessary to pass the source vertex argument. If something along these lines could make it into the BGL that would be great. I would like to make my work open source some time and it would be great if it works seamlessly with boost at that point. For now, I can tolerate overly complicated workarounds. -- Alex Hagen-Zanker
participants (2)
-
Alex Hagen-Zanker -
Jeremiah Willcock