Difference between revisions of "CPP/Boost/BGL/IndirectPriorityQueue"
From ProgrammingExamples
< CPP
Daviddoria (Talk | contribs) (Created page with '==IndirectPriorityQueue.cpp== <source lang="cpp"> #include <iostream> #include <iomanip> #include <boost/graph/grid_graph.hpp> #include <boost/graph/detail/d_ary_heap.hpp> #incl…') |
(No difference)
|
Revision as of 10:42, 3 September 2012
IndirectPriorityQueue.cpp
#include <iostream> #include <iomanip> #include <boost/graph/grid_graph.hpp> #include <boost/graph/detail/d_ary_heap.hpp> #include <boost/property_map/property_map.hpp> #include <cstdlib> int main(int, char*[]) { srand((unsigned int)time(NULL)); boost::array<std::size_t, 2> lengths = { { 5,5 } }; 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::vector_property_map<std::size_t, GridIndexMapType> IndexInHeapMap; IndexInHeapMap index_in_heap(gridIndexMap); typedef boost::graph_traits<GraphType>::vertex_iterator VertexIteratorType; typedef boost::vector_property_map<float, GridIndexMapType> PriorityMapType; PriorityMapType priorityMap(gridIndexMap); VertexIteratorType vertexIterator, vertexIteratorEnd; typedef std::greater<float> ComparisonFunctor; typedef boost::d_ary_heap_indirect<Vertex, 4, IndexInHeapMap, PriorityMapType, ComparisonFunctor > MutableQueue; ComparisonFunctor comparisonFunctor; MutableQueue mutableQueue(priorityMap, index_in_heap, comparisonFunctor); std::cout << "There are " << mutableQueue.size() << " items in the queue." << std::endl; // Add random values to the vertices and add them to the queue for( tie(vertexIterator, vertexIteratorEnd) = vertices(graph); vertexIterator != vertexIteratorEnd; ++vertexIterator) { put(priorityMap, *vertexIterator, rand() % 1000); } for( tie(vertexIterator, vertexIteratorEnd) = vertices(graph); vertexIterator != vertexIteratorEnd; ++vertexIterator) { mutableQueue.push(*vertexIterator); } std::cout << "There are " << mutableQueue.size() << " items in the queue." << std::endl; // Insert another set of random values for each vertex for( tie(vertexIterator, vertexIteratorEnd) = vertices(graph); vertexIterator != vertexIteratorEnd; ++vertexIterator) { put(priorityMap, *vertexIterator, rand() % 1000); } for( tie(vertexIterator, vertexIteratorEnd) = vertices(graph); vertexIterator != vertexIteratorEnd; ++vertexIterator) { mutableQueue.push(*vertexIterator); } std::cout << "There are " << mutableQueue.size() << " items in the queue." << std::endl; std::cout << "The priority queue is: " << std::endl; while( ! mutableQueue.empty() ) { Vertex u = mutableQueue.top(); // These two lines are equivalent std::cout << "vertex: " << u[0] << " " << u[1] << " priority: " << get(priorityMap, u) << std::endl; mutableQueue.pop(); } std::cout << std::endl; return 0; } /* Output: There are 0 items in the queue. There are 25 items in the queue. There are 50 items in the queue. The priority queue is: vertex: 2 4 priority: 967 vertex: 0 0 priority: 945 vertex: 0 0 priority: 945 vertex: 1 3 priority: 922 vertex: 0 2 priority: 907 vertex: 4 4 priority: 901 vertex: 2 4 priority: 967 vertex: 4 4 priority: 901 vertex: 0 1 priority: 858 vertex: 0 2 priority: 907 vertex: 0 1 priority: 858 vertex: 3 4 priority: 852 vertex: 3 4 priority: 852 vertex: 2 2 priority: 793 vertex: 2 2 priority: 793 vertex: 1 3 priority: 922 vertex: 1 1 priority: 791 vertex: 1 1 priority: 791 vertex: 4 2 priority: 781 vertex: 4 2 priority: 781 vertex: 1 2 priority: 748 vertex: 1 2 priority: 748 vertex: 2 3 priority: 734 vertex: 4 3 priority: 661 vertex: 4 3 priority: 661 vertex: 2 3 priority: 734 vertex: 3 3 priority: 652 vertex: 3 3 priority: 652 vertex: 3 2 priority: 529 vertex: 3 2 priority: 529 vertex: 3 0 priority: 493 vertex: 3 0 priority: 493 vertex: 2 0 priority: 488 vertex: 2 0 priority: 488 vertex: 4 1 priority: 450 vertex: 4 1 priority: 450 vertex: 4 0 priority: 346 vertex: 4 0 priority: 346 vertex: 0 3 priority: 328 vertex: 0 3 priority: 328 vertex: 1 4 priority: 245 vertex: 1 4 priority: 245 vertex: 1 0 priority: 216 vertex: 1 0 priority: 216 vertex: 0 4 priority: 64 vertex: 0 4 priority: 64 vertex: 2 1 priority: 47 vertex: 2 1 priority: 47 vertex: 3 1 priority: 14 vertex: 3 1 priority: 14 */
CMakeLists.txt
cmake_minimum_required(VERSION 2.6) Project(IndirectPriorityQueue) set(Boost_USE_MULTITHREADED ON) FIND_PACKAGE(Boost 1.38 COMPONENTS) INCLUDE_DIRECTORIES(${INCLUDE_DIRECTORIES} ${Boost_INCLUDE_DIRS}) LINK_DIRECTORIES(${LINK_DIRECTORIES} ${Boost_LIBRARY_DIRS}) ADD_EXECUTABLE(IndirectPriorityQueue IndirectPriorityQueue.cpp)