Need example of substitution of priority queue
I wish to run a breadth_first_search() on a graph where I am defining the priority queue (I have a hand-rolled sort order). Is there any reason I cannot use std::priority_queue<> to do this? Does anyone have an example, or know of one in the docs? Thanks Eric
On Thu, 20 May 2010, Eric Fowler wrote:
I wish to run a breadth_first_search() on a graph where I am defining the priority queue (I have a hand-rolled sort order). Is there any reason I cannot use std::priority_queue<> to do this? Does anyone have an example, or know of one in the docs?
One easy place to find that code is in this function in
boost/graph/dijkstra_shortest_paths.hpp:
// Call breadth first search
template
I don't see how this substitutes a hand-rolled queue.
And I don't see why this:
boost::bfs_visitor
On Thu, 20 May 2010, Eric Fowler wrote:
I wish to run a breadth_first_search() on a graph where I am defining the priority queue (I have a hand-rolled sort order). Is there any reason I cannot use std::priority_queue<> to do this? Does anyone have an example, or know of one in the docs?
One easy place to find that code is in this function in boost/graph/dijkstra_shortest_paths.hpp:
// Call breadth first search template
inline void dijkstra_shortest_paths_no_init (const Graph& g, typename graph_traits<Graph>::vertex_descriptor s, PredecessorMap predecessor, DistanceMap distance, WeightMap weight, IndexMap index_map, Compare compare, Combine combine, DistZero zero, DijkstraVisitor vis, ColorMap color); (note that there are other overloads that do not call breadth_first_search directly). That code creates a priority queue and uses it in BFS. I do not see any code in BGL that uses std::priority_queue in BFS.
-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
On Thu, 20 May 2010, Eric Fowler wrote:
I don't see how this substitutes a hand-rolled queue.
That code I pointed to creates a queue and uses it in breadth_first_search.
And I don't see why this:
boost::bfs_visitor
nv; std::stack<T> q; breadth_first_search(graph, vertex, q, nv);
Is getting me this:
In file included from MyDialog.h:8, from MyDialog.cpp:2: ../DelaunayGraph/DelaunayGraph.h: In member function ‘Vertex DelaunayGraph<T>::seek_vertex_nearest_point(const POS<T>&) const [with T = short int]’: MyDialog.cpp:44: instantiated from here ../DelaunayGraph/DelaunayGraph.h:214: error: no matching function for call to ‘breadth_first_search(const DelaunayGraph<short int>&, const Vertex&, std::stack
>&, boost::bfs_visitorboost::null_visitor&)’ make: *** [MyDialog.o] Error 1
It appears that the version of breadth_first_search that takes an explicit queue without using named parameters needs an explicitly specified color map as well. -- Jeremiah Willcock
Thank you. I can now compile with an std::vector<> as my queue, and
the default color map.
In looking at the Dijkstra example, I see it is using a
boost::mutable_queue<>, which has the primary feature of being able to
dynamically change the sorting criterion. This is exciting but not
something I need.
Turning my attention to boost::queue<>, I am trying to see how to
place my own sorting criteria. It looks like I need to define a class
encapsulating my data (or deriving from the class that holds my data),
and to define the usual ordering operators (<,>,==, etc) within that
class. I would then declare an object of type boost::queue<MyClass>
and go from there.
Is that the "cheapest" way to get a priority queue with a custom sort order?
Eric
On Fri, May 21, 2010 at 1:13 PM, Jeremiah Willcock
On Thu, 20 May 2010, Eric Fowler wrote:
I don't see how this substitutes a hand-rolled queue.
That code I pointed to creates a queue and uses it in breadth_first_search.
And I don't see why this:
boost::bfs_visitor
nv; std::stack<T> q; breadth_first_search(graph, vertex, q, nv);
Is getting me this:
In file included from MyDialog.h:8, from MyDialog.cpp:2: ../DelaunayGraph/DelaunayGraph.h: In member function ‘Vertex DelaunayGraph<T>::seek_vertex_nearest_point(const POS<T>&) const [with T = short int]’: MyDialog.cpp:44: instantiated from here ../DelaunayGraph/DelaunayGraph.h:214: error: no matching function for call to ‘breadth_first_search(const DelaunayGraph<short int>&, const Vertex&, std::stack
>&, boost::bfs_visitorboost::null_visitor&)’ make: *** [MyDialog.o] Error 1 It appears that the version of breadth_first_search that takes an explicit queue without using named parameters needs an explicitly specified color map as well.
-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
On Fri, 21 May 2010, Eric Fowler wrote:
Thank you. I can now compile with an std::vector<> as my queue, and the default color map.
Named parameters should also allow you to use the built-in color map generation; you weren't using them before so that's why I told you to just add that argument explicitly.
In looking at the Dijkstra example, I see it is using a boost::mutable_queue<>, which has the primary feature of being able to dynamically change the sorting criterion. This is exciting but not something I need.
It's not dynamically changing, or are you referring to update()? That just lets you update the sort key of an element without removing and reinserting it.
Turning my attention to boost::queue<>, I am trying to see how to place my own sorting criteria. It looks like I need to define a class encapsulating my data (or deriving from the class that holds my data), and to define the usual ordering operators (<,>,==, etc) within that class. I would then declare an object of type boost::queue<MyClass> and go from there.
Is that the "cheapest" way to get a priority queue with a custom sort order?
boost::queue<> is unsorted, so you cannot use a sort order with it. Are you sure your problem is not just shortest paths with custom compare and/or combine operators? That is the easiest way: dijkstra_shortest_paths sets up the queue, color map, and such for you. Otherwise, look at the code in dijkstra_shortest_paths that I pointed out and use one of the queues instantiated there. Note that Dijkstra's algorithm does use a custom < operator in its priority queue in the mutable_queue variant (in order to use indirect_cmp and the user's comparison operator which is not necessarily < either). -- Jeremiah Willcock
participants (2)
-
Eric Fowler -
Jeremiah Willcock