Re: [Boost-users] Using a binomial_heap with indirect_cmp

Subject: Re: [Boost-users] Using a binomial_heap with indirect_cmp
From: David Doria (daviddoria_at_[hidden])
Date: 2012-09-05 17:36:20

On Wed, Sep 5, 2012 at 3:27 PM, David Doria <daviddoria_at_[hidden]> wrote:
> I am trying to keep a heap sorted by values in a property map. I tried
> the code below, but the compiler does not like my arguments to the
> heap constructor (PriorityQueueType pq(indirectComparison);).
> According to the documentation
> (http://www.boost.org/doc/libs/1_51_0/doc/html/boost/heap/binomial_heap.html),
> there is a constructor:
>
>   explicit binomial_heap(value_compare const & = value_compare());
>
> that takes a value_compare, which I was thinking would of type
> IndirectComparisonType that I provided (I don't really understand the
> optional template arguments and the base_maker::compare_argument type
> of things)?
>
> Here is the indirect_cmp doc for reference:
> http://www.boost.org/doc/libs/1_51_0/boost/pending/indirect_cmp.hpp
>
> #include <boost/heap/binomial_heap.hpp>
> #include <boost/pending/indirect_cmp.hpp>
> #include <boost/array.hpp>
> #include <boost/graph/grid_graph.hpp>
> #include <iostream>
>
> int main(int, char*[])
> {
>   // Construct a graph
>   boost::array<std::size_t, 2> lengths = { { 2,2 } };
>   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));
>
>   // Construct a property map
>   typedef boost::vector_property_map<float, GridIndexMapType> PriorityMapType;
>   PriorityMapType priorityMap(gridIndexMap);
>
>   // Construct the indirect comparison functor
>   typedef boost::indirect_cmp<PriorityMapType, std::less<float> >
> IndirectComparisonType;
>   IndirectComparisonType indirectComparison(priorityMap);
>
>   // Construct the queue
>   typedef int ValueType;
>   typedef boost::heap::binomial_heap<ValueType,
> boost::heap::stable<false>, IndirectComparisonType> PriorityQueueType;
>   PriorityQueueType pq(indirectComparison);
>
>   return 0;
> }
>
> Does anyone know how to provide this indirect comparison functor to
> the queue properly?
>
> Thanks,
>
> David

I found out that you have to wrap the option:

typedef boost::heap::binomial_heap<Vertex, boost::heap::stable<false>,
boost::heap::compare<IndirectComparisonType> > PriorityQueueType;

versus what I was trying before:

typedef boost::heap::binomial_heap<Vertex, boost::heap::stable<false>,
IndirectComparisonType > PriorityQueueType;

Here is an example of how to do use this indirect heap:
http://programmingexamples.net/wiki/CPP/Boost/Heap/IndirectCompare

David