#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*[])
{
// Seed random number gererators
srand((unsigned int)time(NULL));
srand48((unsigned int)time(NULL));
// Create a graph
boost::array<std::size_t, 2> lengths = { { 2,2 } };
typedef boost::grid_graph<2> GraphType;
GraphType graph(lengths);
// Declare iterators that we will use
typedef boost::graph_traits<GraphType>::vertex_iterator VertexIteratorType;
VertexIteratorType vertexIterator, vertexIteratorEnd;
// Setup the graph properties
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);
// Initialize
for( tie(vertexIterator, vertexIteratorEnd) = vertices(graph); vertexIterator != vertexIteratorEnd; ++vertexIterator)
{
put(index_in_heap, *vertexIterator, (size_t)(-1));
}
typedef boost::vector_property_map<float, GridIndexMapType> PriorityMapType;
PriorityMapType priorityMap(gridIndexMap);
// Setup the queue
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)
{
float newPriority = rand() % 1000;
Vertex v = *vertexIterator;
std::cout << "Original priority for " << v[0] << ", " << v[1] << " " << newPriority << std::endl;
put(priorityMap, *vertexIterator, newPriority);
mutableQueue.push(*vertexIterator);
std::cout << "Index added caller: " << get(index_in_heap, v) << std::endl;
}
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)
{
float newPriority = rand() % 1000;
Vertex v = *vertexIterator;
std::cout << "New priority for " << v[0] << ", " << v[1] << " " << newPriority << std::endl;
put(priorityMap, *vertexIterator, newPriority);
mutableQueue.update(*vertexIterator);
}
std::cout << "There are " << mutableQueue.size() << " items in the queue." << std::endl;
while( ! mutableQueue.empty() )
{
// MutableQueueType::value_type u = mutableQueue.top();
Vertex u = mutableQueue.top();
// These two lines are equivalent
std::cout << "vertex: " << u[0] << " " << u[1]
<< " priority: " << get(mutableQueue.keys(), u)
// << " indexInHeap: " << get(queue.index_in_heap(), u) // private
<< " indexInHeap: " << get(index_in_heap, u)
<< std::endl;
mutableQueue.pop();
}
std::cout << std::endl;
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8aW9tYW5pcD4KCiNpbmNsdWRlIDxib29zdC9ncmFwaC9ncmlkX2dyYXBoLmhwcD4KI2luY2x1ZGUgPGJvb3N0L2dyYXBoL2RldGFpbC9kX2FyeV9oZWFwLmhwcD4KI2luY2x1ZGUgPGJvb3N0L3Byb3BlcnR5X21hcC9wcm9wZXJ0eV9tYXAuaHBwPgoKI2luY2x1ZGUgPGNzdGRsaWI+Cgp0ZW1wbGF0ZSA8dHlwZW5hbWUgVFF1ZXVlPgpzdGF0aWMgdm9pZCBPdXRwdXRRdWV1ZShUUXVldWUgcXVldWUpOwoKaW50IG1haW4oaW50LCBjaGFyKltdKQp7CiAgLy8gU2VlZCByYW5kb20gbnVtYmVyIGdlcmVyYXRvcnMKICBzcmFuZCgodW5zaWduZWQgaW50KXRpbWUoTlVMTCkpOwogIHNyYW5kNDgoKHVuc2lnbmVkIGludCl0aW1lKE5VTEwpKTsKCiAgLy8gQ3JlYXRlIGEgZ3JhcGgKICBib29zdDo6YXJyYXk8c3RkOjpzaXplX3QsIDI+IGxlbmd0aHMgPSB7IHsgMiwyIH0gfTsKICB0eXBlZGVmIGJvb3N0OjpncmlkX2dyYXBoPDI+IEdyYXBoVHlwZTsKICBHcmFwaFR5cGUgZ3JhcGgobGVuZ3Rocyk7CgogIC8vIERlY2xhcmUgaXRlcmF0b3JzIHRoYXQgd2Ugd2lsbCB1c2UKICB0eXBlZGVmIGJvb3N0OjpncmFwaF90cmFpdHM8R3JhcGhUeXBlPjo6dmVydGV4X2l0ZXJhdG9yIFZlcnRleEl0ZXJhdG9yVHlwZTsKCiAgVmVydGV4SXRlcmF0b3JUeXBlIHZlcnRleEl0ZXJhdG9yLCB2ZXJ0ZXhJdGVyYXRvckVuZDsKCiAgLy8gU2V0dXAgdGhlIGdyYXBoIHByb3BlcnRpZXMKICB0eXBlZGVmIGJvb3N0OjpncmFwaF90cmFpdHM8R3JhcGhUeXBlPjo6dmVydGV4X2Rlc2NyaXB0b3IgVmVydGV4OwogIHR5cGVkZWYgYm9vc3Q6OnByb3BlcnR5X21hcDxHcmFwaFR5cGUsIGJvb3N0Ojp2ZXJ0ZXhfaW5kZXhfdD46OmNvbnN0X3R5cGUgR3JpZEluZGV4TWFwVHlwZTsKICBHcmlkSW5kZXhNYXBUeXBlIGdyaWRJbmRleE1hcChnZXQoYm9vc3Q6OnZlcnRleF9pbmRleCwgZ3JhcGgpKTsKCiAgdHlwZWRlZiBib29zdDo6dmVjdG9yX3Byb3BlcnR5X21hcDxzdGQ6OnNpemVfdCwgR3JpZEluZGV4TWFwVHlwZT4gSW5kZXhJbkhlYXBNYXA7CiAgSW5kZXhJbkhlYXBNYXAgaW5kZXhfaW5faGVhcChncmlkSW5kZXhNYXApOwoKICAvLyBJbml0aWFsaXplCiAgZm9yKCB0aWUodmVydGV4SXRlcmF0b3IsIHZlcnRleEl0ZXJhdG9yRW5kKSA9IHZlcnRpY2VzKGdyYXBoKTsgdmVydGV4SXRlcmF0b3IgIT0gdmVydGV4SXRlcmF0b3JFbmQ7ICsrdmVydGV4SXRlcmF0b3IpCiAgewogICAgcHV0KGluZGV4X2luX2hlYXAsICp2ZXJ0ZXhJdGVyYXRvciwgKHNpemVfdCkoLTEpKTsKICB9CgogIHR5cGVkZWYgYm9vc3Q6OnZlY3Rvcl9wcm9wZXJ0eV9tYXA8ZmxvYXQsIEdyaWRJbmRleE1hcFR5cGU+IFByaW9yaXR5TWFwVHlwZTsKICBQcmlvcml0eU1hcFR5cGUgcHJpb3JpdHlNYXAoZ3JpZEluZGV4TWFwKTsKCiAgLy8gU2V0dXAgdGhlIHF1ZXVlCiAgdHlwZWRlZiBzdGQ6OmdyZWF0ZXI8ZmxvYXQ+IENvbXBhcmlzb25GdW5jdG9yOwogIHR5cGVkZWYgYm9vc3Q6OmRfYXJ5X2hlYXBfaW5kaXJlY3Q8VmVydGV4LCA0LCBJbmRleEluSGVhcE1hcCwKICAgICAgUHJpb3JpdHlNYXBUeXBlLCBDb21wYXJpc29uRnVuY3RvciA+IE11dGFibGVRdWV1ZVR5cGU7CgogIENvbXBhcmlzb25GdW5jdG9yIGNvbXBhcmlzb25GdW5jdG9yOwogIE11dGFibGVRdWV1ZVR5cGUgbXV0YWJsZVF1ZXVlKHByaW9yaXR5TWFwLCBpbmRleF9pbl9oZWFwLCBjb21wYXJpc29uRnVuY3Rvcik7CgogIHN0ZDo6Y291dCA8PCAiVGhlcmUgYXJlICIgPDwgbXV0YWJsZVF1ZXVlLnNpemUoKSA8PCAiIGl0ZW1zIGluIHRoZSBxdWV1ZS4iIDw8IHN0ZDo6ZW5kbDsKCiAgLy8gQWRkIHJhbmRvbSB2YWx1ZXMgdG8gdGhlIHZlcnRpY2VzIGFuZCBhZGQgdGhlbSB0byB0aGUgcXVldWUKICBmb3IoIHRpZSh2ZXJ0ZXhJdGVyYXRvciwgdmVydGV4SXRlcmF0b3JFbmQpID0gdmVydGljZXMoZ3JhcGgpOyB2ZXJ0ZXhJdGVyYXRvciAhPSB2ZXJ0ZXhJdGVyYXRvckVuZDsgKyt2ZXJ0ZXhJdGVyYXRvcikKICB7CiAgICBmbG9hdCBuZXdQcmlvcml0eSA9IHJhbmQoKSAlIDEwMDA7CiAgICBWZXJ0ZXggdiA9ICp2ZXJ0ZXhJdGVyYXRvcjsKCiAgICBzdGQ6OmNvdXQgPDwgIk9yaWdpbmFsIHByaW9yaXR5IGZvciAiIDw8IHZbMF0gPDwgIiwgIiA8PCB2WzFdIDw8ICIgIiA8PCBuZXdQcmlvcml0eSA8PCBzdGQ6OmVuZGw7CiAgICBwdXQocHJpb3JpdHlNYXAsICp2ZXJ0ZXhJdGVyYXRvciwgbmV3UHJpb3JpdHkpOwogICAgbXV0YWJsZVF1ZXVlLnB1c2goKnZlcnRleEl0ZXJhdG9yKTsKICAgIHN0ZDo6Y291dCA8PCAiSW5kZXggYWRkZWQgY2FsbGVyOiAiIDw8IGdldChpbmRleF9pbl9oZWFwLCB2KSA8PCBzdGQ6OmVuZGw7CiAgfQoKICBzdGQ6OmNvdXQgPDwgIlRoZXJlIGFyZSAiIDw8IG11dGFibGVRdWV1ZS5zaXplKCkgPDwgIiBpdGVtcyBpbiB0aGUgcXVldWUuIiA8PCBzdGQ6OmVuZGw7CgogIC8vIEluc2VydCBhbm90aGVyIHNldCBvZiByYW5kb20gdmFsdWVzIGZvciBlYWNoIHZlcnRleAogIGZvciggdGllKHZlcnRleEl0ZXJhdG9yLCB2ZXJ0ZXhJdGVyYXRvckVuZCkgPSB2ZXJ0aWNlcyhncmFwaCk7IHZlcnRleEl0ZXJhdG9yICE9IHZlcnRleEl0ZXJhdG9yRW5kOyArK3ZlcnRleEl0ZXJhdG9yKQogIHsKICAgIGZsb2F0IG5ld1ByaW9yaXR5ID0gcmFuZCgpICUgMTAwMDsKCiAgICBWZXJ0ZXggdiA9ICp2ZXJ0ZXhJdGVyYXRvcjsKICAgIHN0ZDo6Y291dCA8PCAiTmV3IHByaW9yaXR5IGZvciAiIDw8IHZbMF0gPDwgIiwgIiA8PCB2WzFdIDw8ICIgIiA8PCBuZXdQcmlvcml0eSA8PCBzdGQ6OmVuZGw7CiAgICBwdXQocHJpb3JpdHlNYXAsICp2ZXJ0ZXhJdGVyYXRvciwgbmV3UHJpb3JpdHkpOwogICAgbXV0YWJsZVF1ZXVlLnVwZGF0ZSgqdmVydGV4SXRlcmF0b3IpOwogIH0KCiAgc3RkOjpjb3V0IDw8ICJUaGVyZSBhcmUgIiA8PCBtdXRhYmxlUXVldWUuc2l6ZSgpIDw8ICIgaXRlbXMgaW4gdGhlIHF1ZXVlLiIgPDwgc3RkOjplbmRsOwoKICB3aGlsZSggISBtdXRhYmxlUXVldWUuZW1wdHkoKSApCiAgewovLyAgICBNdXRhYmxlUXVldWVUeXBlOjp2YWx1ZV90eXBlIHUgPSBtdXRhYmxlUXVldWUudG9wKCk7CiAgICBWZXJ0ZXggdSA9IG11dGFibGVRdWV1ZS50b3AoKTsKCiAgICAvLyBUaGVzZSB0d28gbGluZXMgYXJlIGVxdWl2YWxlbnQKICAgIHN0ZDo6Y291dCA8PCAidmVydGV4OiAiIDw8IHVbMF0gPDwgIiAiIDw8IHVbMV0KICAgICAgICAgICAgICA8PCAiIHByaW9yaXR5OiAiIDw8IGdldChtdXRhYmxlUXVldWUua2V5cygpLCB1KQovLyAgICAgICAgICAgICAgPDwgIiBpbmRleEluSGVhcDogIiA8PCBnZXQocXVldWUuaW5kZXhfaW5faGVhcCgpLCB1KSAvLyBwcml2YXRlCiAgICAgICAgICAgICAgPDwgIiBpbmRleEluSGVhcDogIiA8PCBnZXQoaW5kZXhfaW5faGVhcCwgdSkKICAgICAgICAgICAgICA8PCBzdGQ6OmVuZGw7CgogICAgbXV0YWJsZVF1ZXVlLnBvcCgpOwogIH0KCiAgc3RkOjpjb3V0IDw8IHN0ZDo6ZW5kbDsKCiAgcmV0dXJuIDA7Cn0K