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…') |
Daviddoria (Talk | contribs) |
||
Line 9: | Line 9: | ||
#include <cstdlib> | #include <cstdlib> | ||
+ | |||
+ | template <typename TQueue> | ||
+ | static void OutputQueue(TQueue queue); | ||
int main(int, char*[]) | int main(int, char*[]) | ||
Line 31: | Line 34: | ||
typedef std::greater<float> ComparisonFunctor; | typedef std::greater<float> ComparisonFunctor; | ||
− | typedef boost::d_ary_heap_indirect<Vertex, 4, IndexInHeapMap, PriorityMapType, ComparisonFunctor > | + | typedef boost::d_ary_heap_indirect<Vertex, 4, IndexInHeapMap, PriorityMapType, ComparisonFunctor > MutableQueueType; |
ComparisonFunctor comparisonFunctor; | ComparisonFunctor comparisonFunctor; | ||
− | + | MutableQueueType mutableQueue(priorityMap, index_in_heap, comparisonFunctor); | |
std::cout << "There are " << mutableQueue.size() << " items in the queue." << std::endl; | std::cout << "There are " << mutableQueue.size() << " items in the queue." << std::endl; | ||
Line 50: | Line 53: | ||
std::cout << "There are " << mutableQueue.size() << " items in the queue." << std::endl; | std::cout << "There are " << mutableQueue.size() << " items in the queue." << std::endl; | ||
+ | |||
+ | std::cout << "The priority queue is: " << std::endl; | ||
+ | OutputQueue(mutableQueue); | ||
// Insert another set of random values for each vertex | // Insert another set of random values for each vertex | ||
Line 65: | Line 71: | ||
std::cout << "The priority queue is: " << std::endl; | std::cout << "The priority queue is: " << std::endl; | ||
− | while( ! | + | OutputQueue(mutableQueue); |
+ | |||
+ | std::cout << std::endl; | ||
+ | |||
+ | return 0; | ||
+ | } | ||
+ | |||
+ | template <typename TQueue> | ||
+ | static void OutputQueue(TQueue queue) | ||
+ | { | ||
+ | while( ! queue.empty() ) | ||
{ | { | ||
− | + | typename TQueue::value_type u = queue.top(); | |
// These two lines are equivalent | // These two lines are equivalent | ||
− | std::cout << "vertex: " << u[0] << " " << u[1] << " priority: " << get( | + | std::cout << "vertex: " << u[0] << " " << u[1] << " priority: " << get(queue.keys(), u) << std::endl; |
− | + | queue.pop(); | |
} | } | ||
− | |||
− | |||
− | |||
− | |||
} | } | ||
Line 83: | Line 95: | ||
There are 0 items in the queue. | There are 0 items in the queue. | ||
There are 25 items in the queue. | There are 25 items in the queue. | ||
+ | The priority queue is: | ||
+ | vertex: 4 3 priority: 989 | ||
+ | vertex: 3 2 priority: 976 | ||
+ | vertex: 0 1 priority: 937 | ||
+ | vertex: 1 4 priority: 824 | ||
+ | vertex: 0 2 priority: 805 | ||
+ | vertex: 1 0 priority: 770 | ||
+ | vertex: 4 2 priority: 770 | ||
+ | vertex: 4 4 priority: 733 | ||
+ | vertex: 2 2 priority: 623 | ||
+ | vertex: 0 4 priority: 566 | ||
+ | vertex: 3 0 priority: 513 | ||
+ | vertex: 4 0 priority: 494 | ||
+ | vertex: 2 3 priority: 418 | ||
+ | vertex: 3 1 priority: 411 | ||
+ | vertex: 1 1 priority: 408 | ||
+ | vertex: 0 3 priority: 378 | ||
+ | vertex: 3 3 priority: 300 | ||
+ | vertex: 3 4 priority: 286 | ||
+ | vertex: 0 0 priority: 206 | ||
+ | vertex: 2 1 priority: 198 | ||
+ | vertex: 1 2 priority: 159 | ||
+ | vertex: 2 0 priority: 157 | ||
+ | vertex: 2 4 priority: 108 | ||
+ | vertex: 1 3 priority: 103 | ||
+ | vertex: 4 1 priority: 5 | ||
There are 50 items in the queue. | There are 50 items in the queue. | ||
The priority queue is: | The priority queue is: | ||
− | vertex: | + | vertex: 3 0 priority: 998 |
− | vertex: | + | vertex: 3 2 priority: 979 |
− | vertex: | + | vertex: 3 2 priority: 979 |
− | vertex: | + | vertex: 2 4 priority: 920 |
− | vertex: 0 | + | vertex: 0 1 priority: 853 |
− | vertex: | + | vertex: 0 1 priority: 853 |
− | vertex: | + | vertex: 3 0 priority: 998 |
− | vertex: 4 4 priority: | + | vertex: 4 4 priority: 842 |
− | vertex: | + | vertex: 2 2 priority: 830 |
− | vertex: | + | vertex: 2 2 priority: 830 |
− | + | vertex: 3 3 priority: 811 | |
− | vertex: 3 | + | vertex: 3 3 priority: 811 |
− | vertex: 3 | + | vertex: 0 2 priority: 781 |
− | vertex: | + | vertex: 0 2 priority: 781 |
− | vertex: | + | vertex: 1 1 priority: 556 |
− | vertex: 1 | + | vertex: 4 0 priority: 517 |
− | vertex: | + | vertex: 4 0 priority: 517 |
− | vertex: | + | vertex: 4 3 priority: 464 |
− | vertex: 4 | + | vertex: 4 3 priority: 464 |
− | vertex: 4 | + | vertex: 3 1 priority: 363 |
− | vertex: 1 | + | vertex: 3 1 priority: 363 |
− | vertex: 1 | + | vertex: 0 4 priority: 345 |
− | vertex: | + | vertex: 1 1 priority: 556 |
− | vertex: | + | vertex: 0 4 priority: 345 |
− | vertex: 4 | + | vertex: 1 2 priority: 300 |
− | vertex: 2 | + | vertex: 1 2 priority: 300 |
− | vertex: | + | vertex: 4 4 priority: 842 |
− | vertex: | + | vertex: 2 1 priority: 287 |
− | vertex: | + | vertex: 2 1 priority: 287 |
− | vertex: | + | vertex: 2 3 priority: 222 |
− | vertex: 3 | + | vertex: 2 3 priority: 222 |
− | vertex: 3 | + | vertex: 1 0 priority: 197 |
− | vertex: | + | vertex: 2 4 priority: 920 |
− | vertex: 2 | + | vertex: 1 0 priority: 197 |
− | vertex: | + | vertex: 1 4 priority: 189 |
− | vertex: | + | vertex: 1 4 priority: 189 |
− | vertex: 4 | + | vertex: 0 3 priority: 187 |
− | vertex: | + | vertex: 0 3 priority: 187 |
− | vertex: 0 3 priority: | + | vertex: 1 3 priority: 136 |
− | vertex: | + | vertex: 1 3 priority: 136 |
− | vertex: 1 | + | vertex: 0 0 priority: 119 |
− | vertex: | + | vertex: 0 0 priority: 119 |
− | vertex: | + | vertex: 2 0 priority: 118 |
− | vertex: | + | vertex: 2 0 priority: 118 |
− | vertex: 0 4 priority: | + | vertex: 3 4 priority: 115 |
− | vertex: | + | vertex: 3 4 priority: 115 |
− | vertex: | + | vertex: 4 1 priority: 70 |
− | vertex: | + | vertex: 4 1 priority: 70 |
− | vertex: | + | vertex: 4 2 priority: 63 |
− | vertex: | + | vertex: 4 2 priority: 63 |
*/ | */ | ||
+ | |||
</source> | </source> | ||
Latest revision as of 10:51, 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> template <typename TQueue> static void OutputQueue(TQueue queue); 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 > MutableQueueType; ComparisonFunctor comparisonFunctor; MutableQueueType 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; std::cout << "The priority queue is: " << std::endl; OutputQueue(mutableQueue); // 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; OutputQueue(mutableQueue); std::cout << std::endl; return 0; } template <typename TQueue> static void OutputQueue(TQueue queue) { while( ! queue.empty() ) { typename TQueue::value_type u = queue.top(); // These two lines are equivalent std::cout << "vertex: " << u[0] << " " << u[1] << " priority: " << get(queue.keys(), u) << std::endl; queue.pop(); } } /* Output: There are 0 items in the queue. There are 25 items in the queue. The priority queue is: vertex: 4 3 priority: 989 vertex: 3 2 priority: 976 vertex: 0 1 priority: 937 vertex: 1 4 priority: 824 vertex: 0 2 priority: 805 vertex: 1 0 priority: 770 vertex: 4 2 priority: 770 vertex: 4 4 priority: 733 vertex: 2 2 priority: 623 vertex: 0 4 priority: 566 vertex: 3 0 priority: 513 vertex: 4 0 priority: 494 vertex: 2 3 priority: 418 vertex: 3 1 priority: 411 vertex: 1 1 priority: 408 vertex: 0 3 priority: 378 vertex: 3 3 priority: 300 vertex: 3 4 priority: 286 vertex: 0 0 priority: 206 vertex: 2 1 priority: 198 vertex: 1 2 priority: 159 vertex: 2 0 priority: 157 vertex: 2 4 priority: 108 vertex: 1 3 priority: 103 vertex: 4 1 priority: 5 There are 50 items in the queue. The priority queue is: vertex: 3 0 priority: 998 vertex: 3 2 priority: 979 vertex: 3 2 priority: 979 vertex: 2 4 priority: 920 vertex: 0 1 priority: 853 vertex: 0 1 priority: 853 vertex: 3 0 priority: 998 vertex: 4 4 priority: 842 vertex: 2 2 priority: 830 vertex: 2 2 priority: 830 vertex: 3 3 priority: 811 vertex: 3 3 priority: 811 vertex: 0 2 priority: 781 vertex: 0 2 priority: 781 vertex: 1 1 priority: 556 vertex: 4 0 priority: 517 vertex: 4 0 priority: 517 vertex: 4 3 priority: 464 vertex: 4 3 priority: 464 vertex: 3 1 priority: 363 vertex: 3 1 priority: 363 vertex: 0 4 priority: 345 vertex: 1 1 priority: 556 vertex: 0 4 priority: 345 vertex: 1 2 priority: 300 vertex: 1 2 priority: 300 vertex: 4 4 priority: 842 vertex: 2 1 priority: 287 vertex: 2 1 priority: 287 vertex: 2 3 priority: 222 vertex: 2 3 priority: 222 vertex: 1 0 priority: 197 vertex: 2 4 priority: 920 vertex: 1 0 priority: 197 vertex: 1 4 priority: 189 vertex: 1 4 priority: 189 vertex: 0 3 priority: 187 vertex: 0 3 priority: 187 vertex: 1 3 priority: 136 vertex: 1 3 priority: 136 vertex: 0 0 priority: 119 vertex: 0 0 priority: 119 vertex: 2 0 priority: 118 vertex: 2 0 priority: 118 vertex: 3 4 priority: 115 vertex: 3 4 priority: 115 vertex: 4 1 priority: 70 vertex: 4 1 priority: 70 vertex: 4 2 priority: 63 vertex: 4 2 priority: 63 */
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)