Difference between revisions of "CPP/Boost/BGL/IndirectPriorityQueue"

From ProgrammingExamples
< CPP
Jump to: navigation, search
(Created page with '==IndirectPriorityQueue.cpp== <source lang="cpp"> #include <iostream> #include <iomanip> #include <boost/graph/grid_graph.hpp> #include <boost/graph/detail/d_ary_heap.hpp> #incl…')
 
 
Line 9: Line 9:
  
 
#include <cstdlib>
 
#include <cstdlib>
 +
 +
template <typename TQueue>
 +
static void OutputQueue(TQueue queue);
  
 
int main(int, char*[])
 
int main(int, char*[])
Line 31: Line 34:
  
 
   typedef std::greater<float> ComparisonFunctor;
 
   typedef std::greater<float> ComparisonFunctor;
−
   typedef boost::d_ary_heap_indirect<Vertex, 4, IndexInHeapMap, PriorityMapType, ComparisonFunctor > MutableQueue;
+
   typedef boost::d_ary_heap_indirect<Vertex, 4, IndexInHeapMap, PriorityMapType, ComparisonFunctor > MutableQueueType;
  
 
   ComparisonFunctor comparisonFunctor;
 
   ComparisonFunctor comparisonFunctor;
−
   MutableQueue mutableQueue(priorityMap, index_in_heap, comparisonFunctor);
+
   MutableQueueType mutableQueue(priorityMap, index_in_heap, comparisonFunctor);
  
 
   std::cout << "There are " << mutableQueue.size() << " items in the queue." << std::endl;
 
   std::cout << "There are " << mutableQueue.size() << " items in the queue." << std::endl;
Line 50: Line 53:
  
 
   std::cout << "There are " << mutableQueue.size() << " items in the queue." << std::endl;
 
   std::cout << "There are " << mutableQueue.size() << " items in the queue." << std::endl;
 +
 +
  std::cout << "The priority queue is: " << std::endl;
 +
  OutputQueue(mutableQueue);
  
 
   // Insert another set of random values for each vertex
 
   // Insert another set of random values for each vertex
Line 65: Line 71:
  
 
   std::cout << "The priority queue is: " << std::endl;
 
   std::cout << "The priority queue is: " << std::endl;
−
   while( ! mutableQueue.empty() )
+
  OutputQueue(mutableQueue);
 +
 
 +
  std::cout << std::endl;
 +
 
 +
  return 0;
 +
}
 +
 
 +
template <typename TQueue>
 +
static void OutputQueue(TQueue queue)
 +
{
 +
   while( ! queue.empty() )
 
   {
 
   {
−
     Vertex u = mutableQueue.top();
+
     typename TQueue::value_type u = queue.top();
  
 
     // These two lines are equivalent
 
     // These two lines are equivalent
−
     std::cout << "vertex: " << u[0] << " " << u[1] << " priority: " << get(priorityMap, u) << std::endl;
+
     std::cout << "vertex: " << u[0] << " " << u[1] << " priority: " << get(queue.keys(), u) << std::endl;
  
−
     mutableQueue.pop();
+
     queue.pop();
 
   }
 
   }
−
 
−
  std::cout << std::endl;
 
−
 
−
  return 0;
 
 
}
 
}
  
Line 83: Line 95:
 
There are 0 items in the queue.
 
There are 0 items in the queue.
 
There are 25 items in the queue.
 
There are 25 items in the queue.
 +
The priority queue is:
 +
vertex: 4 3 priority: 989
 +
vertex: 3 2 priority: 976
 +
vertex: 0 1 priority: 937
 +
vertex: 1 4 priority: 824
 +
vertex: 0 2 priority: 805
 +
vertex: 1 0 priority: 770
 +
vertex: 4 2 priority: 770
 +
vertex: 4 4 priority: 733
 +
vertex: 2 2 priority: 623
 +
vertex: 0 4 priority: 566
 +
vertex: 3 0 priority: 513
 +
vertex: 4 0 priority: 494
 +
vertex: 2 3 priority: 418
 +
vertex: 3 1 priority: 411
 +
vertex: 1 1 priority: 408
 +
vertex: 0 3 priority: 378
 +
vertex: 3 3 priority: 300
 +
vertex: 3 4 priority: 286
 +
vertex: 0 0 priority: 206
 +
vertex: 2 1 priority: 198
 +
vertex: 1 2 priority: 159
 +
vertex: 2 0 priority: 157
 +
vertex: 2 4 priority: 108
 +
vertex: 1 3 priority: 103
 +
vertex: 4 1 priority: 5
 
There are 50 items in the queue.
 
There are 50 items in the queue.
 
The priority queue is:  
 
The priority queue is:  
−
vertex: 2 4 priority: 967
+
vertex: 3 0 priority: 998
−
vertex: 0 0 priority: 945
+
vertex: 3 2 priority: 979
−
vertex: 0 0 priority: 945
+
vertex: 3 2 priority: 979
−
vertex: 1 3 priority: 922
+
vertex: 2 4 priority: 920
−
vertex: 0 2 priority: 907
+
vertex: 0 1 priority: 853
−
vertex: 4 4 priority: 901
+
vertex: 0 1 priority: 853
−
vertex: 2 4 priority: 967
+
vertex: 3 0 priority: 998
−
vertex: 4 4 priority: 901
+
vertex: 4 4 priority: 842
−
vertex: 0 1 priority: 858
+
vertex: 2 2 priority: 830
−
vertex: 0 2 priority: 907
+
vertex: 2 2 priority: 830
−
vertex: 0 1 priority: 858
+
vertex: 3 3 priority: 811
−
vertex: 3 4 priority: 852
+
vertex: 3 3 priority: 811
−
vertex: 3 4 priority: 852
+
vertex: 0 2 priority: 781
−
vertex: 2 2 priority: 793
+
vertex: 0 2 priority: 781
−
vertex: 2 2 priority: 793
+
vertex: 1 1 priority: 556
−
vertex: 1 3 priority: 922
+
vertex: 4 0 priority: 517
−
vertex: 1 1 priority: 791
+
vertex: 4 0 priority: 517
−
vertex: 1 1 priority: 791
+
vertex: 4 3 priority: 464
−
vertex: 4 2 priority: 781
+
vertex: 4 3 priority: 464
−
vertex: 4 2 priority: 781
+
vertex: 3 1 priority: 363
−
vertex: 1 2 priority: 748
+
vertex: 3 1 priority: 363
−
vertex: 1 2 priority: 748
+
vertex: 0 4 priority: 345
−
vertex: 2 3 priority: 734
+
vertex: 1 1 priority: 556
−
vertex: 4 3 priority: 661
+
vertex: 0 4 priority: 345
−
vertex: 4 3 priority: 661
+
vertex: 1 2 priority: 300
−
vertex: 2 3 priority: 734
+
vertex: 1 2 priority: 300
−
vertex: 3 3 priority: 652
+
vertex: 4 4 priority: 842
−
vertex: 3 3 priority: 652
+
vertex: 2 1 priority: 287
−
vertex: 3 2 priority: 529
+
vertex: 2 1 priority: 287
−
vertex: 3 2 priority: 529
+
vertex: 2 3 priority: 222
−
vertex: 3 0 priority: 493
+
vertex: 2 3 priority: 222
−
vertex: 3 0 priority: 493
+
vertex: 1 0 priority: 197
−
vertex: 2 0 priority: 488
+
vertex: 2 4 priority: 920
−
vertex: 2 0 priority: 488
+
vertex: 1 0 priority: 197
−
vertex: 4 1 priority: 450
+
vertex: 1 4 priority: 189
−
vertex: 4 1 priority: 450
+
vertex: 1 4 priority: 189
−
vertex: 4 0 priority: 346
+
vertex: 0 3 priority: 187
−
vertex: 4 0 priority: 346
+
vertex: 0 3 priority: 187
−
vertex: 0 3 priority: 328
+
vertex: 1 3 priority: 136
−
vertex: 0 3 priority: 328
+
vertex: 1 3 priority: 136
−
vertex: 1 4 priority: 245
+
vertex: 0 0 priority: 119
−
vertex: 1 4 priority: 245
+
vertex: 0 0 priority: 119
−
vertex: 1 0 priority: 216
+
vertex: 2 0 priority: 118
−
vertex: 1 0 priority: 216
+
vertex: 2 0 priority: 118
−
vertex: 0 4 priority: 64
+
vertex: 3 4 priority: 115
−
vertex: 0 4 priority: 64
+
vertex: 3 4 priority: 115
−
vertex: 2 1 priority: 47
+
vertex: 4 1 priority: 70
−
vertex: 2 1 priority: 47
+
vertex: 4 1 priority: 70
−
vertex: 3 1 priority: 14
+
vertex: 4 2 priority: 63
−
vertex: 3 1 priority: 14
+
vertex: 4 2 priority: 63
  
 
*/
 
*/
 +
 
</source>
 
</source>
  

Latest revision as of 10:51, 3 September 2012

IndirectPriorityQueue.cpp

#include <iostream>
#include <iomanip>
 
#include <boost/graph/grid_graph.hpp>
#include <boost/graph/detail/d_ary_heap.hpp>
#include <boost/property_map/property_map.hpp>
 
#include <cstdlib>
 
template <typename TQueue>
static void OutputQueue(TQueue queue);
 
int main(int, char*[])
{
  srand((unsigned int)time(NULL));
 
  boost::array<std::size_t, 2> lengths = { { 5,5 } };
  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::vector_property_map<std::size_t, GridIndexMapType> IndexInHeapMap;
  IndexInHeapMap index_in_heap(gridIndexMap);
 
  typedef boost::graph_traits<GraphType>::vertex_iterator VertexIteratorType;
 
  typedef boost::vector_property_map<float, GridIndexMapType> PriorityMapType;
  PriorityMapType priorityMap(gridIndexMap);
  VertexIteratorType vertexIterator, vertexIteratorEnd;
 
  typedef std::greater<float> ComparisonFunctor;
  typedef boost::d_ary_heap_indirect<Vertex, 4, IndexInHeapMap, PriorityMapType, ComparisonFunctor > MutableQueueType;
 
  ComparisonFunctor comparisonFunctor;
  MutableQueueType mutableQueue(priorityMap, index_in_heap, comparisonFunctor);
 
  std::cout << "There are " << mutableQueue.size() << " items in the queue." << std::endl;
 
  // Add random values to the vertices and add them to the queue
  for( tie(vertexIterator, vertexIteratorEnd) = vertices(graph); vertexIterator != vertexIteratorEnd; ++vertexIterator)
  {
    put(priorityMap, *vertexIterator, rand() % 1000);
  }
 
  for( tie(vertexIterator, vertexIteratorEnd) = vertices(graph); vertexIterator != vertexIteratorEnd; ++vertexIterator)
  {
    mutableQueue.push(*vertexIterator);
  }
 
  std::cout << "There are " << mutableQueue.size() << " items in the queue." << std::endl;
 
  std::cout << "The priority queue is: " << std::endl;
  OutputQueue(mutableQueue);
 
  // Insert another set of random values for each vertex
  for( tie(vertexIterator, vertexIteratorEnd) = vertices(graph); vertexIterator != vertexIteratorEnd; ++vertexIterator)
  {
    put(priorityMap, *vertexIterator, rand() % 1000);
  }
 
  for( tie(vertexIterator, vertexIteratorEnd) = vertices(graph); vertexIterator != vertexIteratorEnd; ++vertexIterator)
  {
    mutableQueue.push(*vertexIterator);
  }
 
  std::cout << "There are " << mutableQueue.size() << " items in the queue." << std::endl;
 
  std::cout << "The priority queue is: " << std::endl;
  OutputQueue(mutableQueue);
 
  std::cout << std::endl;
 
  return 0;
}
 
template <typename TQueue>
static void OutputQueue(TQueue queue)
{
  while( ! queue.empty() )
  {
    typename TQueue::value_type u = queue.top();
 
    // These two lines are equivalent
    std::cout << "vertex: " << u[0] << " " << u[1] << " priority: " << get(queue.keys(), u) << std::endl;
 
    queue.pop();
  }
}
 
/* Output:
There are 0 items in the queue.
There are 25 items in the queue.
The priority queue is: 
vertex: 4 3 priority: 989
vertex: 3 2 priority: 976
vertex: 0 1 priority: 937
vertex: 1 4 priority: 824
vertex: 0 2 priority: 805
vertex: 1 0 priority: 770
vertex: 4 2 priority: 770
vertex: 4 4 priority: 733
vertex: 2 2 priority: 623
vertex: 0 4 priority: 566
vertex: 3 0 priority: 513
vertex: 4 0 priority: 494
vertex: 2 3 priority: 418
vertex: 3 1 priority: 411
vertex: 1 1 priority: 408
vertex: 0 3 priority: 378
vertex: 3 3 priority: 300
vertex: 3 4 priority: 286
vertex: 0 0 priority: 206
vertex: 2 1 priority: 198
vertex: 1 2 priority: 159
vertex: 2 0 priority: 157
vertex: 2 4 priority: 108
vertex: 1 3 priority: 103
vertex: 4 1 priority: 5
There are 50 items in the queue.
The priority queue is: 
vertex: 3 0 priority: 998
vertex: 3 2 priority: 979
vertex: 3 2 priority: 979
vertex: 2 4 priority: 920
vertex: 0 1 priority: 853
vertex: 0 1 priority: 853
vertex: 3 0 priority: 998
vertex: 4 4 priority: 842
vertex: 2 2 priority: 830
vertex: 2 2 priority: 830
vertex: 3 3 priority: 811
vertex: 3 3 priority: 811
vertex: 0 2 priority: 781
vertex: 0 2 priority: 781
vertex: 1 1 priority: 556
vertex: 4 0 priority: 517
vertex: 4 0 priority: 517
vertex: 4 3 priority: 464
vertex: 4 3 priority: 464
vertex: 3 1 priority: 363
vertex: 3 1 priority: 363
vertex: 0 4 priority: 345
vertex: 1 1 priority: 556
vertex: 0 4 priority: 345
vertex: 1 2 priority: 300
vertex: 1 2 priority: 300
vertex: 4 4 priority: 842
vertex: 2 1 priority: 287
vertex: 2 1 priority: 287
vertex: 2 3 priority: 222
vertex: 2 3 priority: 222
vertex: 1 0 priority: 197
vertex: 2 4 priority: 920
vertex: 1 0 priority: 197
vertex: 1 4 priority: 189
vertex: 1 4 priority: 189
vertex: 0 3 priority: 187
vertex: 0 3 priority: 187
vertex: 1 3 priority: 136
vertex: 1 3 priority: 136
vertex: 0 0 priority: 119
vertex: 0 0 priority: 119
vertex: 2 0 priority: 118
vertex: 2 0 priority: 118
vertex: 3 4 priority: 115
vertex: 3 4 priority: 115
vertex: 4 1 priority: 70
vertex: 4 1 priority: 70
vertex: 4 2 priority: 63
vertex: 4 2 priority: 63
 
*/

CMakeLists.txt

cmake_minimum_required(VERSION 2.6)
 
Project(IndirectPriorityQueue)
 
set(Boost_USE_MULTITHREADED ON)
FIND_PACKAGE(Boost 1.38 COMPONENTS)
 
INCLUDE_DIRECTORIES(${INCLUDE_DIRECTORIES} ${Boost_INCLUDE_DIRS})
LINK_DIRECTORIES(${LINK_DIRECTORIES} ${Boost_LIBRARY_DIRS})
 
ADD_EXECUTABLE(IndirectPriorityQueue IndirectPriorityQueue.cpp)
Retrieved from "http://programmingexamples.net/w/index.php?title=CPP/Boost/BGL/IndirectPriorityQueue&oldid=5181"