fork 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 TGraph, typename TIndexInHeapMap>
  11. static void OutputIndexHeapMap(TGraph g, TIndexInHeapMap indexHeapMap);
  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. std::cout << "Initial heap map" << std::endl;
  44. OutputIndexHeapMap(graph, index_in_heap);
  45.  
  46. typedef boost::vector_property_map<float, GridIndexMapType> PriorityMapType;
  47. PriorityMapType priorityMap(gridIndexMap);
  48.  
  49. // Setup the queue
  50. typedef std::greater<float> ComparisonFunctor;
  51. typedef boost::d_ary_heap_indirect<Vertex, 4, IndexInHeapMap,
  52. PriorityMapType, ComparisonFunctor > MutableQueueType;
  53.  
  54. ComparisonFunctor comparisonFunctor;
  55. MutableQueueType mutableQueue(priorityMap, index_in_heap, comparisonFunctor);
  56.  
  57. std::cout << "There are " << mutableQueue.size() << " items in the queue." << std::endl;
  58.  
  59. // Add random values to the vertices and add them to the queue
  60. for( tie(vertexIterator, vertexIteratorEnd) = vertices(graph); vertexIterator != vertexIteratorEnd; ++vertexIterator)
  61. {
  62. float newPriority = rand() % 1000;
  63. Vertex v = *vertexIterator;
  64.  
  65. std::cout << "Original priority for " << v[0] << ", " << v[1] << " " << newPriority << std::endl;
  66. put(priorityMap, *vertexIterator, newPriority);
  67. mutableQueue.push(*vertexIterator);
  68. }
  69.  
  70. std::cout << "Heap map after initial pushes:" << std::endl;
  71. OutputIndexHeapMap(graph, index_in_heap);
  72.  
  73. std::cout << "There are " << mutableQueue.size() << " items in the queue." << std::endl;
  74.  
  75. // Insert another set of random values for each vertex
  76. for( tie(vertexIterator, vertexIteratorEnd) = vertices(graph); vertexIterator != vertexIteratorEnd; ++vertexIterator)
  77. {
  78. float newPriority = rand() % 1000;
  79.  
  80. Vertex v = *vertexIterator;
  81. std::cout << "New priority for " << v[0] << ", " << v[1] << " " << newPriority << std::endl;
  82. put(priorityMap, *vertexIterator, newPriority);
  83. mutableQueue.update(*vertexIterator);
  84. }
  85.  
  86. std::cout << "Heap map after updates:" << std::endl;
  87. OutputIndexHeapMap(graph, index_in_heap);
  88.  
  89. std::cout << "There are " << mutableQueue.size() << " items in the queue." << std::endl;
  90.  
  91. // Output (and empty) the queue
  92. while( ! mutableQueue.empty() )
  93. {
  94. // MutableQueueType::value_type u = mutableQueue.top();
  95. Vertex u = mutableQueue.top();
  96.  
  97. // These two lines are equivalent
  98. std::cout << "vertex: " << u[0] << " " << u[1]
  99. << " priority: " << get(mutableQueue.keys(), u)
  100. << std::endl;
  101.  
  102. mutableQueue.pop();
  103. }
  104.  
  105. std::cout << "Heap map at end:" << std::endl; // All (size_t)(-1)
  106. OutputIndexHeapMap(graph, index_in_heap);
  107.  
  108. std::cout << std::endl;
  109.  
  110. return 0;
  111. }
  112.  
  113. template <typename TGraph, typename TIndexInHeapMap>
  114. static void OutputIndexHeapMap(TGraph g, TIndexInHeapMap indexHeapMap)
  115. {
  116. typedef typename boost::graph_traits<TGraph>::vertex_iterator VertexIteratorType;
  117. VertexIteratorType vertexIterator, vertexIteratorEnd;
  118. for( tie(vertexIterator, vertexIteratorEnd) = vertices(g); vertexIterator != vertexIteratorEnd; ++vertexIterator)
  119. {
  120. std::cout << "Index: " << get(indexHeapMap, *vertexIterator) << std::endl;
  121. }
  122. }
  123.  
Not running #stdin #stdout 0s 0KB
stdin
Standard input is empty
stdout
Standard output is empty