fork download
copy 
  1.  
  2. #include <iostream>
  3. #include <iomanip>
  4.  
  5. #include <boost/graph/grid_graph.hpp>
  6. #include <boost/graph/detail/d_ary_heap.hpp>
  7. #include <boost/property_map/property_map.hpp>
  8.  
  9. #include <cstdlib>
  10.  
  11. template <typename TQueue>
  12. static void OutputQueue(TQueue queue);
  13.  
  14. int main(int, char*[])
  15. {
  16.   srand((unsigned int)time(NULL));
  17.   srand48((unsigned int)time(NULL));
  18.  
  19.   boost::array<std::size_t, 2> lengths = { { 2,2 } };
  20.   typedef boost::grid_graph<2> GraphType;
  21.   GraphType graph(lengths);
  22.   typedef boost::graph_traits<GraphType>::vertex_descriptor Vertex;
  23.   typedef boost::property_map<GraphType, boost::vertex_index_t>::const_type GridIndexMapType;
  24.   GridIndexMapType gridIndexMap(get(boost::vertex_index, graph));
  25.  
  26.   typedef boost::vector_property_map<std::size_t, GridIndexMapType> IndexInHeapMap;
  27.   IndexInHeapMap index_in_heap(gridIndexMap);
  28.  
  29.   typedef boost::graph_traits<GraphType>::vertex_iterator VertexIteratorType;
  30.  
  31.   typedef boost::vector_property_map<float, GridIndexMapType> PriorityMapType;
  32.   PriorityMapType priorityMap(gridIndexMap);
  33.   VertexIteratorType vertexIterator, vertexIteratorEnd;
  34.  
  35.   typedef std::greater<float> ComparisonFunctor;
  36.   typedef boost::d_ary_heap_indirect<Vertex, 4, IndexInHeapMap, PriorityMapType, ComparisonFunctor > MutableQueueType;
  37.  
  38.   ComparisonFunctor comparisonFunctor;
  39.   MutableQueueType mutableQueue(priorityMap, index_in_heap, comparisonFunctor);
  40.  
  41.   std::cout << "There are " << mutableQueue.size() << " items in the queue." << std::endl;
  42.  
  43.   // Add random values to the vertices and add them to the queue
  44.   for( tie(vertexIterator, vertexIteratorEnd) = vertices(graph); vertexIterator != vertexIteratorEnd; ++vertexIterator)
  45.   {
  46.     float newPriority = rand() % 1000;
  47.     std::cout << "New priority for " << vertexIterator->operator[](0) << ", " << vertexIterator->operator[](1) << " " << newPriority << std::endl;
  48.     put(priorityMap, *vertexIterator, newPriority);
  49.   }
  50.  
  51.   for( tie(vertexIterator, vertexIteratorEnd) = vertices(graph); vertexIterator != vertexIteratorEnd; ++vertexIterator)
  52.   {
  53.     mutableQueue.push(*vertexIterator);
  54.   }
  55.  
  56.   std::cout << "There are " << mutableQueue.size() << " items in the queue." << std::endl;
  57.  
  58.   std::cout << "The priority queue is: " << std::endl;
  59.   OutputQueue(mutableQueue);
  60.  
  61.   // Insert another set of random values for each vertex
  62.   for( tie(vertexIterator, vertexIteratorEnd) = vertices(graph); vertexIterator != vertexIteratorEnd; ++vertexIterator)
  63.   {
  64.     float newPriority = rand() % 1000;
  65.     std::cout << "New priority for " << vertexIterator->operator[](0) << ", " << vertexIterator->operator[](1) << " " << newPriority << std::endl;
  66.     put(priorityMap, *vertexIterator, newPriority);
  67.     mutableQueue.update(*vertexIterator);
  68.   }
  69.  
  70.   std::cout << "There are " << mutableQueue.size() << " items in the queue." << std::endl;
  71.  
  72.   std::cout << "The priority queue is: " << std::endl;
  73. //  OutputQueue(mutableQueue);
  74.  
  75.   while( ! mutableQueue.empty() )
  76.   {
  77.     MutableQueueType::value_type u = mutableQueue.top();
  78.  
  79.     // These two lines are equivalent
  80.     std::cout << "vertex: " << u[0] << " " << u[1]
  81.               << " priority: " << get(mutableQueue.keys(), u)
  82. //              << " indexInHeap: " << get(queue.index_in_heap(), u) // private
  83.               << " indexInHeap: " << get(index_in_heap, u)
  84.               << std::endl;
  85.  
  86.     mutableQueue.pop();
  87.   }
  88.  
  89.   std::cout << std::endl;
  90.  
  91.   return 0;
  92. }
  93.  
  94. template <typename TQueue>
  95. static void OutputQueue(TQueue queue)
  96. {
  97.   while( ! queue.empty() )
  98.   {
  99.     typename TQueue::value_type u = queue.top();
  100.  
  101.     // These two lines are equivalent
  102.     std::cout << "vertex: " << u[0] << " " << u[1]
  103.               << " priority: " << get(queue.keys(), u)
  104.               << std::endl;
  105.  
  106.     queue.pop();
  107.   }
  108. }
  109.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:5:38: error: boost/graph/grid_graph.hpp: No such file or directory
prog.cpp:6:45: error: boost/graph/detail/d_ary_heap.hpp: No such file or directory
prog.cpp:7:47: error: boost/property_map/property_map.hpp: No such file or directory
prog.cpp: In function ‘int main(int, char**)’:
prog.cpp:19: error: ‘boost’ has not been declared
prog.cpp:19: error: expected primary-expression before ‘,’ token
prog.cpp:19: error: ‘lengths’ was not declared in this scope
prog.cpp:19: error: expected primary-expression before ‘{’ token
prog.cpp:19: error: expected `;' before ‘{’ token
prog.cpp:108: error: expected `}' at end of input
stdout
copy 
Standard output is empty
https://ideone.com/uj2lM
language:
C++ (gcc 8.3)
created:
12 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!