CPP/Boost/Heap/IndirectCompare
From ProgrammingExamples
< CPP
#include <boost/heap/binomial_heap.hpp> #include <boost/pending/indirect_cmp.hpp> #include <boost/array.hpp> #include <boost/graph/grid_graph.hpp> #include <iostream> int main(int, char*[]) { boost::array<std::size_t, 2> lengths = { { 2,2 } }; typedef boost::grid_graph<2> GraphType; GraphType graph(lengths); typedef boost::graph_traits<GraphType>::vertex_descriptor Vertex; typedef boost::property_map<GraphType, boost::vertex_index_t>::const_type GridIndexMapType; GridIndexMapType gridIndexMap(get(boost::vertex_index, graph)); typedef boost::graph_traits<GraphType>::vertex_iterator VertexIteratorType; VertexIteratorType vertexIterator, vertexIteratorEnd; typedef boost::vector_property_map<float, GridIndexMapType> PriorityMapType; PriorityMapType priorityMap(gridIndexMap); typedef boost::indirect_cmp<PriorityMapType, std::less<float> > IndirectComparisonType; IndirectComparisonType indirectComparison(priorityMap); typedef boost::heap::binomial_heap<Vertex, boost::heap::stable<false>, boost::heap::compare<IndirectComparisonType> > PriorityQueueType; PriorityQueueType pq(indirectComparison); typedef typename PriorityQueueType::handle_type handle_t; for( tie(vertexIterator, vertexIteratorEnd) = vertices(graph); vertexIterator != vertexIteratorEnd; ++vertexIterator) { put(priorityMap, *vertexIterator, rand() % 1000); pq.push(*vertexIterator); } // Change all of the priorities in the map for( tie(vertexIterator, vertexIteratorEnd) = vertices(graph); vertexIterator != vertexIteratorEnd; ++vertexIterator) { put(priorityMap, *vertexIterator, rand() % 1000); } // Resort the queue for( tie(vertexIterator, vertexIteratorEnd) = vertices(graph); vertexIterator != vertexIteratorEnd; ++vertexIterator) { // pq.update(handle3, 5); } // Output the final queue while(!pq.empty()) { Vertex v = pq.top(); std::cout << v[0] << " " << v[1] << std::endl; pq.pop(); } return 0; }