Boost logo

Boost Users :

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


Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net