Difference between revisions of "CPP/Boost/Heap/IndirectCompare"

From ProgrammingExamples
< CPP
Jump to: navigation, search
(Created page with '<syntaxhighlight lang="cpp"> #include <boost/heap/binomial_heap.hpp> #include <boost/pending/indirect_cmp.hpp> #include <boost/array.hpp> #include <boost/graph/grid_graph.hpp> #i…')
 
(No difference)

Latest revision as of 17:35, 5 September 2012

#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;
}