Daviddoria at 14:51, 3 September 2012

2012-09-03T14:51:20Z

Daviddoria: Created page with '==IndirectPriorityQueue.cpp== #include #include #include #include #incl…'

2012-09-03T14:42:45Z

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…'

New page

==IndirectPriorityQueue.cpp==
<source lang="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

*/
</source>

==CMakeLists.txt==
<source lang="cmake">
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)

</source>

CPP/Boost/BGL/IndirectPriorityQueue - Revision history

Daviddoria at 14:51, 3 September 2012

Daviddoria: Created page with '==IndirectPriorityQueue.cpp== #include #include #include #include #incl…'