fork download 
#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 TGraph, typename TIndexInHeapMap>
static void OutputIndexHeapMap(TGraph g, TIndexInHeapMap indexHeapMap);

int main(int, char*[])
{
  // Seed random number gererators
  srand((unsigned int)time(NULL));
  srand48((unsigned int)time(NULL));

  // Create a graph
  boost::array<std::size_t, 2> lengths = { { 2,2 } };
  typedef boost::grid_graph<2> GraphType;
  GraphType graph(lengths);

  // Declare iterators that we will use
  typedef boost::graph_traits<GraphType>::vertex_iterator VertexIteratorType;

  VertexIteratorType vertexIterator, vertexIteratorEnd;

  // Setup the graph properties
  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);

  // Initialize
  for( tie(vertexIterator, vertexIteratorEnd) = vertices(graph); vertexIterator != vertexIteratorEnd; ++vertexIterator)
  {
    put(index_in_heap, *vertexIterator, (size_t)(-1));
  }

  std::cout << "Initial heap map" << std::endl;
  OutputIndexHeapMap(graph, index_in_heap);

  typedef boost::vector_property_map<float, GridIndexMapType> PriorityMapType;
  PriorityMapType priorityMap(gridIndexMap);

  // Setup the queue
  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)
  {
    float newPriority = rand() % 1000;
    Vertex v = *vertexIterator;

    std::cout << "Original priority for " << v[0] << ", " << v[1] << " " << newPriority << std::endl;
    put(priorityMap, *vertexIterator, newPriority);
    mutableQueue.push(*vertexIterator);
  }

  std::cout << "Heap map after initial pushes:" << std::endl;
  OutputIndexHeapMap(graph, index_in_heap);

  std::cout << "There are " << mutableQueue.size() << " items in the queue." << std::endl;

  // Insert another set of random values for each vertex
  for( tie(vertexIterator, vertexIteratorEnd) = vertices(graph); vertexIterator != vertexIteratorEnd; ++vertexIterator)
  {
    float newPriority = rand() % 1000;

    Vertex v = *vertexIterator;
    std::cout << "New priority for " << v[0] << ", " << v[1] << " " << newPriority << std::endl;
    put(priorityMap, *vertexIterator, newPriority);
    mutableQueue.update(*vertexIterator);
  }

  std::cout << "Heap map after updates:" << std::endl;
  OutputIndexHeapMap(graph, index_in_heap);

  std::cout << "There are " << mutableQueue.size() << " items in the queue." << std::endl;

  // Output (and empty) the queue
  while( ! mutableQueue.empty() )
  {
//    MutableQueueType::value_type u = mutableQueue.top();
    Vertex u = mutableQueue.top();

    // These two lines are equivalent
    std::cout << "vertex: " << u[0] << " " << u[1]
              << " priority: " << get(mutableQueue.keys(), u)
              << std::endl;

    mutableQueue.pop();
  }

  std::cout << "Heap map at end:" << std::endl; // All (size_t)(-1)
  OutputIndexHeapMap(graph, index_in_heap);

  std::cout << std::endl;

  return 0;
}

template <typename TGraph, typename TIndexInHeapMap>
static void OutputIndexHeapMap(TGraph g, TIndexInHeapMap indexHeapMap)
{
  typedef typename boost::graph_traits<TGraph>::vertex_iterator VertexIteratorType;
  VertexIteratorType vertexIterator, vertexIteratorEnd;
  for( tie(vertexIterator, vertexIteratorEnd) = vertices(g); vertexIterator != vertexIteratorEnd; ++vertexIterator)
  {
    std::cout << "Index: " << get(indexHeapMap, *vertexIterator) << std::endl;
  }
}
Not running #stdin #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/cZosV
language:
C++ (gcc 8.3)
created:
13 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!