fork download
copy 
  1. #include <iostream>
  2. #include <iomanip>
  3.  
  4. #include <boost/graph/grid_graph.hpp>
  5. #include <boost/graph/detail/d_ary_heap.hpp>
  6. #include <boost/property_map/property_map.hpp>
  7.  
  8. #include <cstdlib>
  9.  
  10. template <typename TQueue>
  11. static void OutputQueue(TQueue queue);
  12.  
  13. int main(int, char*[])
  14. {
  15.   // Seed random number gererators
  16.   srand((unsigned int)time(NULL));
  17.   srand48((unsigned int)time(NULL));
  18.  
  19.   // Create a graph
  20.   boost::array<std::size_t, 2> lengths = { { 2,2 } };
  21.   typedef boost::grid_graph<2> GraphType;
  22.   GraphType graph(lengths);
  23.  
  24.   // Declare iterators that we will use
  25.   typedef boost::graph_traits<GraphType>::vertex_iterator VertexIteratorType;
  26.  
  27.   VertexIteratorType vertexIterator, vertexIteratorEnd;
  28.  
  29.   // Setup the graph properties
  30.   typedef boost::graph_traits<GraphType>::vertex_descriptor Vertex;
  31.   typedef boost::property_map<GraphType, boost::vertex_index_t>::const_type GridIndexMapType;
  32.   GridIndexMapType gridIndexMap(get(boost::vertex_index, graph));
  33.  
  34.   typedef boost::vector_property_map<std::size_t, GridIndexMapType> IndexInHeapMap;
  35.   IndexInHeapMap index_in_heap(gridIndexMap);
  36.  
  37.   // Initialize
  38.   for( tie(vertexIterator, vertexIteratorEnd) = vertices(graph); vertexIterator != vertexIteratorEnd; ++vertexIterator)
  39.   {
  40.     put(index_in_heap, *vertexIterator, (size_t)(-1));
  41.   }
  42.  
  43.   typedef boost::vector_property_map<float, GridIndexMapType> PriorityMapType;
  44.   PriorityMapType priorityMap(gridIndexMap);
  45.  
  46.   // Setup the queue
  47.   typedef std::greater<float> ComparisonFunctor;
  48.   typedef boost::d_ary_heap_indirect<Vertex, 4, IndexInHeapMap,
  49.       PriorityMapType, ComparisonFunctor > MutableQueueType;
  50.  
  51.   ComparisonFunctor comparisonFunctor;
  52.   MutableQueueType mutableQueue(priorityMap, index_in_heap, comparisonFunctor);
  53.  
  54.   std::cout << "There are " << mutableQueue.size() << " items in the queue." << std::endl;
  55.  
  56.   // Add random values to the vertices and add them to the queue
  57.   for( tie(vertexIterator, vertexIteratorEnd) = vertices(graph); vertexIterator != vertexIteratorEnd; ++vertexIterator)
  58.   {
  59.     float newPriority = rand() % 1000;
  60.     Vertex v = *vertexIterator;
  61.  
  62.     std::cout << "Original priority for " << v[0] << ", " << v[1] << " " << newPriority << std::endl;
  63.     put(priorityMap, *vertexIterator, newPriority);
  64.     mutableQueue.push(*vertexIterator);
  65.     std::cout << "Index added caller: " << get(index_in_heap, v) << std::endl;
  66.   }
  67.  
  68.   std::cout << "There are " << mutableQueue.size() << " items in the queue." << std::endl;
  69.  
  70.   // Insert another set of random values for each vertex
  71.   for( tie(vertexIterator, vertexIteratorEnd) = vertices(graph); vertexIterator != vertexIteratorEnd; ++vertexIterator)
  72.   {
  73.     float newPriority = rand() % 1000;
  74.  
  75.     Vertex v = *vertexIterator;
  76.     std::cout << "New priority for " << v[0] << ", " << v[1] << " " << newPriority << std::endl;
  77.     put(priorityMap, *vertexIterator, newPriority);
  78.     mutableQueue.update(*vertexIterator);
  79.   }
  80.  
  81.   std::cout << "There are " << mutableQueue.size() << " items in the queue." << std::endl;
  82.  
  83.   while( ! mutableQueue.empty() )
  84.   {
  85. //    MutableQueueType::value_type u = mutableQueue.top();
  86.     Vertex u = mutableQueue.top();
  87.  
  88.     // These two lines are equivalent
  89.     std::cout << "vertex: " << u[0] << " " << u[1]
  90.               << " priority: " << get(mutableQueue.keys(), u)
  91. //              << " indexInHeap: " << get(queue.index_in_heap(), u) // private
  92.               << " indexInHeap: " << get(index_in_heap, u)
  93.               << std::endl;
  94.  
  95.     mutableQueue.pop();
  96.   }
  97.  
  98.   std::cout << std::endl;
  99.  
  100.   return 0;
  101. }
  102.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/OgWF6
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!