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